Boost logo

Boost :

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-01-14 12:21:50


On Tue, 8 Jan 2002, David Abrahams wrote:

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

What exactly is the problem you are trying to solve? Are you trying to
optimize space? Or are you tring to make the interface simpler?

Also, note that at the end of the algorithm, the Queue is empty, so if a
user wanted to know the distances after the algorithm is finished, they
would not have access to that information if it was stored on the Queue.

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

How about instead pass the color map into the visitor, and assign black to
vertices at the appropriate time?

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org) office phone: (812) 855-3608
----------------------------------------------------------------------


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk