Hi David. I understand that Boost's architecture (taking into account the template stuff, the fact all algorithms are implemented as functions and the layering of the algorithms implementations) favors a nice performance of the library. However, I can't get how algorithms can be implemented in a manner to be fast with a wide variety of graph structures. To make my point clear, I mean that a DFS is always a DFS, the algorithm is the same. So, how could one implement a 'optimized' DFS for a wide variety a graph structures. I might have not understood your post correctly. If this is the case, can you clearify this doubt. Thanks.
You should probably know that although graph construction should be fast with Boost, most of the attention to optimization went into the algorithms, and on making them as fast as possible on a wide variety of graph structures.
-- Leandro Terra C. Melo