Re: BGL: traversal algorithm for tree

From: Björn Lindberg (yg-boost-users_at_[hidden])
Date: 2002-07-16 10:09:22

Jeremy Siek wrote:
> 
> 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.

Using the above I get a compile error:

-----
phylo_tree.cpp: In function `std::string
   phylo::write_newicktree(phylo::tree&)':
phylo_tree.cpp:63: wrong number of template arguments (1, should be 4)
/home/compbio/d95-bli/include/boost/property_map.hpp:328: provided for `
   template<class RandomAccessIterator, class IndexMap, class T, class
R> class
   boost::iterator_property_map'
-----

The offending line is:

typedef boost::iterator_property_map<std::vector<vertex_t>::iterator>
        parent_map_t;

It needs another template argument, namely an "IndexMap". I have to
confess I'm not completely sure what that is.

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

I /think/ I will need access to the parent for some traversals. It will
depend on how I implement them. Right now, I actually changed the graph
type from directed to bidirectional, because I needed access to the
parent. So now I can access the parent with in_edges(...) for the cost
of increased memory requirements. If I get graph_as_tree to work I guess
I can go back to using the directed graph type again?

Björn