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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-07-16 10:48:51

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.

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