Graph Representation in C++ (Job Interview Cheatsheet)

Update: you can watch a video on Graph Representation in C++ here:

A graph is formally defined as a set of vertices V and a set of edges E connecting the vertices:

G=(V,E)

Each edge is a pair of vertices. For a directed graph, the edges are ordered pairs and for undirected graphs, the edges are unordered.

How do we represent a graph in C++? This article summarizes various options available using C++ Standard Template Library (STL).

For each method, we will implement a simple algorithm to check to see if the graph is Eulerian, i.e., if the number of odd-degree nodes is exactly 0 or 2. This is known as the Seven Bridges of Königsberg problem.

Method 1: Direct Translation of the Definition: G=(V,E)

This is probably the most straightforward method of representing a graph in C++: we only translate the math definition directly to STL containers.

In this method, V and E can each be represented using either of these STL containers:

std::vector, std::set, std::list

Consider this simple graph:

For simplicity, out of all available options, let's pick:

V: std::vector
E: std::vector
Edges: std::pair

Now, the graph can be defined as a class and easily initialized using STL's uniform initialization:

class Graph {
 public:
  Graph(std::vector<int> &v, std::vector<std::pair<int, int>> &e)
      : v_(v), e_(e) {}
  bool IsEulerWalkable();
  void PrintGraph();
  std::vector<int> v_;
  std::vector<std::pair<int, int>> e_;
};

int main() {
  std::vector<int> v = {0, 1, 2, 3};
  std::vector<std::pair<int, int>> e = {{1, 3}, {1, 3}, {3, 0}, {3, 0},
                                        {0, 2}, {2, 1}, {2, 3}};
  Graph g(v, e);
  std::cout << g.IsEulerWalkable() << std::endl;
}

Notice how nicely initializing vertices and edges in the above code matches the input graph definition.

Having the above definition and initialization, we can now implement

IsEulerWalkable()

as:

bool Graph::IsEulerWalkable() {
  // Create a table to hold degree of each vertex
  std::vector<int> degrees(v_.size());
  
  // Iterate all edges
  for (auto e : e_) {
    degrees[e.first]++;
    degrees[e.second]++;
  }
  int countOdds = 0;

  // Iterate through degree table and count the number of odd ones
  for (auto d : degrees) {
    if (d % 2 == 1) {
      countOdds++;
    }
  }
  return (countOdds == 0 || countOdds == 2);
}

The above code is very self explanatory: we iterate through all edges and add to the degree of each vertex that is on the edge. In the end, we count the number of vertices with odd edges and return true if the count was 0 or 2.

Method 2: Adjacency List

In this method rather than having two separate sets for V and E, conceptually we represent the graph as a mapping between vertices and sets of adjacent vertices. Consider the following graph:

This mapping can be represented using the table below:

To model this in C++, we can create a new class called

Vertex

, which has two member variables:

```
vertex_number
```
: an integer variable
```
adjacents
```
: a set of adjacent vertices


struct Vertex {
  Vertex(int v, std::set<int> a) : vertex_number(v), adjacents(a) {}
  int vertex_number;
  std::set<int> adjacents;
};

class Graph {
 public:
  Graph(std::vector<Vertex> v) : v_(v) {}
  bool IsEulerWalkable();
  std::vector<Vertex> v_;
};

int main() {
  Graph g({Vertex(0, {1, 2, 3}), Vertex(1, {0, 2, 3}), Vertex(2, {0, 1, 3}),
           Vertex(3, {0, 1, 2})});
  std::cout << g.IsEulerWalkable() << std::endl;
}

Again, notice how we used uniform initialization to initialize the graph to the input table that represents it.

Having the above definition, we can rewrite

IsEulerWalkable()

as:

bool Graph::IsEulerWalkable() {
  // Create a table to hold degree of each vertex
  std::vector<int> degrees(v_.size());

  // Iterate vertices
  for (auto v : v_) {
    degrees[v.vertex_number] = v.adjacents.size();
  }

  // Iterate through degree table and count the number of odd ones

  int countOdds = 0;

  for (auto d : degrees) {
    if (d % 2 == 1) {
      countOdds++;
    }
  }
  return (countOdds == 0 || countOdds == 2);
}

Notice how we used STL's

size()

function to get the degree of each node:

Using adjacency list, the degree of each node is already available.

Method 3: Adjacency Matrix

Adjacency matrix is a two-dimensional matrix where the entry i,j is 1 if there is an edge between vertices i and j.

If the graph is undirected, the adjacency matrix is symmetrical: if entry i, j is 1, then entry j, i is also 1.

The adjacency matrix can be represented using a two-dimensional matrix:

class Graph {
 public:
  Graph(std::vector<std::vector<int>> &adjacency) : adjacency_(adjacency) {}
  bool IsEulerWalkable();
  void PrintGraph();
  std::vector<std::vector<int>> adjacency_;
};

int main() {
  std::vector<std::vector<int>> adjacency = {{0, 1, 1, 0, 0},
                                             {1, 0, 1, 1, 1},
                                             {1, 1, 0, 1, 0},
                                             {0, 1, 1, 0, 1},
                                             {0, 1, 0, 1, 0}};
  Graph g(adjacency);
  std::cout << "g.isEulerWalkable(): " << g.IsEulerWalkable() << std::endl;
  return 0;
}

Again notice how nicely the initialization of the adjacency matrix using uniform initialization matches the given table.

With the above class definition, we can rewrite

IsEulerWalkable()

as:

bool Graph::IsEulerWalkable() {
  // Create a table to hold degree of each vertex
  std::vector<int> degrees(adjacency_.size());

  // Iterate all edges
  for (int i = 0; i < adjacency_.size(); i++) {
    for (int j = 0; j < adjacency_.size(); j++) {
      if (adjacency_[i][j] == 1) {
        degrees[i]++;
      }
    }
  }

  int countOdds = 0;

  // Iterate through degree table and count the number of odd ones
  for (auto d : degrees) {
    if (d % 2 == 1) {
      countOdds++;
    }
  }
  return (countOdds == 0 || countOdds == 2);
}

Notice that to get the degree of each vertex, we have to iterate each row and add the number of

1's

The main concern with the adjacency matrix is its size. For a graph of

vertices, we need

n^2

entries. The advantage, however is that we can check if nodes i and j are adjacent just by checking entry i, j in

O(1)

time.

Comparison of the three methods

How do these methods compare? The following table summarizes the main differences:

The first method, direct translation, seems to have low memory size, but finding adjacents of a vertex takes

O(m)

, where m is the number of edges.

The adjacency list improves the runtime complexity for finding adjacents of a vertex. However, if we just want to check if nodes i, j are adjacent, the runtime is still not constant.

Adjacency matrix has the highest space, but due to the nature of vector's access time, you can quickly check to see if two nodes are adjacent in constant time.

Trade-off between std::vector, std::set, and std::list:

As I mentioned in the beginning there is some trade-off between using STL's vector, set, or list to represent the vertices and the edges.

Let's review some main differences:

std::set:

A set is automatically sorted
Insert/Delete/Find in set takes O(log n)

std::unordered_set:

An unordered set is not sorted
Insert/Delete/Find in set takes O(log 1)

std::vector:

A vector is not sorted

Insert/Delete/Find in set takes O(n)

std::list:

A list is not sorted

Find in set takes O(n)

Insert/Delete in set takes O(1)

Based on this, if you want to keep your edges or vertices sorted, you should probably go with a set. If you want a very fast search time, you should go with an unordered_set.

If find time is not that important, you can go with a list or a vector. But there is one more important reason that one might use a vector/list instead of set, which is representing multigraph:

A multigraph is similar to a graph, but it can have multiple edges between two nodes.

A set or unordered_set cannot have repeated items. For example, in the multigraph shown in the above picture, we would have two similar edges between 0 and 1:

(0,1)

and

(0,1)

. This cannot be represented using a set. Therefore for representing a multigraph, you may want to use std::vector, list, or a

multiset

Summary

We showed how you can represent a graph in C++ using one of the three methods: direct translation of the graph definition, adjacency list, and adjacency matrix. If you are preparing for technical job interviews, make sure you understand the difference and the pros and cons for each method.

Check my other video on Bazel & Visual Studio Code with GTest, Glog and Abseil: