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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-07-12 10:44:40

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 :)

Regards,
Jeremy

On Fri, 12 Jul 2002, [iso-8859-1] Björn Lindberg wrote:
yg-boo> I have implemented a rooted tree structure as a BGL graph. I need to be
yg-boo> able to traverse the tree from root to leaves, while doing something at
yg-boo> each vertex. I need to be able to do this as inorder and postorder
yg-boo> traversal. My question is if it's possible to do this with any of the
yg-boo> existing algorithms in BGL. My current thinking is to implement a
yg-boo> function traversal( ... ), but if there already exists an alternative, I
yg-boo> would prefer to use it.
yg-boo>
yg-boo>
yg-boo> Björn

----------------------------------------------------------------------
 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]
----------------------------------------------------------------------