Representing Graphs With the C++ STL

mgcadmin 14-09-2021

Graphs are an Abstract Data Type (ADT) with ALOT of applications. From pathfinding in artificial intelligence, to network routing, databases, and innumerable other uses, finding an efficient way to represent graphs to be processed by algorithms is an important topic.

Graphs & Graphing Algorithms

Graphs are an Abstract Data Type (ADT) with ALOT of applications. From pathfinding in artificial intelligence, to network routing, databases, and innumerable other uses, finding an efficient way to represent graphs to be processed by algorithms is an important topic.

Thankfully the C++ Standard Template Library offers us a rich selection of container classes to aid in representing graphs easily and efficiently. But before we get into all of that, lets run through some basic graphing vocabulary.

Terminology

Graphs are comprised of nodes, called Vertexes, which are connected By Edges. You'll often see this written as G = {V, E}.

G = {V, E}  or Graphs = Vertexes and the Edges that link them.

Edges can be directed, or undirected. A directed edge means that If an Edge exists between vertex 'A' and vertex 'B' it's like a one way street, you can travel from A to B, but not the other way unless the edge 'B' -> 'A' is specified to exist as well. Conversely, If an edge is undirected then it is implicitly understood that if edge 'A' -> 'B' exists, than edge 'B' -> 'A' does as well.

A directed graph and an undirected graph may have the same vertexes, but they will be processed VERY differently because of their edges. Aside from being directed and undirected, an Edge can also be 'weighted' or 'unweighted'. Weights can be used to represent things like distance. For example, if our vertexes represent cities, an edge might represent a highway between those two cities, with the distance between the two cities being the edges weight. 

When an edge exists between two vertexes, the vertexes are whats called 'adjacent'. Adjacency is how we will represent our graph data for graphing algorithms. The two dominant ways for representing graphs are:

1. Adjacency List - An adjacency list is a list of edges (and possibly weights) for each vertex in the graph. They are best used for representing 'sparse', or graphs with smaller amounts of nodes. Their space complexity is O(V+E).
2. Adjacency Matrix - an adjacency matrix is an N x M (in the case of unweighted graphs) boolean matrix where a 0 represents no adjacency, and 1 represents adjacency. For a weighted graph, the weights are used to represent adjacency instead of a 1. They can pack alot of information and are thus good for 'dense' or larger graphs, though they are O(V²).

Adjacency List

The adjacency list representation of a graph can be implemented in about 30 lines of code. By using std::map, std::list, and std::pair we can create an easy to use adjacency list representation of our graph. We're going to create an std::map, that use's char for its key, and its value will be an std::list of type std::pair<char, int>. The std::pair will represent the weighted edge in our list. So if we have adjList['A'], its refrencing a list of the weighted edges belonging to vertex A. Lets take a look at some code to get a clearer picture.

#include <iostream>
#include <map>
#include <list>
using namespace std;

//Our Graph ADT
class Graph {
public:
int V; //number of vertexes in our graph.
Graph(int n) : V(n) { }
std::map<char, std::list<std::pair<char, int>>> adjList;
void addEdge(char v, char u, int w);
void showAdjList();
};

You can see in the class definition how we defined our adjacency list as described above, and have a method for adding edges to that list. We also have a method for displaying the adjacency list:

void Graph::addEdge(char v, char u, int w)
{
   adjList[v].push_back(make_pair(u, w));
   adjList[u].push_back(make_pair(v, w));
}

void Graph::showAdjList()
{
  for (auto v : adjList)
  {
    cout<<v.first<<": ";
    for (auto u : adjList[v.first])
    {
      cout<<u.first<<" ";
    }
    cout<<endl;
  }
}

If we wanted to have a directed graph instead of an undirected graph, we could simply remove or comment out the second line of addEdge(). If we wanted our edges to be unweighted, we'd simply pass '0' as the edge weight. Neat, simple, and efficient. When it comes to the adjacency list representation of graphs, STL Containers give us the right tools for the Job.

Adjacency Matrix

The STL doesnt stop performing just because we've changed representations. Thanks to std::vector, a 2D matrix is easier than ever to implement. Very little has changed in our class definition, infact besides changing from an std::map<char, std::list<std::pair<>>> to an std::vector<std::vector<int>>, the only change is to the class constructor where we resize the vector to the size of our graph:

#include <iostream>
#include <vector>
using namespace std;

class Graph {
public:
int V;
Graph(int n) : V(n+1) { adjMatrix.resize(V, std::vector<int>(V, 0)); }
std::vector<std::vector<int>> adjMatrix;
void addEdge(char v, char u, int w);
void showAdjList();
};

void Graph::addEdge(char v, char u, int w)
{
int a = v - 'A' + 1;
int b = u - 'A' + 1;
adjMatrix[a][b] = w;
adjMatrix[b][a] = w;
}

void Graph::showAdjList()
{
cout<<"\n ";
for (int i = 1; i < V; i++)
  cout<<char(i+'A'-1)<<" ";
cout<<endl;
for (int i = 1; i < V; i++)
{
  cout<<char(i+'A'-1)<<" ";
  for (auto u = 1; u < adjMatrix[i].size(); u++)
  {
    cout<<adjMatrix[i][u]<<" ";
  }
  cout<<endl;
 }
}

Note the code to change from char labels to index values. This allows to continue using char labels for with our adjacency matrix. It also allows us to keep our API identical to the adjacency list representation.

Test Driving our Graph

Lets build the following graph in both matrix and list form, because our API for both is classes is identical, we can use the same driver program for both.

int main()
{
  Graph G(6);
  G.addEdge('A', 'B', 6);
  G.addEdge('A', 'C', 7);
  G.addEdge('A', 'E', 2);
  G.addEdge('B', 'C', 5);
  G.addEdge('C', 'E', 5);
  G.addEdge('D', 'E', 4);
  G.addEdge('D', 'F', 1);
  G.addEdge('E', 'F', 2);
  G.addEdge('F', 'A', 3);
  G.showAdjList();
  return 0;
}

Adjacency Matrix Output: (Note the symmetry created by an undirected graph rep)

  A B C D E F 
A 0 6 7 0 2 3 
B 6 0 5 0 0 0 
C 7 5 0 0 5 0 
D 0 0 0 0 4 1 
E 2 0 5 4 0 2 
F 3 0 0 1 2 0 

Adjacency List output:

A: B C E F 
B: A C 
C: A B E 
D: E F 
E: A C D F 
F: D E A 

We now have two different ways to represent graph data using C++'s Standard Template Library containers. 

Full Source code from this article is available on my github at:

https://github.com/maxgoren/examples/blob/main/graphing-adjlist.cpp

https://github.com/maxgoren/examples/blob/main/graphing-adjmatrix.cpp

---