Re: BGL: traversal algorithm for tree

From: Björn Lindberg (yg-boost-users_at_[hidden])
Date: 2002-07-25 14:04:14

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 <boost/graph/graph_traits.hpp>

namespace boost
{
    
    template<typename TreeGraph, typename TreeGraphVisitor>
    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]