Re: [Boost-Users] Re: BGL: traversal algorithm for tree

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-07-25 11:11:43

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_at_[hidden]>
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_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------