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