From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2002-01-09 00:02:45
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/>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk