Re: [Boost-users] [BGL] Complexity time of algorithms

From: Jeremy Siek (jeremy.siek_at_[hidden])
Date: 2006-04-29 12:32:21

Hi Leandro,

On Apr 29, 2006, at 11:17 AM, Leandro Melo wrote:
> Hi.
> According to the site, most boost graph algorithms guarantee
> complexity bounds. For instance, DFS and BFS have complexity time O(V
> + E), Bellman-Ford has complexity O(VE), etc...
> As fair as I'm concerned (and from the knowledge I have) the
> complexity time bounds exposed on the graph web pages (like the ones I
> described above) are usually the 'best' theoretical values for them
> that can be found in the literature.
> However, something is still 'dark' for me. Most of this algorithms
> achieve this time bounds when implemented in a very specialized
> manner. Boost graph library is NOT like this, since we know it's a
> very nice generic library. Boost uses Property Maps for a lot of
> algorithms. My question is whether or not this property maps affect
> the complexity bounds.
> For example: In the original implementation of Bellman-Ford (which
> achieves O(VE)) weights are attached to edges. In boost's
> implementation, they're in the form of property maps. Right there,
> there's a change from a constant time operation (edge->get_weight, for
> example) to a logarithmic time operation (weight_map[edge], for
> example).
> I must say that I didn't take carefull look at the algorithms
> implementations, but it just seems weird to me that the same
> complexity bounds can still be achieved with those property maps.
> Can anyone help understand that?

Let me clear up some confusion about property maps... its
a fairly widespread confusion. The BGL algorithms takes as
input objects that must conform to the Property Map *interface*
(or *concept* in C++ generic programming lingo).
So the BGL algorithms do not require you to use a particular  
implementation
for the mapping... that's the whole point of having the property
map as a template parameter. So your assertion that property
maps are logarithmic is somewhat non-sensical. Some implementations
of property maps are constant-time, some are logarithmic, it all  
depends.

The time bounds on DFS, etc. assume that you are
using a property map that has constant time lookup, such as using
an iterator_property_map with a vector::iterator. This should
be made more explicit in the documentation.

Cheers,
Jeremy