"Leandro Melo"
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.
That's the magic of generic programming.
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.
You create abstractions ("concepts") that handle all the various structures without adding any performance penalty. For example, all of the algorithms use property maps to access properties associated with edges and vertices. That allows them to run fast whether the properties are stored internally or externally. I suggest reading the BGL book; it has a pretty good introduction to generic programming. -- Dave Abrahams Boost Consulting www.boost-consulting.com