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

From: David A. Greene (greened_at_[hidden])
Date: 2007-12-05 17:02:47

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