Re: [boost] BGL: properties & edges

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-08-13 12:46:50

Hi Vladimir,

On Tue, 13 Aug 2002, Vladimir Prus wrote:
ghost> >
ghost> > For adjacency_list, the way to get external property maps is to first
ghost> > create an internal property map that assigns an index to each edge, and
ghost> > then you can use the index as a key in external maps.
ghost>
ghost> Hmm... will that property be automagic or I'll have to assign indices

Yes, you'd have to assign indices manually.

ghost> manually? I hope you'll agree that the latter case is a little bit more
ghost> complicated that it should be:
ghost>
ghost> 1. I have to declare graph with additional internal property
ghost> 2. I have to fill that internal property when needed.
ghost> 3. I have to first find edge's index and then index my map.

I agree, it is a pain. Though, item 3 isn't a problem if you use
iterator_property_map for external storage.

ghost> > ghost> What would be nice is to have a way to get a property map type given
ghost> > a graph ghost> type and a contained type. Something like
ghost> > ghost>
ghost> > ghost>     boost::edge_property_map<CFG, bool>::type final ;
ghost> >
ghost> > And this would be an internal map, yes? But I thought you just said you
ghost> > wanted external, not internal.
ghost>
ghost> Not exactly. You will be able to index this map using edge_descriptor but the
ghost> data will not be stored in graph. So this is external property.
[snip]
ghost> One possible approach to store edges indices inside graph.
ghost> edge_property_map would just keep a vector of values, and its
ghost> subscript operator would:
ghost> 1. Obtain index for the edge
ghost> 2. Subscript the vector.
ghost>
ghost> Of course, there are possible problems, such as whether the indices should be
ghost> updated when graph changes (and edge_property_map would be invalidated) or
ghost> not, etc., but I think it worth trying.

Yes, updating indices when the graph changes is a problem, though we
already face that problem with vertices, and so far we have just left it
up to users to make sure that external property maps stay in sync, which
is not ideal.

One approach we could take to try an address these problems is to build a
new graph class built on top of adjacency_list. Would you be interested in
working on this Vladimir? I could help some, but I'm pretty busy right now
studying for PhD qualifying exams.

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