Re: [boost] BGL limitations (?) and possible solutions

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2002-01-09 00:02:45

Hi,
David Abrahams wrote:

> Suppose I want to find the length of the shortest path from A to B in an
> arbitrary graph. I would normally use a breadth-first search, and store
> intermediate distances to each active vertex alongside its descriptor in the
> algorithm's Queue. AFAICT, the BGL approach makes me pay for a property map
> that can store the distances from A to X for any arbitrary vertex X. This
> could be fixed, however, by allowing users to store some other type in the
> buffer, and modifying some of the visitor interfaces to give them access to
> these objects. Does this make sense, or have I overlooked something obvious?

i haven't checked the BGL sources but graph search algorithms need a
flag indicating whether a node was visited. Of course, storing the
distince can be considered a flag: Actually, often search algorithms are
formulated to update a distance which is initially set to infinity.

Whether a property map actually stored anything with all nodes or just
with the nodes needing a different value than the default value, is,
however, an entirely different issue :-) What does not work general
graphs is to store nothing with nodes: This works with trees and DAGs
but as soon as there can be cycles it does not work.
-- 
<mailto:dietmar_kuehl_at_[hidden]> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>