Re: BGL: traversal algorithm for tree

Jeremy Siek wrote:

yg-boo> I've made the changes you requested, and include the file as an yg-boo> attachment to this post. I'm not sure I feel up to writing either yg-boo> documentation or tests yet. If I get the time, I could look at yg-boo> some of the existing tests to get an idea for how you are yg-boo> constructing them. In any case, I feel honoured to be able to make yg-boo> an -- albeit minor -- contribution to the BGL.

If you don't have the time, no big deal. I may get around to it :) How about we put this stuff in the boost sandbox for now. I'll go ahead and check this in. Also, do you have a sourceforge user name? If so I'll give you permissions to access the sandbox CVS.

I just created a Sourceforge account, username "blindberg". What is the sandbox?

yg-boo> example is: ((a, b, c), (d, e));. This necessitates that I have a yg-boo> switch-case construct in the methods of the visitor used, yg-boo> selecting on the node type. Do you think this is a sufficient yg-boo> approach? Maybe this could be done with templates instead?

Yeah, your approach is fine. I can't think of a way to use templates for this... best save that hammer for when we really need it ;)

I guess you're right here. Have you checked it in yet? I ask because I found a "bug" in the algorithm in that it might work differently from what one would expect. They it was originally written, it visited edges /after/ visiting the corresponding target node. This worked fine for myfrist purpose; to write out a tree with edge weights. However, apart from being named on_edge, which is a bit counter-intuitive, there is often a reason to want to visit an edge /before/ the target node. I decided to make both possible, so that a TreeGraphVisitor now has to implement both on_edge (before) as well as postedge (after). I'm attaching the new code to this post. Björn ---------- /* Copyright 2002 Björn Lindberg */ #ifndef BOOST_TRAVERSE_TREE_GRAPH_HPP #define BOOST_TRAVERSE_TREE_GRAPH_HPP #include namespace boost { template void traverse_tree_graph( typename boost::graph_traits<TreeGraph>::vertex_descriptor v, TreeGraph & g, TreeGraphVisitor visitor) { visitor.preorder(v, g); typename boost::graph_traits<TreeGraph>::adjacency_iterator i, end; tie(i, end) = adjacent_vertices(v, g); if (i != end) // if current node is not a leaf { visitor.on_edge(boost::edge(v, *i, g).first, g); traverse_tree_graph(*i, g, visitor); visitor.postedge(boost::edge(v, *i++, g).first, g); while (i != end) { visitor.inorder(v, g); visitor.on_edge(boost::edge(v, *i, g).first, g); traverse_tree_graph(*i, g, visitor); visitor.postedge(boost::edge(v, *i++, g).first, g); } } else visitor.inorder(v, g); visitor.postorder(v, g); } } #endif // BOOST_TRAVERSE_TREE_GRAPH_HPP [Non-text portions of this message have been removed]