On Mon, 22 Jul 2002, [iso-8859-1] Bj�rn Lindberg wrote: yg-boo> Hi, Jeremy yg-boo> yg-boo> I'm working exclusively with trees in my current work rather than yg-boo> DAGs. I think the DAG traversal is probably a good idea for DAGs, yg-boo> but for trees the colour is maybe an unnecessary overhead? Yep, sounds like changing the name, and leaving out the coloring is the right approach. 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. yg-boo> I have been thinking a bit about trees in the context of the BGL yg-boo> lately. For my work, I frequently need to handle leaves yg-boo> differently from inner nodes. I decided to implement this as a yg-boo> "vertex_type" internal property, which is an enum of the types yg-boo> {ROOT, INNER, LEAF}. The simplest example of this is using the yg-boo> traverse_tree_graph algoritm to print out a tree with edge yg-boo> weights, and where only the leaf nodes have explicit names. An 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 ;) yg-boo> yg-boo> Bj�rn yg-boo> ---------- yg-boo> yg-boo> /* Copyright 2002 Bj�rn Lindberg yg-boo> */ yg-boo> #ifndef BOOST_TRAVERSE_TREE_GRAPH_HPP yg-boo> #define BOOST_TRAVERSE_TREE_GRAPH_HPP yg-boo> yg-boo> #include <boost/graph/graph_traits.hpp> yg-boo> yg-boo> yg-boo> namespace boost yg-boo> { yg-boo> yg-boo> template<typename TreeGraph, typename TreeGraphVisitor> yg-boo> void traverse_tree_graph(typename boost::graph_traits<TreeGraph>::vertex_descriptor v, yg-boo> TreeGraph & g, yg-boo> TreeGraphVisitor visitor) yg-boo> { yg-boo> visitor.preorder(v, g); yg-boo> typename boost::graph_traits<TreeGraph>::adjacency_iterator i, end; yg-boo> tie(i, end) = adjacent_vertices(v, g); yg-boo> if (i != end) // if current node is not a leaf yg-boo> { yg-boo> traverse_tree_graph(*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_tree_graph(*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> yg-boo> } yg-boo> yg-boo> #endif // BOOST_TRAVERSE_TREE_GRAPH_HPP yg-boo> yg-boo> yg-boo> [Non-text portions of this message have been removed] yg-boo> yg-boo> yg-boo> yg-boo> Info: <http://www.boost.org> yg-boo> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> yg-boo> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com> yg-boo> yg-boo> yg-boo> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 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 ----------------------------------------------------------------------