[Boost-users] [BGL] Property Map Types

From: David A. Greene (greened_at_[hidden])
Date: 2007-12-05 15:56:41

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