Re: [boost] BGL: properties & edges

From: Vladimir Prus (ghost_at_[hidden])
Date: 2002-08-14 01:28:30

Hi Jeremy,

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

Agree, but 1-2 still remain. Further, wrapper which holds a vector internally 
would be more usefull -- you don't need to declare vector/array yourself and
create a property map from it.

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

Not sure a new graph class would completely solve the problem: I would like 
to have external property maps available for all graphs (or all PropertyGraph 
models). 

As to your question -- yea, I would be interested in devising some solution.
However, I've two other pending tasks -- making Boost.Build v2 build 
something, and finishing/submitting command line parser, which stayed 90% 
finished for half an year. It means that I cannot start actually working with 
graph properties before October. (and also hope *my* PhD qualifying exams 
won't take much time)

- Volodya