Re: [Boost-Users] Re: BGL: traversal algorithm for tree

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-07-19 11:50:38

Hi Björn,

One more issue just came to mind.

Even though the graph is acyclic, we still need to consider the case when
a vertex has more than one in-edge. Do we want the traverse_dag algorithm
to visit that node just once, or multiple times? If just once, then we
need to added coloring similar to DFS.

Or is what you really want a tree traversal (still formulated in terms of
BGL graphs) and not a dag traversal? (a node in tree graph never has more
than one in-edge). The only difference being that you would change the
name to traverse_tree_graph.

Cheers,
Jeremy

On Fri, 19 Jul 2002, [iso-8859-1] Björn Lindberg wrote:
yg-boo> ----------
yg-boo>     template<typename DAG, typename DAGVisitor>
yg-boo>     void traverse_dag(typename
yg-boo> boost::graph_traits<DAG>::vertex_descriptor v,
yg-boo> 		      DAG & g,
yg-boo> 		      DAGVisitor visitor)
yg-boo>     {
yg-boo> 	visitor.preorder(v, g);
yg-boo> 	typename boost::graph_traits<DAG>::adjacency_iterator i, end;
yg-boo> 	tie(i, end) = adjacent_vertices(v, g);
yg-boo> 	if (i != end) // om ej löv
yg-boo> 	{
yg-boo> 	    traverse_dag(*i, g, visitor);
yg-boo> 	    visitor.on_edge(boost::edge(v, *i++, g).first, g);
yg-boo> 	    while (i != end)
yg-boo> 	    {
yg-boo> 		visitor.inorder(v, g);
yg-boo> 		traverse_dag(*i, g, visitor);
yg-boo> 		visitor.on_edge(boost::edge(v, *i++, g).first, g);
yg-boo> 	    }
yg-boo> 	}
yg-boo> 	else
yg-boo> 	    visitor.inorder(v, g);
yg-boo> 	visitor.postorder(v, g);
yg-boo>     }
yg-boo> ----------

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