# Boost Users :

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

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> // Set up the vertex IDs and names
adel.e> enum { r, s, t, u, v , N};
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> 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> and I got a wrong order 0->3 ->2->1->4
adel.e> Normally , the edge rank don't have any influence on the

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

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: (812) 855-3608
----------------------------------------------------------------------