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