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