Graph Representation
I’ve covered in previous articles the basics of graph representation utilizing Adjacency lists and Matrix form as well as Edge List representations, links to those articles can be found at the bottom of the page as well as under the Articles tab at the top. In this article i’m going to explore another method for graph representation that is sometimes called the object oriented graph. This method makes heavy use of data structures, and as the name implies, object oriented principles.
A major departure from the normal convention here is that the concept of the graph node is flushed out more, with each vertex being represented as an object containing its own adjacency list instead of the graph merely being a list of associated labels. This requires a different approach to everything from building and displaying the graph to interacting and traversing the graph. The positive side is that the graph structure becomes more intuitive once you see how it comes together.
The Graph Vertex
In previous articles the graph vertexes were abstract, they were represented by labels and nothing more. Object oriented graphs contain actual vertex objects. To accomplish this were going to create a graph vertex struct with a label for the vertex as well as using a set that will contain pointers to its adjacent vertexes, which will be used as in the same manner as an adjacency list.
We use std::set here because of its desirable property of not allowing duplicates. In an unweighted, undirected graph this allows us to not have to check if a vertex is already on the adjacency list while adding it should the situation arise where an edge is accidentally added twice.
The Graph ADT
With our graph vertex data structure we can work on implementing the rest of our graph ADT. For my graph i used std::map to associate graph labels with a pointer to the actual vertex object. In my implementation i chose to use single letter characters for the vertex labels, but strings or integers could easily be used instead. The important thing is that the constructor be supplied with the number of vertexes the graph will hold so that the vertex objects can be created during graph construction.
As you can see the way we interact with the graph is fundamentally changed, and we need a bit of exception handling to ensure we’re working with valid graph objects.
The getVert() function is innocuously important. In our previous graph representations, the graph was just a label mapped to the list, now our graph is actually vertex objects, and the adjacency list is a list of other vertex objects instead of just more labels.
Traversing the Graph
Because of the fundamental differences in the graph structure, our method of traversal has changed as well. In order to highlight the importance of the getVert() function, i’m going to show how we perform a breadth first traversal. I’m using our vertex objects for the traversal, but only their labels to record the path, in my old adjacency list graph example, we used just the labels for traversal as well.
This method allows us to do more with the graph itself.
I highly reccomend looking at my other articles on Graph representation and traversal to get a deeper understanding of the differences between them and this method, as the difference becomes more appreciative. Those articles can be found here:
Breadth First Search/Single Source Shortest Path
