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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2000-10-19 10:56:18

Hi Krishna,

Instead of using -1 and 0, I suggest using the technique I mentioned
in my later email, that of initializing the predecessor of each vertex
(or just the source vertex) to itself.

It would be useful to avoid the extra bool to say whether a vertex is
invalid, but this would add
requirements to the vertex descriptor, which may be problematic to
implement for certain kinds of graphs. For example, adjacency_list
uses just an integer, or a void* for the vertex_descriptor, so
I can't change the meaning of the default constructor. To make that
change I would need to changed the vertex descriptor type... a nontrivial
change.

Cheers,

Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------

On Thu, 19 Oct 2000, Krishna Padmasola wrote:

> Jeremy,
> 
> Is it possible to make it work such that when VertexList=vecS,
> VertexDescriptor() returns -1, and when VertexList=listS,
> VertexDescriptor() returns 0?  That way, it works transparently for the
> user, and the default VertexDescriptor() will be an invalid descriptor,
> regardless of the type of VertexList selector.
> 
> This would be quite useful, since vertex descriptor comparisons are
> quite common in algorithms. Currently, I return a
> pair<VertexDescriptor,bool> from several of my functions, but just
> returning a VertexDescriptor would suffice, if one can check that it is
> invalid (currently I need the bool to tell me if it is valid or not).
> 
> Thanks in advance,
> Krishna.
> 
> jsiek_at_[hidden] wrote:
> > 
> > Hi John,
> > 
> > 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).
> > 
> > Cheers,
> > 
> > Jeremy
> > 
> > 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 ).
> >  > Thanks,
> >  > John Britton
> >  > Very Important Engineer++
> >  > Peak Audio Inc.
> >  > 1790 30th Street, Suite 414
> >  > Boulder, CO 80301
> >  > 303.449.9337 x102
> >  > johnb_at_[hidden]
> >  > http://www.peakaudio.com/
> >  >
> >  >
> >  >
> >  >
> >  >
> 
> 
> 
>