Re: BGL: traversal algorithm for tree

From: Björn Lindberg (yg-boost-users_at_[hidden])
Date: 2002-07-18 09:43:32

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<std::vector<vertex_t>::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<graph_t, vertex_index_t>::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