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

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 
vertex_descriptor[num_vertices(g)];
     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 
following:

     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 
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 
vertex_descriptor[num_vertices(Graph_Boost)];
     double* d                                      = new 
Scalar[num_vertices(Graph_Boost)];
     dijkstra_shortest_paths_no_color_map(Graph_Boost,
                                                                         
   0,
                                                                         
   predecessor_map(p).
                                                                           distance_map(d));

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::detail::csr_edge_index_map<Vertex,EdgeIndex> 
boost::get<boost::directedS,boost::no_property,Edge_Cost,boost::no_property,size_t,Vertex>(boost::edge_index_t,const 
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 
compressed_sparse_row_graph.