Re: BGL: traversal algorithm for tree

From: Björn Lindberg (yg-boost-users_at_[hidden])
Date: 2002-07-22 06:15:05

Jeremy Siek wrote:
> 
> Hi Björn,
> 
> One more issue just came to mind.
> 
> Even though the graph is acyclic, we still need to consider the case when
> a vertex has more than one in-edge. Do we want the traverse_dag algorithm
> to visit that node just once, or multiple times? If just once, then we
> need to added coloring similar to DFS.
> 
> Or is what you really want a tree traversal (still formulated in terms of
> BGL graphs) and not a dag traversal? (a node in tree graph never has more
> than one in-edge). The only difference being that you would change the
> name to traverse_tree_graph.

Hi, Jeremy

I'm working exclusively with trees in my current work rather than DAGs.
I think the DAG traversal is probably a good idea for DAGs, but for
trees the colour is maybe an unnecessary overhead?

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

I have been thinking a bit about trees in the context of the BGL lately.
For my work, I frequently need to handle leaves differently from inner
nodes. I decided to implement this as a "vertex_type" internal property,
which is an enum of the types {ROOT, INNER, LEAF}. The simplest example
of this is using the traverse_tree_graph algoritm to print out a tree
with edge weights, and where only the leaf nodes have explicit names. An
example is: ((a, b, c), (d, e));. This necessitates that I have a
switch-case construct in the methods of the visitor used, selecting on
the node type. Do you think this is a sufficient approach? Maybe this
could be done with templates instead?

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
        {
            traverse_tree_graph(*i, g, visitor);
            visitor.on_edge(boost::edge(v, *i++, g).first, g);
            while (i != end)
            {
                visitor.inorder(v, g);
                traverse_tree_graph(*i, g, visitor);
                visitor.on_edge(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]