7.6. ImplementationΒΆ
Using dictionaries, it is easy to implement the adjacency list in Python. In
our implementation of the Graph abstract data type we will create two classes
(see Listing 1 and Listing 2),
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 weights are not needed, a set could
be used instead of a dictionary. In order to handle both cases, a dictionary
called neighbors is used, but it is given a default value of None.
The listing below shows the code for the Vertex class. The initialization
method simply initializes the key, which will typically be a string,
and the neighbors dictionary. The add_neighbor method is used add a
connection from this vertex to another. The connections method returns
all of the vertices in the adjacency list, as represented by the neighbors
instance variable. The weight method returns the weight of the edge from
this vertex to the vertex passed as a parameter, or None if it is not set.
Listing 1
class Vertex:
def __init__(self, key):
self.key = key
self.neighbors = {}
def add_neighbor(self, neighbor, weight=None):
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 in the next listing, contains a dictionary that maps
vertex names to vertex objects. In Figure 4 this
dictionary object is represented by the shaded gray box. 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.
Listing 2
class Graph:
def __init__(self):
self.vertices = {}
def add_vertex(self, vertex):
self.vertices[vertex.key] = vertex
def get_vertex(self, key):
if key in self.vertices[key]:
return self.vertices[key]
else:
return None
def __contains__(self, key):
"""
Overload the in operator to support:
>>> g = Graph()
>>> g.add_vertex(Vertex(42))
>>> 42 in g
True
"""
return key in self.vertices
def add_edge(self, from_key, to_key, weight=None):
if from_key not in self.vertices:
self.add_vertex(Vertex(from_key))
if to_key not in self.vertices:
self.add_vertex(Vertex(to_key))
self.vertices[from_key].add_neighbor(
self.vertices[to_key],
weight
)
def get_vertices(self):
return self.vertices.keys()
def __iter__(self):
return iter(self.vertices.values())
Using the Graph and Vertex classes just defined, the following Python
session creates the graph in Figure 2. 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. You
should check the output of the edge list at the end of this session against
Figure 2.
>>> g = Graph()
>>> for i in range(6):
... g.add_vertex(Vertex(i))
...
>>> g.vertices
{0: <graphs.Vertex object at 0x7f8e3b60ff98>,
1: <graphs.Vertex object at 0x7f8e3b633b70>,
2: <graphs.Vertex object at 0x7f8e3b633e80>,
3: <graphs.Vertex object at 0x7f8e3b633f60>,
4: <graphs.Vertex object at 0x7f8e3b633f98>,
5: <graphs.Vertex object at 0x7f8e3b633fd0>}
>>> 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