Object-Oriented Graph Implementation

I demonstrated how a hash table can be used to implement a graph, but going forward, we’ll work with an object-oriented approach.

Here’s the beginning of an object-oriented graph implementation, using Python:

The Vertex class has two primary attributes, the value and an array of adjacent_vertices. In our social network example, each vertex represents a person, and the value might be a string containing the person’s name. With a more complex application, we’d probably want to store multiple pieces of data inside a vertex, such as the person’s additional profile information.

The adjacent_vertices array contains all the vertices this vertex connects to. We can add a new adjacent vertex to a given vertex using the add_adjacent_vertex method.

Here’s how we can use this class to build a directed graph representing who follows whom in this image:

Now, if we were building an undirected graph for the social network (where all friendships are mutual), it would make sense if we add Bob to Alice’s list of friends, we should automatically add Alice to Bob’s list of friends as well.

To do this, we can modify our add_adjacent_vertex method as follows:

Let’s say we’re calling this method on Alice and adding Bob to her list of friends. As with the previous version, we use self.adjacent_vertices.append(vertex) to add Bob to Alice’s list of adjacent_vertices. However, we also call this very method on Bob’s vertex, with vertex.adjacent_vertices.append(self). This adds Alice to Bob’s list of friends as well.

To keep things simple going forward, we’re going to work with graphs that are connected (again, meaning all vertices are connected to each other in some way). With such graphs, we can use this one Vertex class to achieve all the algorithms going forward. The general idea is if we have access to just one vertex, we can find all other vertices from there, since all the vertices are connected.

However, it’s important to point out that if we’re dealing with a disconnected graph, it may be impossible to discover all the vertices just from one vertex. In this case, we may need to store all the graph vertices in some additional data structure, such as an array, so that we have access to all of them. (It’s common to see graph implementations use a separate Graph class to contain this array.)