Re: [Boost-users] [BGL] Property Map Types

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-12-06 09:08:17

On Dec 5, 2007 3:56 PM, David A. Greene <greened_at_[hidden]> wrote:
> When I define an adjacency_list with vecS for the VertexList and use
> bundled properties to store attributes, what is the time complexity of
> invoking operator[] on the graph object?  Is it constant-time, logarithmic
> or something else?  In other words, what's the underlying data structure
> used to store the mapping from vertex descriptor to bundle?
>
> I've been trying to play around with changing this data structure by
> specializing property_map and property_traits, something like this:
>

<snip>

>
> This isn't all compiling yet, but am I on the right track?  Is this how
> things should be done for bundled properties?  The documentation
> is very sparse here.
>
> I have a code that is spending significant time looking up properties
> and I'd like to optimize it as much as possible.

Hi David,

It's constant time, for both bundled properties and the older interior
properties. "property map" is just an interface - when you call get(p,
v) or get(p, e) for some property map p, vertex v, and edge e,
completely different things happen depending on whether you're using
an interior property map (as with bundled properties) or an external
property map (for example, a vector storing vertex properties). With
bundled/interior properties, the values of the properties are stored
along with the vertex/edge storage, so when you call get(p,v), you can
access the property in constant time (since you have both a vertex
descriptor and the property that you want to access within that
vertex).

For example, if you declare the struct:

struct vertex_properties
{
  std::string name;
  double weight;
};

and then declare a graph to use this struct as a bundled vertex property:

adjacency_list<vecS, vecS, undirectedS, vertex_properties> g;

then you essentially end up with a copy of that struct stored along
with each vertex. A call to g[v].name, for some vertex v, just needs
to access the "name" field of v's internal property struct. So, I
wouldn't try to optimize bundled properties - they're already about as
fast as they're going to get.

Regards,
Aaron