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