On Dec 6, 2007 2:40 PM, David A. Greene
On Thursday 06 December 2007 10:39, Johan Oudinet wrote:
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.
Ok, that's what I would have expected (vecS constant-time, listS not). Thanks for confirming that.
No, both are actually constant-time - access to internal vertex and edge properties is constant time, independent of whether you're storing vertices/edges in a vector or list. The vertex descriptor you get from a using a listS storage selector is a void*, but inside the adjacency_list property accessor code, it's converted to a pointer to the vertex storage, and then the properties can be accessed in constant time as I described before. The whole situation is analogous to defining a struct S of properties (your bundled property definitions), then creating a std::vector<S> or std::list<S> to hold your vertices. In the case of std::vector<S>, given a vertex (represented by an integer), you can obviously get the properties for that vertex in constant time. Also, in the case of std::list<S>, given a vertex (represented by an iterator), you can get the properties of that vertex in constant time. This is essentially what's going on, but it's a little more complicated than that. Regards, Aaron