So I have been taking a course on generic programming lately. It's pretty fun, and I have got a chance to refresh my knowledge in C++ as well as learn some new stuff. Boost graph library (BGL) is one of the cool things I came across recently. I have heard about it long time ago, although I don't remember why. However, I never really get a chance to try it out. Well, I got the chance finally.

Graph Data Structure

BGL supports two graph data structures: adjacency_list and adjacency_matrix, where adjacency_list graph is intended as a panacea for application involving graphs and adjacency_matrix is more about pushing the performance limit for small dense graphs.

These two data structures are pretty easy to use. For example, the use of adjacency_list can be as simple as

#include <boost/graph/adjacency_list.hpp>
using namespace boost;

using Graph = adjacency_list<listS, vecS>;

Graph g;

That's it. Three lines of code and you just create an adjacency list graph using list as the container for per-vertex adjacency relationship and vector for the outer container of all adjacency lists. By default, the graph is a directed graph, but you can make it undirected by specifying it with a template parameter

using Graph = adjacency_list<listS, vecS, undirectedS>;

In the examples below, we will stick to directed graphs though.

Graph Manipulation

Alright, I have to admit the empty graph created in the three lines of code is not that interesting. Let's add some vertices and edges to the graph to make it a bit more exciting.

auto v0 = add_vertex(g);
auto v1 = add_vertex(g);
auto v2 = add_vertex(g);

add_edge(v0, v1, g);
add_edge(v0, v2, g);
add_edge(v1, v2, g);

Very straightforward, right? Let's see if the graph is exactly what we want:

for(auto vp = vertices(g); vp.first != vp.second; ++vp.first) {
  cout << *vp.first << endl;
}

for(auto ep = edges(g); ep.first != ep.second; ++ep.first) {
  cout << source(*ep.first, g) << " -> " << target(*ep.first, g) << endl;
}

And the output looks like:

0
1
2
0 -> 1
0 -> 2
1 -> 2

That's right, we've made a (very simple) graph!

What about remove vertices or edges? Well, BGL has those for you already:

clear_vertex(v2, g);
remove_vertex(v2, g);

After this, the graph looks like:

0
1
0 -> 1

Graph Traversal

Traversing a graph with BGL is just a matter of writing a visitor class to perform the desired operations at several control points during the traversal. For example, if we want to print out the graph in DFS visiting order, we can define a visitor like:

class DFSVisitor : public default_dfs_visitor {
public:
  template <typename Vertex, typename Graph>
  void discover_vertex(Vertex u, const Graph& g) {
    cout << "discover vertex " <<  get(vertex_index, g, u) << endl;
  }
}

Then use it in the DFS algorithm:

depth_first_search(g, visitor(DFSVisitor()));

And we will have the nice output below:

discover vertex 0
discover vertex 1
discover vertex 2

How awesome is that!

Final Words

Well, this is really a 5 minutes primer for BGL. Anyway, these are pretty much everything one needs to get started with BGL. Have fun exploring the scary world! Just remember, whenever you need to handle a graph, BGL is always there for you ;)