Re: [boost] BGL: dijkstra questions

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-01-15 21:11:37

On Tue, 15 Jan 2002, David Abrahams wrote:
> Okay, I can see that I was missing at least a few things: you want to know
> if the vertex is gray, if you're going to avoid duplicate vertices in the
> Queue, since E can potentially be much larger than V in interesting graphs.

Right.

> Anyway, since the user has to supply you with an IndexMap so that you can
> translate vertices to queue positions, you don't need a ternary color map.
> In fact, you don't need a separate color map at all. Just reserve two values
> (say, -1 and 0) in the IndexMap to indicate the white and black nodes.

Currently the user-supplied IndexMap is read-only, and for graph types
that use integers for the vertex_descriptor type, the IndexMap is just an
identity function on the key. I think it might be better to stick with the
color map abstraction for this (or the new one that allows generational
coloring).

> Reducing the size of the queue just makes the case stronger for keeping
> distances and predecessors in the queue, at least if the user doesn't want
> to make a record of them.

Yes, I like the idea of storing the distances and predecessors in the
queue. I'll do a prototype implementation if you're interested.

Cheers,
Jeremy

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