Jeremy Siek wrote:
yg-boo> Right now I'm thinking that I should just skip graph_as_tree, and yg-boo> reimplement the traverse_tree algorithm directly for graphs, so that I yg-boo> can access all of the graph functionality. Would this be best do you yg-boo> think, and have I made any oversights in the reasoning above?
The traverse_tree algorithm would be useful for DAGs. Perhaps a good name for it would be traverse_DAG.
I have implemented a traverse_dag algorithm now. I decided it was better for me, since I needed some additional functionality beyond that of traverse_tree(). I needed the visitor to be invoked on_edge(), and also the inorder() function to be invoked "between" all recursive calls to children. ---------- template<typename DAG, typename DAGVisitor> void traverse_dag(typename boost::graph_traits<DAG>::vertex_descriptor v, DAG & g, DAGVisitor visitor) { visitor.preorder(v, g); typename boost::graph_traits<DAG>::adjacency_iterator i, end; tie(i, end) = adjacent_vertices(v, g); if (i != end) // om ej löv { traverse_dag(*i, g, visitor); visitor.on_edge(boost::edge(v, *i++, g).first, g); while (i != end) { visitor.inorder(v, g); traverse_dag(*i, g, visitor); visitor.on_edge(boost::edge(v, *i++, g).first, g); } } else visitor.inorder(v, g); visitor.postorder(v, g); } ---------- What do you think? BTW, unrelated issue: I'm going to need to keep an external property map with some tables associated with every node. Could this be realised as a vector where the vertex indices are indexing the vector of tables? Björn