Boost logo

Boost Users :

Subject: Re: [Boost-users] [Graph] On Dijkstra SSSP performance
From: Leo Hidd (leohidd_at_[hidden])
Date: 2012-03-08 21:07:49

Le 06/03/2012 21:56, Jeremiah Willcock a écrit :
> On Tue, 6 Mar 2012, Leo Hidd wrote:
>> Sorry Jeremiah, my bad, the #4 is with vecS instead of listS, my bad
>> (bad copy-paste....), so the #3 plus optimizations.
> Could you please also try compressed_sparse_row_graph (you can just
> build one from your adjacency list for testing purposes)? You might
> also want to try dijkstra_shortest_paths_no_color_map, but I'm not
> sure that will help your performance.
for the dijkstra_shortest_paths_no_color_map, it accelerate things a
little. With config #4, for remind:
4- graph type: out-edge as vecS;
     predecessors: vertex_descriptor* p = new
     distances: double* d = new double[num_vertices(g)];
     NDEBUG defined (release configuration);
     with optimizations (option /Ox)
     - dijkstra_shortest_paths elapsed time: 5741ms
it gives 4800ms. If I use directedS instead of undirectedS on the graph
type (and I double the number of edges, to create both senses), it goes
down to 4420ms. If I use bidirectionalS (not doubling the edges),
results are weird (distances are wrong and the elapsed time is nonsense
too fast, like 57ms).

As for the compressed_sparse_row_graph, I can't get it working. I do the

     typedef std::pair<int, int> Edge;
     typedef property < edge_weight_t, double > Edge_Cost;
     typedef compressed_sparse_row_graph<directedS,
     no_property, // Vertex properties
                                                                             Edge_Cost // Edge properties
> csr_graph_t;
     typedef boost::graph_traits < csr_graph_t >::vertex_descriptor

     Edge* edge_list = new Edge
[2*NbOfEdges];//then I fill it
     Edge_Cost* edge_weight_list = new Edge_Cost[2*NbOfEdges];//then
I fill it
     csr_graph_t Graph_Boost (edges_are_unsorted, edge_list,
edge_list+2*NbOfEdges, edge_weight_list, NbOfVertices);
     vertex_descriptor* p = new
     double* d = new

but it gives me a compilation error (related to the use of the dijkstra
function) saying that none of the 6 overloads of boost::get, including:

boost::compressed_sparse_row_graph<Directed,VertexProperty,EdgeProperty> &)

could convert all the argument types. What am I doing wrong?
Additionally, how can I build a compressed_sparse_row_graph from an
adjacency_list, as you suggest?
>> As for the vector vs array new, yes, I know, but since it has some
>> overhead when accessing elements, it makes it slower (comparing #1 to
>> #2 makes it very explicit)
> Which compiler are you using? Do you have a small test program you
> can send, preferably with a synthetic data set (or a reference to one
> from the University of Florida sparse matrix collection or similar)?
> -- Jeremiah Willcock

I'm using the c++ compiler embedded with Microsoft Visual Studio 2008
Pro. I can provide a test case, but I'd like first get it working with

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