Boost Graph

Hello all,

EDIT 2 : updated version. You should still read (even quickly) this tutorial first as it covers important information used in the second tutorial. But don’t implement anything from here.

EDIT : To whoever is reading this right, I am going to re-write this tutorial soonish (I hope). Everything below is perfectly valid BUT after playing around with my code I realized that it’s a very sub optimal way of using the boost graph library. The reason for that is my usage of indexes I update manually. I wouldn’t recommend using numerical index but directly using Vertex is more clever. Especially, it works only because I use vecS for the storing. But vecS doesn’t allow iterators to suppress vertex which makes this graph annoying on the long run. And indexes to add Vertex don’t work “out of the box” with listS as storage.

So stay tuned for the next tutorial on boost graph 🙂

How to use Boost Graph

I wanted to put on a little tutorial on how to use boost graph in a program. I know the documentation is awesome but I still had to dig before fully grasping how it works so I though another tutorial wouldn’t be such a bad thing.

So, this is how you declare a graph :

#include "boost/graph/adjacency_list.hpp"

typedef boost::adjacency_list<
boost::vecS, boost::vecS, boost::undirectedS,
topologicalmap::Intersection_Graph ,
boost::edge_weight_t,
boost::no_property > Graph;

The adjacent list takes 6 template :

  • Storage of vertices : vector or other. Here I declared it to be a vector
  • Storage of edges : same as for the vertices.
  • Type of edges : directed or not
  • Vertice’s data : you may want to store data at each vertices. Here I had a custom structure named topological_map::Intersection_Graph
  • Edge’s data : same you may want to add data to edges. Here for example, I’m adding a weight to each of them. boost::edge_weight_t is already a data structure defined in boost Graph.
  • Map properties : Property associated with the whole graph. Here I add nothing at all.

Using bundle properties, you can literally add whatever you want to the graph vertices, edges or map property. My custom struct is as such :

struct Intersection_Graph{
    std::string type;
    cv::Mat mat;
    cv::Point2i point;
    int index;
};

When declaring a graph, on can either declare it with a certain number of vertices or without any and adding them dynamically. I found this to be somewhat unclear in the documentation. This is perfectly valid :

Graph _graph;
boost::add_vertex(_graph);
//Handy function to know the number of vertices
int num_vertice = boost::num_vertices(_graph);
_graph[num_vertice - 1].type = type;
_graph[num_vertice - 1].mat = m;
_graph[num_vertice - 1].point = p;
_graph[num_vertice - 1].index = num_vertice - 1;

But this would be as well :

Graph _graph(9);
for ( size_t i = 0 ; i < boost::num_vertices(_graph) ; i++){
    _graph[i].type = type;
    _graph[i].mat = m;
    _graph[i].point = p;
    _graph[i].index = i;
}

However, this :

Graph _graph(9);
boost::add_vertex(_graph);

Create a 10th vertex and leave all the last ones “empty”. So take care not to mix the two.

To add an edge is as simple as :

boost::add_edge(start, end, _graph);

Where start and end are the number of the two vertices to connect.

To finish this tutorial, here is a handy function to print a graph :

//first is beginning, second is "past the end"
std::pair<vertex_iter, vertex_iter> vp;
//vertices access all the vertix
for (vp = boost::vertices(_graph); vp.first != vp.second; ++vp.first) {
    Vertex v = *vp.first;
    std::cout << _graph[v].type << " with index " << _graph[v].index;

    typedef boost::graph_traits<Graph> GraphTraits;
    typename boost::property_map<Graph, boost::vertex_index_t>::type 
        index = get(boost::vertex_index, _graph);

    std::cout << " edges: ";
    typename GraphTraits::out_edge_iterator out_i, out_end;
    typename GraphTraits::edge_descriptor e;
    for (boost::tie(out_i, out_end) = boost::out_edges(v, _graph); 
        out_i != out_end; ++out_i) {
        e = *out_i;
        Vertex src = boost::source(e, _graph), targ = boost::target(e, _graph);
        std::cout << "(" << index[src] << "," 
                << index[targ] << ") ";
    }
    std::cout << std::endl;   
}
std::cout << std::endl;

Let’s cut the code.

//first is beginning, second is "past the end"
std::pair<vertex_iter, vertex_iter> vp;
//vertices access all the vertix
for (vp = boost::vertices(_graph); vp.first != vp.second; ++vp.first) {
    Vertex v = *vp.first;
    std::cout << _graph[v].type << " with index " << _graph[v].index;

Create an iterator on the vertexes. vp.first point to the first element of the graph and vp.second to something after the graph.
We iterate through it all and print the wanted information.

typedef boost::graph_traits<Graph> GraphTraits;
typename boost::property_map<Graph, boost::vertex_index_t>::type 
    index = get(boost::vertex_index, _graph);

std::cout << " edges: ";
typename GraphTraits::out_edge_iterator out_i, out_end;
typename GraphTraits::edge_descriptor e;
for (boost::tie(out_i, out_end) = boost::out_edges(v, _graph); 
    out_i != out_end; ++out_i) {

We create an index element on the graph. This will help us later in the print by given us the number (or index) of a given vertice.

We create an iterator on edges. We use the function boost::tie to get the first and last of all out edges. We then iterate. Note that we only need to do the out-edges because I declare an undirected graph but you would have to do in-edges as well if it is directed. The procedure is essentially the same

e = *out_i;
Vertex src = boost::source(e, _graph), targ = boost::target(e, _graph);
std::cout << "(" << index[src] << "," 
        << index[targ] << ") ";

Using the index of the graph, we obtain the index of the source vertice and the target vertice of every edge.

 

Advertisements

One thought on “Boost Graph

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s