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-06 10:56:34

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

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.

thx again, leo