Re: BGL: traversal algorithm for tree

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

Jeremy Siek wrote:
> 
> Hi Björn,
> 
> Here's a couple options:
> 
> 1. Use depth_first_search. Use the finish_vertex event point for your
>   postorder action, and use the tree_edge event point for the inorder
>   action. This will be a bit tricky, since you will not want
>   to trigger the inorder action on every call to tree_edge, only on
>   the second call to tree_edge per vertex.
> 
> 2. Use the traverse_tree function in boost/graph/tree_traits.hpp and
>   the graph_as_tree adaptor from boost/graph/graph_as_tree.hpp. Note
>   that these two files are undocumented and untested :( However,
>   if you find bugs I promise to fix them :)

It looks to me like the second suggestion would be the simplest and most
elegant solution. I have a couple of questions though, I can't get it to
quite work. I think I'm misunderstanding the template parameters to the
graph_as_tree class. What is ParentMap in this context?

Let's say I have the following graph type:

typedef boost::adjacency_list<boost::vecS, boost::vecS,
        boost::directedS, vertex_property, edge_property> tree;

How would I make a graph_as_tree object out of such a graph for use with
the traverse_tree function?

Thanks in advance,

Björn