Re: [boost] [graph] SoC update

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2007-08-31 08:48:45

On Thu, 2007-08-30 at 22:07 -0400, Andrew Sutton wrote:
> I'm more than willing to spend some serious time working on  
> Boost.Graph this semester - It won't be as much as I spent this  
> summer, but at least a couple days a week. 

Great! I am, of course, willing to spend what time I can on this
long-overdue project.

> Besides, the person  
> working on Boost docs for IBD was me.

I should have known that :)

> Unfortunately, I've only taken a quick look at pBGL so I don't know  
> too much about it. Those improvements would have to be pointed out.

Sure. The one major improvement that we're working on in the pBGL that's
also useful for the BGL is the "named vertices" extension to graphs. The
basic idea is very simple: if the vertex property somehow contains a
"name" buried inside it, we can use that name as an alternative way to
refer to the vertex. For example, say we have a City structure that we
attach to each vertex:

  struct City {
    City() {}

    City(const std::string& name, int population = -1)
      : name(name), population(population) { }
  
    std::string name;
    int population;
  };

If we tell the BGL that the "name" field of the City structure is the
name of the corresponding vertex, then graphs will now allow us to refer
to cities by name:

  typedef adjacency_list<...> RoadMap;
  RoadMap road_map;
  
  Vertex bloomington = add_vertex(City("Bloomington", 69291), map);
  Vertex indianapolis = add_vertex(City("Indianapolis", 791926), map);
  Vertex chicago = add_vertex(City("Chicago", 9500000), map);

  add_edge(bloomington, "Indianapolis", map);
  add_edge("Indianapolis", chicago, map);
  add_edge("Indianapolis", "Cincinatti", map);

The graph handles the mapping from names like "Indianapolis" to vertex
descriptors, even adding vertices when no such vertex exists (as is the
case for "Cincinatti"). 

How many times have users had to create and maintain an
std::map<std::string, vertex_descriptor> to do this same thing? Too
many, in my opinion.

        - Doug