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())
    
    def add_vertex(self, key):
        # 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
        self.vertices[from_key].add_neighbor(self.vertices[to_key], weight)

Testing

In [51]:
g = Graph()
In [52]:
for i in range(65, 71):
    g.add_vertex(chr(i))
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]:
g.add_edge("Z","A", 5)
---------------------------------------------------------------------------
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]:
g.add_edge("A","Z", 5)
---------------------------------------------------------------------------
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:
    g.add_edge("A","Z", 5)
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]:
g.add_edge('A', 'B', 5)

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)
    g.add_edge(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]:
nodeA A nodeB B nodeA->nodeB nodeC C nodeA->nodeC nodeB->nodeC nodeE E nodeB->nodeE nodeC->nodeA nodeC->nodeB nodeE->nodeA nodeE->nodeC nodeF F nodeE->nodeF nodeD D nodeD->nodeB nodeD->nodeF nodeF->nodeE