[Boost-users] [BGL]: Highest performance graph-type available?

From: Greg Link (link_at_[hidden])
Date: 2006-05-10 23:23:45

I'm using BGL for the johnson_all_pairs_shortest_path algorithm, and  
spending about 98% of my runtime in that algorithm. Breaking it down,  
the BFS_visit itself is consuming some 85% of my total runtime.  
Hence, any and every improvement I can get in my BGL performance will  
make my app much much snappier.

Currently, my graph type is a

adjacency_list <vecS, vecS, undirectedS, no_property, property  
<edge_weight_t, double> >

and I'm wondering if that's the best choice. My graph has (E=2*V),  
and all nodes are of constant degree, with 4 edges incident on them.  
V is usually in the range of 150-500.

Would one of the other types (such as listS) perhaps be faster, and  
still work? I know some BGL algorithms require certain graph storage  
types, so I'm hesitant to just start poking around and trying random  
things. That, and other than "listS", I don't know of any other types  
of graph, as I'm quite new to both the BGL and boost in general.

Any thoughts on what might make things faster? Additionally, are  
there any compiler flags I should consider other than the 'vanilla'  
ones? (-O3). I'm using GCC 4.0.1 currently, if it matters.

Thanks for the great library, and such a friendly list,
        Greg Link