Boost logo

Boost Users :

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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at