[Boost-users] [Graph] On Dijkstra SSSP performance

Subject: [Boost-users] [Graph] On Dijkstra SSSP performance
From: Leo Hidd (leohidd_at_[hidden])
Date: 2012-03-05 11:50:30

Hello guys,

I'm newbie on Boost, but thanks to some examples I found over the net I 
could make it work. Now I have a question on the performance of the 
dijkstra_shortest_paths function. The kind of graph I have is actually a 
3D surface mesh, with each vertex being a node and each edge being an 
edge of the graph. So my graph is undirected, the number of edges is 
approximately 3 times the number of vertices (I typically have around 4 
millions of vertices), the degree of the vertices is not constant, it 
varies between 3 and 12 (but 90% of the vertices have 5 or 6 neighbors) 
and the weight of the edges are the (3D Euclidean) distances between the 
adjacent vertices. As for the Boost lib, so far I'm using the classic 
adjacency_list<listS, vecS, undirectedS, no_property, < 
boost::edge_weight_t, Scalar > > graph_t type, with the 
dijkstra_shortest_paths function. But I feel the performance is very low 
compared to my implementation of Dijkstra algorithm. Dijkstra algorithm 
is very simple, so my implementation is a simple transcription of the 
text book in C language (I'm using Microsoft Visual Studio 2008). The 
data structure I'm using is a classic binary tree

typedef struct tree_el {
    int idx;
    int source_idx;
    double dist;
    tree_el * right, * left;
} node;

and the functions I've implemented are insert (inserts a node with the 
smallest dist as the left most element or, in case of equality, it put 
the node with smallest idx as the left most element), remove_smallest 
(return the left most node and delete it from the tree) and remove_node 
(finds and return a given node and delete it from tree). The remove_node 
I use combined with insert whenever a given node has it's dist updated 
(in case new dist is smallest than the current one), so I remove the 
node, create a new one with the new dist (but same idx) and insert it 
into the tree (so that it will be always sorted). Well, since this is a 
real simple scholar case and that the performance is around 4 times 
faster than the dijkstra_shortest_paths function, which I call like this:

std::vector<vertex_descriptor> p(num_vertices(g));
std::vector<Scalar> d(num_vertices(g));
vertex_descriptor s = vertex(A, g);
dijkstra_shortest_paths (g, s,
        predecessor_map(make_iterator_property_map(p.begin(), 
get(vertex_index, g))).
        distance_map(make_iterator_property_map(d.begin(), 
get(vertex_index, g))));

I'm here to ask you how to make a better use of Boost in order to have 
performance at least in pair with what I have so far. I'm not concerned 
by the build time of the graph (add nodes/edges) since I do it only once 
and it remains the same all over my runtime. I'm only concerned by the 
SSSP itself, which I call thousands of times with different sources (I 
actually do multi source shortest path search) (all pairs is not a 
solution to me since I use way less sources than the total of nodes I 
have, and, for a graph with as much nodes as I have, I can't hold in 
memory all these distances). It seems to massively use STL containers 
(like vectors and lists) which maybe be the reason why it runs slower, 
but I'm not sure. Is there a way to use other graph type so that it can 
run faster?

Thank you for your attention,

leo