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