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
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@osl.iu.edu
C++ Booster (http://www.boost.org) office phone: (812) 855-3608
----------------------------------------------------------------------
