Re: [Boost-users] bfs problem

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2003-11-11 09:15:07

On Tue, 11 Nov 2003, Jeremy Siek wrote:
jsiek>
jsiek> I'm not sure what you mean by "edge rank"... the change above just
jsiek> reorders the edges.
jsiek>
jsiek> Also, what you mean by "wrong order". What is wrong about that order? To
jsiek> me it looks like a void breadth-first traversal. To quote the docs on
                          ^^^^

should be "valid"

jsiek> the definition of breadth-first:
jsiek>
jsiek>   A breadth-first traversal visits vertices that are closer to the source
jsiek>   before visiting vertices that are further away. In this context
jsiek>   ``distance'' is defined as the number of edges in the shortest path from
jsiek>   the source vertex.
jsiek>
jsiek> There are many possible valid BFS traversals of a given graph. The order
jsiek> for visiting adjacent vertices is not specified. So from 0, either 2 or 3
jsiek> is a fine choice for the next visit. The BGL implementation arbitrarily
jsiek> chooses a particular order, which has to do with the order provided by the
jsiek> out_edge_iterator implementation for the particular graph type.

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