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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-12-06 19:30:40

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