Re: BGL: traversal algorithm for tree

Jeremy Siek wrote:

On Tue, 16 Jul 2002, [iso-8859-1] Björn Lindberg wrote: yg-boo> The offending line is: yg-boo> yg-boo> typedef boost::iterator_property_map::iterator> yg-boo> parent_map_t; yg-boo> yg-boo> It needs another template argument, namely an "IndexMap". I have to yg-boo> confess I'm not completely sure what that is.

Oops, my documentation lied to me. I'll have to fix that too.

An IndexMap maps vertices to a unique integer for each vertex, in the range [0,N), where N=num_vertices(G). If the graph has an internal property map for vertex indices, then you can get the map this way:

typedef property_map::type index_map_t; index_map_t index_map = get(vertex_index, G);

yg-boo> > One question... do you need to access parents? If not, you could fabricate yg-boo> > a dummy property map of the right type and pass that in. Or you could hack yg-boo> > graph_as_tree and remove all the stuff about parents. yg-boo> yg-boo> I /think/ I will need access to the parent for some traversals. It will yg-boo> depend on how I implement them. Right now, I actually changed the graph yg-boo> type from directed to bidirectional, because I needed access to the yg-boo> parent. So now I can access the parent with in_edges(...) for the cost yg-boo> of increased memory requirements. If I get graph_as_tree to work I guess yg-boo> I can go back to using the directed graph type again?

Sure, or you can implement the parent property map using in_edges(). The graph_as_tree approach will use a bit less memory.

I have managed to use the traverse_tree algorithm with graph_as_tree now. I just thought of something though. When I traverse the tree, I will need access to several internal properties at the nodes and also edges in the original graph. Elsewhere I access them via property maps, but I can't see how this could be done inside a TreeVisitor. Even if I take a Tree as an argument to the TreeVisitor constructor, I won't be able to extract the property maps from the graph inside the Tree (graph_as_tree really), right? Right now I'm thinking that I should just skip graph_as_tree, and reimplement the traverse_tree algorithm directly for graphs, so that I can access all of the graph functionality. Would this be best do you think, and have I made any oversights in the reasoning above? TIA, Björn