[Data Structure] Python: Graphs

Vertex and Graph Class

The Graph class holds a vertex adjacency list using a dictionary that maps a Vertex object to a list of aadjacent Vertex objects.

The Vertex class contains a label, but can be augmented by graph algorithms to contain additional data if required. 

A Graph object is initialized with an empty adjacency list. Vertex objects are created and added to the Graph using the add_vertex() method. 

class Vertex:
    def __init__(self, label):
        self.label = label
        
class Graph:
    def __init__(self):
        self.adjacency_list = {}
  
    def add_vertex(self, new_vertex):
        self.adjacency_list[new_vertex] = []
        
# Program to create and populate a Graph object.
g = Graph()
vertex_a = Vertex("New York")
vertex_b = Vertex("Tokyo")
vertex_c = Vertex("London")

g.add_vertex(vertex_a)
g.add_vertex(vertex_b)
g.add_vertex(vertex_c)

 

Graph Edges and Edge Weights

Edges are represented as vertex pairs, using a 2-item tuple.
Ex: (vertex_a, vertex_b) is an edge that goes from vertex_a to vertex_b.

Undirected edges are two symmetric vertex pairs: (vertex_a, vertex_b) and (vertex_b, vertex_a).

 

Edges also have numeric weights.

By default, an edge is assigned with weight 1.0. Edge weights are stored in the dictionary edge_weights where the vertex pair is the key and the edge weight is the value. 

class Graph:
    def __init__(self):
        self.adjacency_list = {}
        self.edge_weights = {}
        
    def add_vertex(self, new_vertex):
        self.adjacency_list[new_vertex] = []
        
    def add_directed_edge(self, from_vertex, to_vertex, weight = 1.0):
        self.edge_weights[(from_vertex, to_vertex)] = weight
        self.adjacency_list[from_vertex].append(to_vertex)
        
    def add_undirected_edge(self, vertex_a, vertex_b, weight = 1.0):
        self.add_directed_edge(vertex_a, vertex_b, weight)
        self.add_directed_edge(vertex_b, vertex_a, weight)

 

 

---

Python: Breadth-First Search

 

Breadth-first search traverses a graph by starting at a specific vertex and visiting the vertex's adjacent vertices before visiting the next closest vertices. No vertex is re-visited.

# Breadth-first search function
def breadth_first_search(graph, start_vertex, distances=dict()):
    discovered_set = set()
    frontier_queue = Queue()
    visited_list = []
    
    # start_vertex has a distance of 0 from itself
    distances[start_vertex] = 0

    frontier_queue.enqueue(start_vertex) # Enqueue start_vertex in frontier_queue
    discovered_set.add(start_vertex)     # Add start_vertex to discovered_set

    while (frontier_queue.list.head != None):
        current_vertex = frontier_queue.dequeue()
        visited_list.append(current_vertex)
        for adjacent_vertex in graph.adjacency_list[current_vertex]:
            if adjacent_vertex not in discovered_set:
                frontier_queue.enqueue(adjacent_vertex)
                discovered_set.add(adjacent_vertex)
                
                # Distance of adjacent_vertex is 1 more than current_vertex
                distances[adjacent_vertex] = distances[current_vertex] + 1
    return visited_list

 

 

---

Python: Depth-First Search

 

Depth-first search traverses a graph by first visiting a specific starting vertex, and then visiting every vertex along each path originating from the starting vertex. Each path is traversed to the path's end before backtracking.

# Depth-first search function
def depth_first_search(graph, start_vertex, visit_function):
    vertex_stack = [start_vertex]
    visited_set = set()

    while len(vertex_stack) > 0:
        current_vertex = vertex_stack.pop()
        if current_vertex not in visited_set:
            visit_function(current_vertex)
            visited_set.add(current_vertex)
            for adjacent_vertex in graph.adjacency_list[current_vertex]:
                vertex_stack.append(adjacent_vertex)