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

From: David A. Greene (greened_at_[hidden])
Date: 2007-12-06 11:00:08

On Thursday 06 December 2007 08:08, Aaron Windsor wrote:

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

Thanks Aaron,

I'm not clear on exactly what you are describing.  get(p, v) doesn't
seem to include the graph itself at all.  So I'm not sure what you're
talking about.  I understand that once you have the bundle, accessing
the member is simply a pointer-to-member dereference.  What I am
wondering is if getting the bundle from the graph (via graph[v]) is
constant-time.  If so, then my life gets much simpler.

I don't see how this can be constant-time for a graph with a listS
VertexList, as v is a void *.  There has to be some kind of map in
that case, correct?  It could be a hash table, but that is not described
anywhere in the documentation.  I find it strange that complexity
guarantees for property access are not included in the BGL 
documentation.

Can you clarify?  Thanks.

                                         -Dave