[BGL] Property Map Types
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: // Define the graph and properties class vertex_property_bundle { ... }; // Define the property tag struct vertex_bundle_property_tag { typedef boost::vertex_property_tag kind; }; typedef boost::property<vertex_bundle_property_tag, vertex_property_bundle> vertex_property_type; typedef boost::adjacency_list<boost::vecS, // Out edge list type boost::vecS, // Vertex list type boost::undirectedS, vertex_property_type // Vertex properties // Edge properties > graph_type; // Specialize the graph property map to be a vector for // vecS vertex lists to make lookup faster template<typename EdgeListType, typename DirectedType> struct property_map<boost::adjacency_list< EdgeListType, vecS, DirectedType, vertex_property_type >, vertex_property_type> { typedef boost::adjacency_list< EdgeListType, vecS, DirectedType, vertex_property_type> graph_type; typedef std::vector<vertex_property_type> type; }; template <typename T> struct property_traits<std::vector<T> > { typedef unsigned long int key_type; typedef T value_type; typedef boost::lvalue_property_map_tag category; }; // overloads of the property map functions for vectors template<typename T> void put(vector<T> &pmap, unsigned long int k, const T& val) { if (pmap.size() <= k) { pmap.resize(k); } pmap[k] = val; } template<typename T> T& get(vector<T> &pmap, unsigned long int k) { assert(k < pmap.size() && "Property map overflow"); return pmap[k]; } template<typename T> const T& get(const vector<T> &pmap, unsigned long int k) { assert(k < pmap.size() && "Property map overflow"); return pmap[k]; } 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. Thanks for helping. -Dave
On Wednesday 05 December 2007 14:56, David A. Greene wrote:
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:
// Define the graph and properties class vertex_property_bundle { ... };
// Define the property tag struct vertex_bundle_property_tag { typedef boost::vertex_property_tag kind; };
typedef boost::property<vertex_bundle_property_tag, vertex_property_bundle> vertex_property_type;
Oops, this isn't right. I got lots of compile errors. Looking through the BGL headers, I stumbled across vertex_bundle_t, so I replaced the above with this: typedef vertex_property_bundle vertex_property_type; typedef boost::vertex_bundle_t vertex_bundle_property_tag;
// Specialize the graph property map to be a vector for // vecS vertex lists to make lookup faster template<typename EdgeListType, typename DirectedType> struct property_map<boost::adjacency_list< EdgeListType, vecS, DirectedType, vertex_property_type
, vertex_property_type> { typedef boost::adjacency_list< EdgeListType, vecS, DirectedType, vertex_property_type> graph_type; typedef std::vector<vertex_property_type> type; };
This isn't right either. I replaced the second vertex_property_type with vertex_bundle_property_tag. The rest of the code is the same, except I added writes to std::cerr in the get() and put() routines to see if they are used. Now I get this compiler error: boost-1_34_1/boost/graph/adjacency_list.hpp:423: error: no matching function for call to "get(boost::vertex_bundle_t, const boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, vertex_property_bundle, boost::no_property, boost::no_property, boost::listS>&)" Eh? -Dave
On Dec 5, 2007 3:56 PM, David A. Greene <greened@obbligato.org> wrote:
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<vecS, vecS, undirectedS, vertex_properties> 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. Regards, Aaron
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<vecS, vecS, undirectedS, vertex_properties> 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. -Dave
On Dec 6, 2007 5:00 PM, David A. Greene <greened@obbligato.org> 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<vecS, vecS, undirectedS, vertex_properties> 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
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. -Dave
On Dec 6, 2007 8:40 PM, David A. Greene <greened@obbligato.org> 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.
You're welcome. Furthermore, space and time complexity for each container are explained in the documentation : http://www.boost.org/libs/graph/doc/using_adjacency_list.html#sec:choosing-g... Regards, -- Johan
On Dec 6, 2007 2:40 PM, David A. Greene <greened@obbligato.org> 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
On Dec 7, 2007 1:30 AM, Aaron Windsor <aaron.windsor@gmail.com> wrote:
On Dec 6, 2007 2:40 PM, David A. Greene <greened@obbligato.org> 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
[snip] I agree with you. I though David didn't have the vertex descriptor, so the complexities that I talked are about how to find the vertex descriptor according to a property. Of course the access to the properties after that is constant time. Sorry for the misunderstanding of your question David. Regards, -- Johan
participants (3)
-
Aaron Windsor -
David A. Greene -
Johan Oudinet