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
Le 06/03/2012 21:56, Jeremiah Willcock a écrit : 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.