Pages

Graph by adjacency list

If you need to work with graphs in your C++11 code, you'd usually rely on someone else's job, like the Boost Graph Library, friendly known as BGL. Sometimes it happens you simply can't, and you have to work it out by yourself. Here I am writing a trivial Graph class that would let me to store an undirected unweighted graph in a compact form.

I have a simple graph as the one showed in the picture. Each vertex is represented by an unsigned integer starting from zero, that helps me to keep the code even simpler. Edges have no weight nor direction, so we can move from vertex 0 to vertex 5 and vice versa, and we are not interested in the cost of moving from one vertex to another one. We only want to know if we can actually go from here to there.

The two common ways to represent a graph differ by using a matrix or a list to store the adjacency of each vertex. As often happens, you should know the actual problem you are tackling to decide which data structure would suit you better. Still, list is usually the primary suspect.

In this first implementation, my class Graph provides only a constructor to set it up and a print method to show what it has in its belly. The main focus here is about showing how the data is stored in it.
using Vertex = unsigned int; // 1
using Edge = std::pair<Vertex, Vertex>; // 2
using Edges = std::vector<Edge>; // 3
using Vertices = std::forward_list<Vertex>; // 4

class Graph
{
public:
    std::vector<Vertices> vertices_; // 5

    Graph(int nv, Edges edges) : vertices_(nv) // 6
    {
        std::for_each(edges.begin(), edges.end(), [this](const Edge& edge) // 7
        {
            if(edge.first < vertices_.size() && edge.second < vertices_.size()) // 8
            {
                vertices_[edge.first].push_front(edge.second); // 9
                vertices_[edge.second].push_front(edge.first);
            }
        });
    }

    void print() // 10
    {
        for(Vertex i = 0; i < vertices_.size(); ++i)
        {
            std::cout << i << ": ";
            std::copy(vertices_[i].begin(), vertices_[i].end(), std::ostream_iterator<Vertex>(std::cout, " "));
            std::cout << std::endl;
        }
    }
};
1. Each vertex is represented by an unsigned integer, starting from zero.
2. An edge is defined by the two vertices delimiting it.
3. I want to pass all the edges in my graph to the class constructor. This is the collection I am going to use for this task.
4. Any vertex in the graph has an associated collection of vertices, all the ones to which it is connected. The cheap C++11 forward_list suffices for this job.
5. A graph is a collection of Vertices. Each element in the vector is an actual vertex of the graph and the associated Vertices keeps track of all the connected vertices.
6. The Graph constructor requires as input the number of vertices in the graph, and all the edges on it. The data member vertices_ is initialized as a collection of empty Vertices.
7. Loop on all the passed edges to associate each vertex in the graph to its connections.
8. A real piece of code should have more effective error handling than this. Here I just discard any wrong edge. It would make sense let the user know that something went wrong.
9. Being the graph undirected, any edge creates two relations.
10. Utility method, just to show that anything worked as expected (hopefully).

Here is how my Graph class is used:
Edges edges { { 0, 1 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 4 }, { 2, 3 }, { 3, 4 } };
Graph graph(6, edges);
graph.print();
The expected output:
0: 5 4 1 
1: 4 2 0 
2: 3 1 
3: 4 2 
4: 3 1 0 
5: 0 

4 comments:

  1. BGL can also do this of course, so why reinvent the wheel?

    ReplyDelete
    Replies
    1. 1. Quoting the post:
      "If you need to work with graphs [..] you'd usually rely on [...] BGL. **Sometimes [...] you simply can't** [...]"
      2. Learning purposes.

      Delete
    2. I couldn't answer better than you, Anonymous II. Thanks for clarifying the point.

      And thank you Anonymous I for asking.

      Delete
  2. BGL is a complex and difficult to use behemoth, documentation is poor and each version bump seems to introduce new and exotic compile errors into existing code. I'm not a fan.

    ReplyDelete