Re: [Boost-Users] Re: BGL and reversing / moving edges

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-07-26 14:14:51

Hi Josh,

On Fri, 26 Jul 2002, joshrose wrote:
joshro> One quick followup, though -- if I do follow the approach of an
joshro> external property map keyed by edge id, won't I wind up having to
joshro> do a potentially expensive lookup on the edge id every time I need
joshro> to access properties keyed by edges?  The reason I was going to

No, the internal property maps supplied by adjacency_list all have
constant time lookup. They are typically implemented by a pointer
dereference and struct access, or via an array lookup.

joshro> shortest paths algo extended to multigraphs.  (If I understand
joshro> correctly, the standard Dijk algo in BGL doesn't handle
joshro> mutigraphs, since it records predecessors as vertices, rather than
joshro> edges.)

Yes, I'm afraid none of the BGL algorithms handle multigraphs. This would
be a great direction to extend the BGL.

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: [phone]
----------------------------------------------------------------------