Representing a Graph

In this section we will look at two common abstract representations of graphs: the adjacency matrix and the unfortunately named adjacency “list”. The adjacency list is really a mapping, so in this section we also consider two possible representations in Python of the adjacency list: one an object-oriented approach with a Python dict as its underlying data type, and one just using a plain dict directly.

It’s useful to be familiar with many ways to represent graphs as you will encounter them everywhere. Ultimately though, we see the adjacency list representation using a pure map type (such as a dict in Python) as the most intuitive and flexible.

The Adjacency Matrix

One of the easiest ways to implement a graph is to use a two-dimensional matrix. In this matrix implementation, each of the rows and columns represent a vertex in the graph. The value that is stored in the cell at the intersection of row $v$ and column $w$ indicates if there is an edge from vertex $v$ to vertex $w$. When two vertices are connected by an edge, we say that they are adjacent. The diagram below illustrates the adjacency matrix for the example graph we presented earlier. A value in a cell represents the weight of the edge from vertex $v$ to vertex $w$.

The advantage of the adjacency matrix is that it is simple, and for small graphs it is easy to see which nodes are connected to other nodes. However, notice that most of the cells in the matrix are empty. Because most of the cells are empty we say that this matrix is “sparse.” A matrix is not a very efficient way to store sparse data. In fact, in Python you must go out of your way to even create a matrix structure like the one above.

The adjacency matrix is a good implementation for a graph when the number of edges is large. But what do we mean by large? How many edges would be needed to fill the matrix? Since there is one row and one column for every vertex in the graph, the number of edges required to fill the matrix is $|V|^2$. A matrix is full when every vertex is connected to every other vertex. There are few real problems that approach this sort of connectivity. The problems we will look at in this section all involve graphs that are sparsely connected.

The Adjacency List

A more space-efficient way to implement a sparsely connected graph is to use the unfortunately named adjacency list structure. In an adjacency list implementation we keep a master collection of all the vertices in the Graph object and then each vertex object in the graph maintains a list of the other vertices that it is connected to. In our implementation of the Vertex class we will use a dictionary rather than a list as our master collection, where the dictionary keys are the vertices, and the values are the weights. The diagram below shows an adjacency list representation of the example graph we have been discussing.

The advantage of the adjacency list implementation is that it allows us to compactly represent a sparse graph. The adjacency list also allows us to easily find all the links that are directly connected to a particular vertex.

An Object-Oriented Approach

Using dictionaries, it is easy to implement the adjacency list in Python. In this implementation we create two classes: Graph, which holds the master list of vertices, and Vertex, which will represent each vertex in the graph.

Each Vertex uses a dictionary to keep track of the vertices to which it is connected, and the weight of each edge. If we weren’t concerned with edge weights, we could use a set in place of a dictionary. This dictionary is called neighbors.

In the code below, the add_neighbor method is used to add a connection from this vertex to another. The get_connections method returns all of the vertices in the adjacency list, as represented by the neighbors instance variable. The get_weight method returns the weight of the edge from this vertex to the vertex passed as a parameter.

class Vertex(object):
    def __init__(self, key):
        self.key = key
        self.neighbors = {}

    def add_neighbor(self, neighbor, weight=0):
        self.neighbors[neighbor] = weight

    def __str__(self):
        return '{} neighbors: {}'.format(
            self.key,
            [x.key for x in self.neighbors]
        )

    def get_connections(self):
        return self.neighbors.keys()

    def get_weight(self, neighbor):
        return self.neighbors[neighbor]

The Graph class, shown below, contains a dictionary that maps vertex names to vertex objects. Graph also provides methods for adding vertices to a graph and connecting one vertex to another. The get_vertices method returns the names of all of the vertices in the graph. In addition, we have implemented the __iter__ method to make it easy to iterate over all the vertex objects in a particular graph. Together, the two methods allow you to iterate over the vertices in a graph by name, or by the objects themselves.

class Graph(object):
    def __init__(self):
        self.verticies = {}

    def add_vertex(self, vertex):
        self.verticies[vertex.key] = vertex

    def get_vertex(self, key):
        try:
            return self.verticies[key]
        except KeyError:
            return None

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

    def add_edge(self, from_key, to_key, weight=0):
        if from_key not in self.verticies:
            self.add_vertex(Vertex(from_key))
        if to_key not in self.verticies:
            self.add_vertex(Vertex(to_key))
        self.verticies[from_key].add_neighbor(self.verticies[to_key], weight)

    def get_vertices(self):
        return self.verticies.keys()

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

Using the Graph and Vertex classes just defined, the following Python session creates our example graph. First we create six vertices numbered 0 through 5. Then we display the vertex dictionary. Notice that for each key 0 through 5 we have created an instance of a Vertex. Next, we add the edges that connect the vertices together. Finally, a nested loop verifies that each edge in the graph is properly stored.

>>> g = Graph()
>>> for i in range(6):
...     g.add_vertex(Vertex(i))
>>> g.verticies
{0: <adjGraph.Vertex instance at 0x41e18>,
 1: <adjGraph.Vertex instance at 0x7f2b0>,
 2: <adjGraph.Vertex instance at 0x7f288>,
 3: <adjGraph.Vertex instance at 0x7f350>,
 4: <adjGraph.Vertex instance at 0x7f328>,
 5: <adjGraph.Vertex instance at 0x7f300>}
>>> g.add_edge(0, 1, 5)
>>> g.add_edge(0, 5, 2)
>>> g.add_edge(1, 2, 4)
>>> g.add_edge(2, 3, 9)
>>> g.add_edge(3, 4, 7)
>>> g.add_edge(3, 5, 3)
>>> g.add_edge(4, 0, 1)
>>> g.add_edge(5, 4, 8)
>>> g.add_edge(5, 2, 1)
>>> for v in g:
...     for w in v.get_connections():
...         print('{} -> {}'.format(v.key, w.key))
...
0 -> 5
0 -> 1
1 -> 2
2 -> 3
3 -> 4
3 -> 5
4 -> 0
5 -> 4
5 -> 2

Using Dictionaries Directly

As with our node and edges representation of trees, you may wonder whether it is worthwhile to wrap the underlying structure of our graph with classes as we have above. This will depend on the context, but our general preference is actually to work directly with the data structure. Doing so allows us to more easily print or otherwise debug a graph, create a graph as a literal composite type, and serialize a graph for instance to JSON.

The example graph above would simply look like:

{
    0: {1: 5, 5: 2},
    1: {2: 4},
    2: {3: 9},
    3: {4: 7, 5: 3},
    4: {0: 1},
    5: {4: 8}
}

For the remainder of the chapter, we will use dictionaries directly in most cases.