[boost] Re: BGL - how to find end of predecessor chain?

From: jsiek_at_[hidden]
Date: 2000-10-17 14:39:43

Thinking about this some more, an even better (and more generic) way
to mark the end of the predecessor chain is to initialize the source
vertex's predecessor to itself and leave the rest uninitialized. Or,
in the case of depth-first search (which creates a forest), intialize
the predecessor of each vertex to itself. Thereby a root node is
distinguished by being its own parent.

I've added this hint to the docs for predecessor_recorder and I've
updated the dijkstra.cpp example.

Cheers,

Jeremy

Daryle Walker writes:
 > on 10/15/00 1:19 PM, jsiek_at_[hidden] wrote:
 > 
 > > In the case when using an adjacency_list with VertexList=vecS, you could
 > > initialize the predecessor array to -1.
 > > 
 > > In the case when using an adjacency_list with VertexList=listS, you could
 > > initialize the predecessor array to 0 (null pointer).
 > 
 > I haven't used the graphing library, but I wonder if this
 > invalid-predecessor tip is documented anywhere?  It could also be a
 > compile-time traits constant to make generic graph processing easier.
 > 
 > > John Britton writes:
 > >> After performing a BFS which fills in a vector of Vertex predecessors, how do
 > >> I determine whether a given Vertex has a valid predecessor? Comparing against
 > >> a default constructed Vertex doesn't seem to work since the default
 > >> constructed Vertex apparently has an index of 0, and thus cannot be
 > >> differentiated from vertex( 0, G ).
 > 
 > -- 
 > 
 > 
 > 
 > 
 > 
 >