[Boost-users] [BGL] Properties Complexity

From: David A. Greene (greened_at_[hidden])
Date: 2007-11-21 17:58:32

What's the complexity of accessing a property bundle for
an adjacency list?  Does it change as the user changes the
selector for the vertex list structure (vecS vs. listS, etc.)?

I could imagine property access being constant-time for
vecS vertex lists, because the vertex space can be represented
with a dense set of numbers corresponding to the vertex's
position in the vector.  The property map can thus be a simple
vector or even a C array indexed by vertex number.

With listS, on the other hand, it's hard to see how one could
get constant-time property map lookup.

I have a problem where vertex property lookup happens very
frequently.  What kind of tradeoffs should I be thinking about?

                                     -Dave