[boost] [Graph] Bundled properties

From: Douglas Gregor (gregod_at_[hidden])
Date: 2004-05-07 10:20:06

Introducing internal properties for vertices and edges is too hard, and is one 
of the various things that came up in the "forced client complexity" thread. 
For a simple task, I ended up writing this:

--------------------------------------------------------
namespace boost {
  enum edge_length_t { edge_length };
  enum edge_speed_limit_t { edge_speed_limit };
  enum edge_direction_t { edge_direction };
  enum edge_snow_route_t { edge_snow_route} ;

  BOOST_INSTALL_PROPERTY(edge, length);
  BOOST_INSTALL_PROPERTY(edge, direction);
  BOOST_INSTALL_PROPERTY(edge, speed_limit);
  BOOST_INSTALL_PROPERTY(edge, snow_route);
}

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    // Vertex properties
    boost::property<boost::vertex_name_t, std::string>,
    // Edge properties
    boost::property<boost::edge_name_t, std::string,
    boost::property<boost::edge_length_t, double,
    boost::property<boost::edge_speed_limit_t, int,
    boost::property<boost::edge_direction_t, char,
    boost::property<boost::edge_snow_route_t, bool> > > > > >
  RouteMap;
--------------------------------------------------------

I'm basically enumerating all of the fields in a struct, but it's not 
represented efficiently (for the human, compiler, or run-time). I'd really 
like to do something like this:

--------------------------------------------------------
struct Intersection
{
  std::string name;
};

struct Street
{
  std::string name;
  double length;
  int speed_limit;
  char direction;
  bool snow_route;
};

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    Intersection, Street> RouteMap;
--------------------------------------------------------

It's a heck of a lot shorter and more intuitive. The attached patch introduces 
this capability for adjacency_list. The UDT's Intersection and Street are 
referred to as "bundled properties", and may occur at the end of the vertex 
or edge property list passed to adjacency_list. Accessing these bundled 
properties is done using the graph's subscript operator:

void foo(Map& g, Map::vertex_descriptor v, Map::edge_descriptor e)
{
  map[v].name = "Albany";
  map[e].length = 25.3;
}

Often one needs a property map for an internal property. With bundled 
properties this is achieved through an overloaded ->* operator. So if you 
want to create a property map from edge descriptors to the speed_limit 
property for a graph g, use:

        g->*&Street::speed_limit

And here's a real usage:

void shortest(Map& g, Map::vertex_descriptor from)
{
  dijkstra_shortest_paths(g, from, weight_map(g->*&Street::length));
}

The attached patch implements this functionality. It is completely 
backward-compatible (no new regressions on GCC 3.3.x), includes documentation 
and a test case, and seems to work well.

Comments?

        Doug