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 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 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.