Graph Implementation

Let's now look more closely at a Python implementation of a graph that we'll be using throughout this week. The implementation uses an adjacency list approach, where we have:

• A linked list of Vertex objects representing the vertices of the graph
• Each Vertex object contains a linked list of Edge objects, representing the edges that are connected to the given Vertex
• Each Edge object contains a reference to the two Vertex objects that it connects, along with a cost (weight)

Here's a visual representation of our forthcoming Graph class:

Try to match up the vertices and edges in the graph on the right with the in-memory representation on the left.

Here's the core definitions of the Graph, Vertex, and Edge objects:

class Graph:
    def __init__(self):
        self.vertices = None    # linked list of vertices in the graph

    class Vertex:
        def __init__(self, id):
            self.id = id        # vertex ID
            self.edges = None   # linked list of edges for this vertex
            self.next = None    # next vertex in the linked list of vertices
        ...

    class Edge:
        def __init__(self, start, end, cost):
            self.start = start  # starting vertex of the edge
            self.end = end      # ending vertex of the edge
            self.cost = cost    # weight of the edge
            self.next = None    # next edge in the linked list of edges
        ...

Here's the full implementation: graph.py

Here's a sample graph: graph.txt

When you run graph.py, you will be prompted to enter both (1) the name of the input file (graph.txt in this case) and (2) the starting point for the algorithms:

$ python graph.py
Graph info file: graph.txt
starting point: Lagos

depth-first traversal from Lagos:
...

Note that there are a methods provided in graph.py:

• get_vertex(), add_vertex(), and add_edge() for fetching and building the graph
• init_from_file(), which reads in a graph configuration from a file and creates a Graph object with the vertices and edges that are listed in the file (example file)
• Various graph algorithms: breadth_first_trav(), depth_first_trav(), and prim()
• Since the various graph algorithms may mark the graph (such as to mark vertices as encountered or done), there is a reinit_vertices() method that resets the state of each vertex so that the next algorithm can have a clean slate