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

Subject: Re: [Boost-users] [Graph] On Dijkstra SSSP performance
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-03-05 12:13:31

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

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

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