Changes between Initial Version and Version 1 of soc/2007/UserFriendlyGraphDesignThree

Timestamp:

May 14, 2007, 4:21:45 PM (15 years ago)

Author:

Andrew Sutton

Comment:

--

soc/2007/UserFriendlyGraphDesignThree

@@ +1 @@
+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 [wiki:soc/2007/UserFriendlyGraphDesignTwo my second iteration], it somewhat more refined, targeting a very specific set of
+criteria: specifically, usability.  The basic outline follows:
+
+{{{
+#!cpp
+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,
+
+{{{
+#!cpp
+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> &g
+           undirected_graph<VP,EP,GP>::vertex_descriptor u,
+           undirected_graph<VP,EP,GP>::vertex_desrciptor v)
+  {
+    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.
+
+It might also be worth noticing the re-ordering of parameters to the `add_edge()` method. This aligns with the more convential style of putting the target object fist in the parameter list.
+
+== 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.