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

From: Johan Oudinet (johan.oudinet_at_[hidden])
Date: 2007-12-06 11:39:53

On Dec 6, 2007 5:00 PM, David A. Greene <greened_at_[hidden]> wrote:
> 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.
>

What Aaron try to explain you is that the vertex (edge) properties are
bound to their corresponding vertex (edge). So the complexity to look
for a vertex property is the same than finding its corresponding
vertex.

If you want to have constant time access to vertex properties, clearly
don't use a ListS for your VertexList but a VecS for example.

Regards,

-- 
Johan