Boost logo

Boost :

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.


> 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

> 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.


 Jeremy Siek
 Ph.D. Student, Indiana Univ. B'ton email: jsiek_at_[hidden]
 C++ Booster ( office phone: (812) 855-3608

Boost list run by bdawes at, gregod at, cpdaniel at, john at