Re: [Boost-users] [BGL] Boost poor performance (against LEDA)

From: David Abrahams (dave_at_[hidden])
Date: 2006-10-02 12:51:09

"Leandro Melo" <ltcmelo_at_[hidden]> writes:

> 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