Re: BGL: traversal algorithm for tree

From: Björn Lindberg (yg-boost-users_at_[hidden])
Date: 2002-07-19 11:12:26

Jeremy Siek wrote:
> 
> yg-boo> Right now I'm thinking that I should just skip graph_as_tree, and
> yg-boo> reimplement the traverse_tree algorithm directly for graphs, so that I
> yg-boo> can access all of the graph functionality. Would this be best do you
> yg-boo> think, and have I made any oversights in the reasoning above?
> 
> The traverse_tree algorithm would be useful for DAGs. Perhaps a good
> name for it would be traverse_DAG.

I have implemented a traverse_dag algorithm now. I decided it was better
for me, since I needed some additional functionality beyond that of
traverse_tree(). I needed the visitor to be invoked on_edge(), and also
the inorder() function to be invoked "between" all recursive calls to
children.

----------
    template<typename DAG, typename DAGVisitor>
    void traverse_dag(typename
boost::graph_traits<DAG>::vertex_descriptor v,
                      DAG & g,
                      DAGVisitor visitor)
    {
        visitor.preorder(v, g);
        typename boost::graph_traits<DAG>::adjacency_iterator i, end;
        tie(i, end) = adjacent_vertices(v, g);
        if (i != end) // om ej löv
        {
            traverse_dag(*i, g, visitor);
            visitor.on_edge(boost::edge(v, *i++, g).first, g);
            while (i != end)
            {
                visitor.inorder(v, g);
                traverse_dag(*i, g, visitor);
                visitor.on_edge(boost::edge(v, *i++, g).first, g);
            }
        }
        else
            visitor.inorder(v, g);
        visitor.postorder(v, g);
    }
----------

What do you think?

BTW, unrelated issue: I'm going to need to keep an external property map
with some tables associated with every node. Could this be realised as a
vector where the vertex indices are indexing the vector of tables?

Björn