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