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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-07-15 09:42:15

Hi Björn,

On Mon, 15 Jul 2002, [iso-8859-1] Björn Lindberg wrote:
yg-boo> > 2. Use the traverse_tree function in boost/graph/tree_traits.hpp and
yg-boo> >   the graph_as_tree adaptor from boost/graph/graph_as_tree.hpp. Note
yg-boo> >   that these two files are undocumented and untested :( However,
yg-boo> >   if you find bugs I promise to fix them :)
yg-boo>
yg-boo> It looks to me like the second suggestion would be the simplest and most
yg-boo> elegant solution. I have a couple of questions though, I can't get it to
yg-boo> quite work. I think I'm misunderstanding the template parameters to the
yg-boo> graph_as_tree class. What is ParentMap in this context?
yg-boo>
yg-boo> Let's say I have the following graph type:
yg-boo>
yg-boo> typedef boost::adjacency_list<boost::vecS, boost::vecS,
yg-boo>         boost::directedS, vertex_property, edge_property> tree;
yg-boo>
yg-boo> How would I make a graph_as_tree object out of such a graph for use with
yg-boo> the traverse_tree function?

The ParentMap maps a vertex to its parent vertex in the tree. So, for
example, you could do the following:

  tree G;
  // fill G with vertices and edges ...

  typedef boost::adjacency_list_traits<boost::vecS, boost::vecS,
    boost::directedS>::vertex_descriptor vertex_t;
  std::vector<vertex_t> parent_vec(num_vertices(G));
  typedef iterator_property_map<std::vector<vertex_t>::iterator>
    parent_map_t;
  parent_map_t parent_map(parent_vec.begin());

  typedef graph_as_tree<tree, parent_map_t> real_tree_t;
  vertex_t root = *vertices(G).begin();
  real_tree_t T(G, root, parent_map);

The above call to the constructor for T fills in the parent map.

One question... do you need to access parents? If not, you could fabricate
a dummy property map of the right type and pass that in. Or you could hack
graph_as_tree and remove all the stuff about parents.

Cheers,
Jeremy

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