After working on some documentation for the library (porting to quickbook), I have been rethinking many of the requirements of these new classes. Although this design is not radically different than that of my second iteration, it somewhat more refined, targeting a very specific set of criteria: specifically, usability. The basic outline follows:

namespace boost {
  template <class VP, class EP, class GP>
  class undirected_graph
  {
    typedef adjacency_list<vecS, vecS, undirectedS, VP, EP, GP, listS> graph_type;
    graph_type g;

  public:
    // ...

    inline graph_type& impl()
    { return g; }

    inline const graph_type& impl() const
    { return g; }
  };

  // the add_edge method...
  template <class VP, class EP, class GP>
  inline std::pair<undirected_graph<VP,EP,GP>::edge_descriptor, bool>
  add_edge(undirected_graph<VP,EP,GP> &g
           undirected_graph<VP,EP,GP>::vertex_descriptor u,
           undirected_graph<VP,EP,GP>::vertex_desrciptor v)
  {
    return boost::add_edge(g.impl(), u, v);
  }
}

Note that an alterntative to exposing an impl() method would be to have the class host all of common operations as member variables and have free functions call those. This would completely hide the underlying adjacency_list from the user. For example,

namespace boost {
  template <class VP, class EP, class GP>
  class undirected_graph
  {
    typedef adjacency_list<vecS, vecS, undirectedS, VP, EP, GP, listS> graph_type;
    graph_type g;

  public:
    // ...

    inline std::pair<edge_descriptor, bool>
    add_edge(vertex_descriptor u, vertex_descriptor v)
    { return boost::add_edge(u, v, g);
  };

  // the add_edge method...
  template <class VP, class EP, class GP>
  inline std::pair<undirected_graph<VP,EP,GP>::edge_descriptor, bool>
  add_edge(undirected_graph<VP,EP,GP>::vertex_descriptor u,
           undirected_graph<VP,EP,GP>::vertex_desrciptor v,
           undirected_graph<VP,EP,GP> &g)
  {
    return g.add_edge(u, v);
  }

Rationale

This is a much, much simpler template interface to a graph class than presented by adjacency_list class. Essentially, we remove almost all of the decision making requirements out of the class by using default arguments for the underlying implementation. Here, the intent is to make get the user working with a graph class (any graph class) as fast as possible. The user really only needs to worry about substituting different containers when performance becomes a requirement. At this point, the user can "simply" redefine the type of thier graphs to an adjacency_list as more of an "advanced" feature of the library. Moreover, by selecting vecS for both the vertex list and out edge list, we guarantee reasonable performance for a number of common graph problems.

We do however, leave the property templates in place so users can experiment with adding new properties to vertices and edges and using them with property maps (which isn't very well documented).

This design, when coupled with improved documentation, should provide

1. a clear starting point for new users,
2. a migration from basic, general functionality to advanced and customizable functionality,
3. and the guarantees type and performance required by the orignal Boost.Graph concepts.

Remarks

I'm actually very fond of this approach since it reduces the interface so much. However, this does leave questions about the directed_graph. Specifically, should its directional selection be directedS or bidirectionalS? My best guess is the latter since it provides more functionality at the expense of space efficiency, but it also makes it more applicable to a wider range of problems.