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

On Mon, 5 Mar 2012, Leo Hidd wrote:

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 > 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

Try using vecS as the out-edge container in your adjacency_list, and are you compiling with optimization on and NDEBUG defined?

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 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?

The only thing I'd change for now is the out-edge container type (see above) and make sure full compiler optimization is on and assertions are disabled. See if those things change your performance results. -- Jeremiah Willcock