Boost logo

Boost Users :

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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at