Re: [Boost-users] bfs problem

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

Hi Adel,

On Tue, 11 Nov 2003, adel essafi wrote:
adel.e> I have a proble with bfs example of graph library.
adel.e> first I write this code
adel.e>  typedef adjacency_list < vecS, vecS, bidirectionalS > graph_t;
adel.e>   // Set up the vertex IDs and names
adel.e>   enum { r, s, t, u, v , N};
adel.e>
adel.e>   const char *name = "rstuv";
adel.e>   // Specify the edges in the graph
adel.e>   typedef std::pair < int, int >E;
adel.e>   E edge_array[] = {  E(0, 2), E(0,3) , E(3, 1), E(2, 3), E(3, 4)};
adel.e>   // Create the graph object
adel.e> and the result (order of visit ) was 0 -> 2-> 3 ->1 ->4 which true.
adel.e>
adel.e> Second I only modified the rank of an edge
adel.e>   E edge_array[] = {   E(0,3) ,E(0, 2), E(3, 1), E(2, 3), E(3, 4)};
adel.e>
adel.e> and I got a wrong order 0->3 ->2->1->4
adel.e> Normally , the edge rank don't have any influence on the
adel.e> result??????????????????????

I'm not sure what you mean by "edge rank"... the change above just
reorders the edges.

Also, what you mean by "wrong order". What is wrong about that order? To
me it looks like a void breadth-first traversal. To quote the docs on
the definition of breadth-first:

  A breadth-first traversal visits vertices that are closer to the source
  before visiting vertices that are further away. In this context
  ``distance'' is defined as the number of edges in the shortest path from
  the source vertex.

There are many possible valid BFS traversals of a given graph. The order
for visiting adjacent vertices is not specified. So from 0, either 2 or 3
is a fine choice for the next visit. The BGL implementation arbitrarily
chooses a particular order, which has to do with the order provided by the
out_edge_iterator implementation for the particular graph type.

Hope that helps,
Jeremy

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