# Graphs¶

## Using Adjacency List Representation¶

In [9]:
import sys
from pythonds9.graphs.utils import viz_graph
import random
In [4]:
sys.maxsize
Out[4]:
9223372036854775807
In [10]:
class VertexError(Exception):
pass
In [37]:
class Vertex:
def __init__(self, key):
self.id = key
self.connected_to = {}  # "adjacency list", represented a dict
self.color = "white"
self.dist = sys.maxsize
self.pred = None
self.disc = 0
self.fin = 0

def __str__(self):
return f"<Vertex({self.id}): connected to: {[x.id for x in self.connected_to]}"

def __repr__(self):
return f"Vertex({self.id!r})"

def add_neighbor(self, nbr, weight=0):
self.connected_to[nbr] = weight

def set_color(self, color):
self.color = color

def set_distance(Self, d):
self.dist = d

def set_pred(self, p):
self.pred = p

def set_finish(self, ftime):
self.fin = ftime

def get_finish(self):
return self.fin

def get_discovery(self):
return self.disc

def get_pred(self):
return self.pred

def get_distance(self):
return self.dist

def get_color(self):
return self.color

def get_connections(self):
# returns the neighbors to this Vertex as a list of their Vertex objects
return self.connected_to.keys()

def get_weight(self, nbr):
return self.connected_to[nbr]

def get_id(self):
return self.id
In [38]:
class Graph:
def __init__(self):
self.vertices = {}
self.num_vertices = 0

def __contains__(self, key):
return key in self.vertices

def __iter__(self):
return iter(self.vertices.values())

# What to do if this key already exists here?
if key not in self.vertices:
new_vertex = Vertex(key)
self.vertices[key] = new_vertex
self.num_vertices += 1

def get_vertex(self, key):
if key in self.vertices:
return self.vertices[key]
else:
return None

# Alternative one-liner
# return self.vertices.get(key)

def add_edge(self, from_key, to_key, weight=0):
"""Add an edge between existing vertices

Vertices are expected to exist, or else a VertexError will
be raise
"""

if from_key not in self.vertices:
raise VertexError(f"'From' Vertex key {from_key!r} not found!")

if to_key not in self.vertices:
raise VertexError(f"'To' Vertex key {to_key!r} not found!")

# lookup the 'from' Vertex object and add a new neighbor to it

## Testing¶

In [51]:
g = Graph()
In [52]:
for i in range(65, 71):
In [53]:
print(g.vertices)
{'A': Vertex('A'), 'B': Vertex('B'), 'C': Vertex('C'), 'D': Vertex('D'), 'E': Vertex('E'), 'F': Vertex('F')}
In [54]:
---------------------------------------------------------------------------
VertexError                               Traceback (most recent call last)
<ipython-input-54-850dcff6de1a> in <module>
----> 1 g.add_edge("Z","A", 5)

<ipython-input-38-48e8457a99e3> in add_edge(self, from_key, to_key, weight)
34
35         if from_key not in self.vertices:
---> 36             raise VertexError(f"'From' Vertex key {from_key!r} not found!")
37
38         if to_key not in self.vertices:

VertexError: 'From' Vertex key 'Z' not found!
In [55]:
---------------------------------------------------------------------------
VertexError                               Traceback (most recent call last)
<ipython-input-55-3d9a7617de16> in <module>
----> 1 g.add_edge("A","Z", 5)

<ipython-input-38-48e8457a99e3> in add_edge(self, from_key, to_key, weight)
37
38         if to_key not in self.vertices:
---> 39             raise VertexError(f"'To' Vertex key {to_key!r} not found!")
40
41         # lookup the 'from' Vertex object and add a new neighbor to it

VertexError: 'To' Vertex key 'Z' not found!
In [56]:
try:
except VertexError:
# maybe we create the vertex as an error handling?
# we don't know if the From or To vertex is missing
pass
In [57]:

### Create a series of randomly created edges between the vertices in our graph¶

In [58]:
for i in range(15):

# Ensures we choose no duplicate "self" vertices
while True:
k_from = random.choice(list(g.vertices))
k_to = random.choice(list(g.vertices))

if k_from != k_to:
break

cost = random.choice(range(0, 11))
print(k_from, k_to, cost)
C A 6
D F 9
F E 1
C B 0
E C 10
B C 8
C A 7
C A 4
E F 8
C A 8
C B 1
E A 6
B E 5
D B 10
A C 10
In [59]:
for v in g:
for w in v.get_connections():
print(f"({v.get_id()}, {w.get_id()})")
(A, B)
(A, C)
(B, C)
(B, E)
(C, A)
(C, B)
(D, F)
(D, B)
(E, C)
(E, F)
(E, A)
(F, E)
In [60]:
g.get_vertex('A').connected_to
Out[60]:
{Vertex('B'): 5, Vertex('C'): 10}

### Visualize using viz_graph¶

In [61]:
viz_graph(g, show_arrows=True)
Out[61]: