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

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