Boost Graph v2

Hello all,

This is an updat of the boost graph tutorial you’ll found here

What changed ?

Ok so I’ll assumed you’ve read the last tutorial on boost graph I made or at least skimmed through it.

In the last version, I was using indexes to go through the Graph and vertex. Even worst, I was using indexes that were stored in a bundle property. So it was hard to update and prone to math error on the long term. Plus, most of the tutorial on boost graph use vecS as storage but iterators on graph are invalidated if you remove a vertex in a graph that uses vecS. Which makes it a pain to use with a dynamic graph.

All those reason pushed me into changing my whole graph structure and, while the previous tutorial is still useful as t help understanding key concept, I’m more going to talk about effective structure here.

All the choice I made came from the question I asked here on stackoverflow.

Ok got it, let’s go :

Here is the new graph structure.

typedef boost::adjacency_list<
    boost::listS, boost::listS, boost::undirectedS, 
    topologicalmap::Intersection_Graph,
    boost::edge_weight_t, 
    boost::no_property > Graph_boost;

typedef typename boost::property_map<Graph, boost::vertex_index_t>::type IndexMap;
typedef typename boost::graph_traits<Graph_boost>::vertex_iterator vertex_iter;
typedef typename boost::graph_traits<Graph_boost>::vertex_descriptor Vertex;
typedef typename boost::graph_traits<Graph_boost>::edge_descriptor Edge;

I chose to use listS as a replacement for vecS so I could use an iterator to dynamically change the graph. The only drawback is the impossibility to add a new Vertex using index number. Indeed listS doesn’t store vertex with a index property as vecS do (it may sound like a drawback at first, but I know think it’s a clever design that force you to design your program more cleverly and less prone to mistakes).

Sadly though, this index property is useful for algorithm such as Dijkstra. One clever solution to this is to

pass it in as a named parameter to all relevant algorithms. This includes constructing derived property maps that rely on a vertex_index (e.g. make_iterator_property_map)

As sehe said on the question on stackoverflow.

So now that we have changed the graph structure and that we have identify the problem that will arise because of the absence of index, let’s solve the problems.

Solve the absence of indexes :

Last version used index number to add a vertex and properties. This is the new best solution.

Vertex vertex_out = boost::add_vertex(_graph);
int num_vertice = boost::num_vertices(_graph);
_graph[vertex_out].type = type;
_graph[vertex_out].mat = m;
_graph[vertex_out].point = p;
_graph[vertex_out].index = num_vertice - 1;

The solution is the use Vertex instead of indexes. By passing those Vertex around, one can create a graph with edges and nodes. Every time you create a node, store the Vertex so you can get the node back using _graph[node].

Edge edg = boost::add_edge(node_1, node_2, _graph).first;

This is how you get edges of the graph. boost::add_edge return a pair and you need to grab the first element to get the actual edge descriptor. Getting the edge back is as easy as _graph[edg]

Final notes

  • The printing function with the iterator of the first tutorial is still working perfectly with this graph. But if you would want to remove a certain number of vertex based on a property, you can now do it by iterating through it, the same way you iterate through the graph to print it.

  • Not being able to add vertex by index may seem counter-intuitive but if your graph is bg or changing often, using vertex descriptor makes a lot more sense. Indeed, by removing graph vertexes index are modified and need to be modified for ALL VERTEXES which means mistakes can easily be made. As well, playing with numbers may seem like a easy task for us humans but we proved as a species that we actually suck big time at math (no offense 😉 ) and even if we think it’s easy, we are going to fuck up. And index error are a pain to track down. Thus playing around with the actual vertex means less confusion and pain in the debugging process <3.

Advertisements

One thought on “Boost Graph v2

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