
Boost Users : 
Subject: [Boostusers] [Graph] On Dijkstra SSSP performance
From: Leo Hidd (leohidd_at_[hidden])
Date: 20120305 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net