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-11 23:34:11

On Mon, 12 Mar 2012, Leo Hidd wrote:

> Le 09/03/2012 03:07, Leo Hidd a écrit :
>> 
>> 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 anyone give me a hand on this here? Do any of you have an working 
> example using compressed_sparse_row_graph graph type for SSSP with 
> dijkstra_shortest_paths, for example?

It looks like you may not be passing your weight map into 
dijkstra_shortest_paths.  If that isn't the problem, what are the exact 
types the compiler says that you are trying to pass to boost::get?  Where 
is dijkstra_shortest_paths_no_color_map is it failing (which line, and 
which instantiation stack)?

-- Jeremiah Willcock