On Tue, 6 Mar 2012, Leo Hidd wrote:
sry, I could not make a reply in the post through http://thread.gmane.org/gmane.comp.lib.boost.user/73084/focus=73086 If i use the "Follow up" action and post it I have this message: "You seem to be top-posting. Don't do that." That's why I'm doing this now. Hope it works. Anyways...
thx Jeremiah for the inputs. I tested what you said for a mesh of 3 million vertices (then, 9 million edges), and here is a summary of the different configs:
1- graph type: out-edge as listS; predecessors: vector
p(num_vertices(g)); distances: vector<double> d(num_vertices(g)); NDEBUG defined (release configuration); no optimizations: - dijkstra_shortest_paths elapsed time: 11970ms 2- graph type: out-edge as listS; predecessors: vertex_descriptor* p = new vertex_descriptor[num_vertices(g)]; distances: double* d = new double[num_vertices(g)]; NDEBUG defined (release configuration); no optimizations: - dijkstra_shortest_paths elapsed time: 9446ms
3- 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); no optimizations: - dijkstra_shortest_paths elapsed time: 8436ms
4- graph type: out-edge as listS; 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
5- my implementation without optimizations takes 3289ms and with optimizations takes 2860ms.
Could you please try #3 with optimizations? Function inlining, in particular, is likely to be important.
Using predecessors and distances storage as simple arrays instead of std::vector have a real gain (although optimization does even more). Is it possible to use arrays (maybe array of arrays) instead of vecS for OutEdgeList and VertexList? Or put arrays inside some kind of class with functions allowing compatibility/interfacing with the Dijkstra algorithm (like insert, sort, remove, or whatever it needs)? Since the Dijkstra algorithm does more read access to the edge list than the distance or path arrays, it could really accelerate things.
That is basically what an std::vector is -- a dynamically-allocated array; when its size isn't being changed, it basically acts like a normal new[]-created array. -- Jeremiah Willcock