C++ Graph Implementation
If you have ever tried to google for a C++ graph implementation you mostly likely came across a big heaping (pun intended) mess of pointers. While this approach works fine, the code is very clunky and the interface tends to become awkward to use.
The problem with these implementations is that they do not make use of the excellent data structures that the C++ STL provides. Why define everything in a low level manner when we can abstract all of it away with permformant higher level data structures?
At the highest level, a graph is a set of nodes connected by a set of edges. The most common way to represent this relation is by using an adjacency matrix like so:
Each node in the graph has its own row and column in the matrix.
- m[i][j] = 1 => i is connected to j
- m[i][j] = 0 => i is not connected to j
This idea can be simplified further by saying that each node has a set of adjacent nodes that it is connected to, i.e.
\(i \in m[j] \implies\) i is adjacent to j
So the adjaceny matrix above could be reduced to the following:
{
A : {B, C, D, E},
B : {A, D, E},
C : {A, F},
D : {A, B, F},
E : {A, B, F},
F : {C, D, E}
}
Essentially we have created a map, where the key is a node and the value is a set of nodes.
The relationship that the map represents is adjacency. C++ provides both a set and a map
data structure, so this could be represented as follows:
std::map<T, std::set<T>> g;
Where T is the node payload type. In order to connect node i to node j, we simply add j to i’s set (and vice versa if the graph is bidirectional).
g[i].insert(j);
To disconnect nodes i and j, simply remove j from i’s set
g[i].erase(j);
The full code for this representation is about 16 lines, and is enough to implement almost any graph algorithm (small modifications/additions must be made for some of the more complicated algorithms).