Re: [Boost-users] [BGL] Accelerating property value-retrieval

Subject: Re: [Boost-users] [BGL] Accelerating property value-retrieval
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2011-04-08 11:12:04

On Friday, 8. April 2011 16:33:23 Jeremiah Willcock wrote:
> On Fri, 8 Apr 2011, Cedric Laczny wrote:
> > Hi,
> > 
> > I would like to know if there is a way to accelerate the retrieval of
> > properties of an edge or a vertex?
> > Actually, I define a new vertex-property (vertex_properties) and this
> > again uses a "struct VertexProperties { ... }" to specify the details of
> > the properties.
> > However, when I want to get the properties of say vertex v, I need to
> > first get the properties-map from the graph and then get the property
> > for v. This obviously suffers from the lookup in the property_map and I
> > would like to know if there is a way to accelerate this?
> 
> You can save the property map in a variable to avoid repeated lookups, but
> I suspect they are not too expensive.
> 

I agree with you on that.

> > In particular, when using vecS as the
> > vertex_container because the vertices could generally be used as
> > indices... I would find this very convenient, especially in combination
> > with filtered_graph when filtering only on vertices that have certain
> > properties (e.g. a category) and one only wants to see those that have a
> > specific character (e.g. color).
> 
> Fast lookups will probably require external properties, since those are
> much simpler and have fewer layers of indirection (no pointers to members,
> for example).  Can you copy your properties to an iterator_property_map
> (built on a vector) before the high-performance parts of your code?
> 

This is a nice idea. So if I am getting this right, in the case of vecS, 
get(vertex_index, g) should return the identity_property_map, thus resulting 
in linear lookup. At the same time, using the intermediate vertex_index map 
and an iterator_property_map would guarantee at least valid lookups in case of 
other vertex-containers, albeit they would then require the usual O(log n) 
lookup. This of course only if the graph also provides a vertex-index map.
Or am I missing something here?

> -- Jeremiah Willcock

Best,

Cedric