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_property_type;
typedef boost::adjacency_list graph_type;
// Specialize the graph property map to be a vector for
// vecS vertex lists to make lookup faster
template
struct property_map,
vertex_property_type> {
typedef boost::adjacency_list<
EdgeListType, vecS, DirectedType, vertex_property_type> graph_type;
typedef std::vector type;
};
template <typename T>
struct property_traits {
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
