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