Re: [boost] BGL: properties & edges

From: Vladimir Prus (ghost_at_[hidden])
Date: 2002-08-13 04:59:10

Jeremy Siek wrote:
> Hi Vladimir,
>
> On Mon, 12 Aug 2002, Vladimir Prus wrote:
> ghost>
> ghost> Hi,
> ghost> I've a simple task: I need to attach bool value to graph edges.
> Okay, docs ghost> say:
> ghost>  "Creating a your own property types and properties is easy; just
> define a ghost> tag class for your new property."
> ghost>
> ghost> But now I really don't like this.
> ghost> 1. Why should I create any "tag class" if edge->bool mapping is all
> I need.
>
> The tag class gives a name to the mapping, to differentiate it from other
> mappings.

Yea, that's good for internal properties, but I want external ones.

> ghost> 2. I don't want to store my mapping as internal property and I see
> no way to ghost> create external one.
> ghost>
> ghost> 3. Finally, edge_descriptor is not required to have "<" operator, so
> I can't ghost> use map (aside from efficiency issues).
>
> For adjacency_list, the way to get external property maps is to first
> create an internal property map that assigns an index to each edge, and
> then you can use the index as a key in external maps.

Hmm... will that property be automagic or I'll have to assign indices 
manually? I hope you'll agree that the latter case is a little bit more 
complicated that it should be:

1. I have to declare graph with additional internal property
2. I have to fill that internal property when needed. 
3. I have to first find edge's index and then index my map.

> ghost> What would be nice is to have a way to get a property map type given
> a graph ghost> type and a contained type. Something like
> ghost>
> ghost>     boost::edge_property_map<CFG, bool>::type final ;
>
> And this would be an internal map, yes? But I thought you just said you
> wanted external, not internal.

Not exactly. You will be able to index this map using edge_descriptor but the 
data will not be stored in graph. So this is external property.

> ghost> If such type is defined for every PropertyGraph then I can
> ghost> associate any data with edges and know that it's as efficient as
> ghost> possible for the given graph type.
> ghost>
> ghost> Opinions?
>
> Sure, that would be nice. I just don't know how to implement it so that
> deciding which internal property to access is done at compile time. If it
> is done at run-time there will be a performance hit. Do you have an
> implementation approach in mind?

One possible approach to store edges indices inside graph.
edge_property_map would just keep a vector of values, and its
subscript operator would:
1. Obtain index for the edge
2. Subscript the vector.

Of course, there are possible problems, such as whether the indices should be
updated when graph changes (and edge_property_map would be invalidated) or 
not, etc., but I think it worth trying.

- Volodya