BGL limitations (?) and possible solutions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-08 20:40:42

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?

Secondly, (and I know we've discussed this in the past), what about
terminating the search as soon as the path is found? I guess I could give
the visitor access to the Queue, and flush it when I've found what I'm
looking for, but it will still go on to explore the rest of the edges on the
current node. Is there a reason not to give visitors a return value and
check that? Won't inlined visitors that always return false cause the check
to be optimized away?

Thanks for your attention,
Dave

===================================================
  David Abrahams, C++ library designer for hire
 resume: http://users.rcn.com/abrahams/resume.html

        C++ Booster (http://www.boost.org)
          email: david.abrahams_at_[hidden]
===================================================