[Boost-commit] svn:boost r46555 - sandbox/SOC/2008/graphs/trunk/boost/graphs

From: asutton_at_[hidden]
Date: 2008-06-20 08:53:24

Author: asutton
Date: 2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
New Revision: 46555
URL: http://svn.boost.org/trac/boost/changeset/46555

Log:
Vertex descriptors are now real, distinct types. This clears a potential
problem where compilation would fail on overloads where the descriptor and
properties/keys are the same type.

Added all the missing add_edge() overloads in both directed and undirected
graphs.

Implemented part of list-based in/out edge storage.

Started rewriting some of the traits checks for directed/undirected graphs.
These will clearly need a fair amount of work in the future.

Added:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp
      - copied, changed from r46477, /sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp
Removed:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp    |   126 ++++++++++++++++++++++++++++++++++++--- 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp         |    41 +++++++++++-                            
   sandbox/SOC/2008/graphs/trunk/boost/graphs/traits.hpp            |    87 ++++++++++++++++++++++-----             
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp  |    89 +++++++++++++++++++++++++--             
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp |    67 ++++++++++++++------                    
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp       |    21 +++--                                   
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp        |    11 ++-                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp        |    11 ++-                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp     |    11 ++-                                     
   9 files changed, 384 insertions(+), 80 deletions(-)

Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
+++ (empty file)
@@ -1,81 +0,0 @@
-
-#ifndef DESCRIPTOR_HPP
-#define DESCRIPTOR_HPP
-
-// Important notes about descriptors
-//
-// A descriptor is basically an opaque reference to an object. It's kind of
-// like an iterator that can't be moved or dereferenced. It's kind of like a
-// flyweight, but you can't implicitly cast it as the shared object. In short,
-// you can't use descriptors without their graph. In general, we'd like the
-// descriptor types to be as trivial as possible. One of the most important
-// facts about descriptors is that, by themselves, they have absolutely no
-// semantics. They cannot be used (in general) be used to access the vertices
-// or edges that they represent.
-//
-// The most important thing to understand about descriptors is that they attempt
-// to model the most "consistent" reference into a storage mechanism. By the
-// term "consistent", we mean a means of accessing elements that allow us to
-// actually build a graph without invalidating memory or iterators. For example,
-// we can't use pointers as descriptors into vectors since vectors occasionally
-// reallocate all their memory (oops), but indices work just fine.
-//
-// Descriptors must be completely independent of the actual type of vertices
-// and edges. Two problems arise if we don't do this. First, we end up with
-// weird cyclic type dependencies that can probably be unrolled using some
-// funky lazy template evaluation, but that's generally beyond me. Second,
-// this would
-
-// Build trivial wrappers around the underlying descriptor types. This allows
-// us to differentiate descriptors based on these types rather than their
-// simple descriptor types.
-
-template <typename D>
-class basic_vertex_descriptor
-{
-public:
-    inline basic_vertex_descriptor()
-        : desc()
-    { }
-
-    inline basic_vertex_descriptor(D d)
-        : desc(d)
-    { }
-
-    // Assignment copy.
-    inline basic_vertex_descriptor& operator=(basic_vertex_descriptor const& d)
-    {
-        desc = d.desc;
-        return *this;
-    }
-
-    // value-type assignment.
-    inline basic_vertex_descriptor& operator=(D d)
-    {
-        desc = d;
-        return *this;
-    }
-
-    // Just to make the access a little prettier.
-    inline D get() const
-    { return desc; }
-
-    // Provides an implicit cast to bool. Returns true if the basic_vertex_descriptor
-    // is not the same as its default value.
-    inline bool is_valid() const
-    { return desc != basic_vertex_descriptor().desc; }
-
-    inline bool operator<(basic_vertex_descriptor const& d) const
-    { return desc < d.desc; }
-
-    inline bool operator==(basic_vertex_descriptor const& d) const
-    { return desc == d.desc; }
-
-    inline bool operator!=(basic_vertex_descriptor const& d) const
-    { return desc != d.desc; }
-
-    D desc;
-};
-
-#endif
-

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -15,16 +15,20 @@
 // graph, you can roll your own. This is analagous to the list/slist data
 // structures in the std library.
 
-#include "none.hpp"
+// Note that directed graphs maintain an independent edge count since the actual
+// count would basically require a search.
 
-#include "descriptor.hpp"
+#include "none.hpp"
 
 #include "directed_vertex.hpp"
-#include "vertex_iterator.hpp"
 #include "vertex_vector.hpp"
+#include "vertex_list.hpp"
+#include "vertex_set.hpp"
+#include "vertex_map.hpp"
 
 #include "directed_edge.hpp"
 #include "edge_vector.hpp"
+#include "edge_list.hpp"
 
 #include "adjacency_iterator.hpp"
 
@@ -75,6 +79,9 @@
     typedef typename vertex_store::vertex_iterator vertex_iterator;
     typedef typename vertex_store::vertex_range vertex_range;
 
+    // This just makes sense.
+    typedef std::size_t edges_size_type;
+
     // FIXME: This is a bit hacky, but without constrained members, we need a key
     // type to enable mapped vertices.
     typedef typename VertexStore::key_type vertex_key;
@@ -152,10 +159,25 @@
      */
     //@{
     vertex_key const& key(vertex_descriptor) const;
-    //@{
+    //@}
 
     /** @name Add Edge
-     * Add an edge, connecting two vertices, to the graph.
+     * Add an edge, connecting two vertices, to the graph. There are a number of
+     * variations of this function, depending on the type of vertex store and
+     * whether or not the edges are labeled. Convenience functions are provided
+     * for graphs with UniqueVertices. Graphs with LabeledEdges can be added
+     * with edge properties. Convenience functions are equivalent to the
+     * expression add_edge(find_vertex(x), find_vertex(y), p) with x and y
+     * eithe vertex proeprties or vertex keys and p optional edge properties.
+     *
+     * ExtendableEdgeSet        add_edge(vertex_descriptor, vertex_descriptor)
+     *   && LabeledEdges        add_edge(vertex_descriptor, vertex_descriptor, edge_properties)
+     *
+     * LabeledUniqueVertices    add_edge(vertex_properties, vertex_properties)
+     *   && LabeledEdges        add_edge(vertex_properties, vertex_properties, edge_properties)
+     *
+     * MappedUniqueVertices     add_edge(vertex_key, vertex_key)
+     *   & LabeledEdges         add_edge(vertex_key, vertex_key, edge_properties)
      */
     //@{
     edge_descriptor add_edge(vertex_descriptor, vertex_descriptor);
@@ -165,12 +187,14 @@
     edge_descriptor add_edge(vertex_descriptor, vertex_descriptor, edge_properties const&);
     edge_descriptor add_edge(vertex_properties const&, vertex_properties const&, edge_properties const&);
     edge_descriptor add_edge(vertex_key const&, vertex_key const&, edge_properties const&);
-    //@{
+    //@}
 
-    /** @name Degree
+    /** @name Size and Degree
      * Return the in/out or cumulative degree of the given vertex.
      */
     //@{
+    vertices_size_type num_vertices() const;
+    edges_size_type num_edges() const;
     out_edges_size_type out_degree(vertex_descriptor v) const;
     in_edges_size_type in_degree(vertex_descriptor v) const;
     incident_edges_size_type degree(vertex_descriptor v) const;
@@ -183,10 +207,11 @@
     //@{
     vertex_properties& operator[](vertex_descriptor);
     edge_properties& operator[](edge_descriptor);
-    //@{
+    //@}
 
 private:
-    vertex_store _verts;
+    vertex_store        _verts;
+    edges_size_type     _edges;
 };
 
 #define BOOST_GRAPH_DG_PARAMS \
@@ -195,6 +220,7 @@
 template <BOOST_GRAPH_DG_PARAMS>
 directed_graph<VP,EP,VS,ES>::directed_graph()
     : _verts()
+    , _edges(0)
 { }
 
 /**
@@ -367,14 +393,19 @@
         // The addition is allowed... Was there already an edge there? If not,
         // connect u to v (and vice-versa) with the given properties. Otherwise,
         // just return the existing edge.
+        edge_descriptor e;
         if(ins.first == src.end_out()) {
             out_descriptor o = src.connect_to(v, ep);
             tgt.connect_from(u, o);
-            return edge_descriptor(u, o);
+            e = edge_descriptor(u, o);
         }
         else {
-            return edge_descriptor(u, *ins.first);
+            e = edge_descriptor(u, *ins.first);
         }
+
+        // Remember that we're allocating the edge.
+        ++_edges;
+        return e;
     }
     else {
         // Can't add the edge? This is a flat refusal (as in a loop).
@@ -384,6 +415,77 @@
 }
 
 /**
+ * Add an edge to the graph that connects the two vertices identified by the
+ * given properties. The edge is either unlabeled or has default properties.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_descriptor
+directed_graph<VP,EP,VS,ES>::add_edge(vertex_properties const& u,
+                                        vertex_properties const& v)
+{
+    return add_edge(u, v, edge_properties());
+}
+
+/**
+ * Add an edge to the graph that connects the two vertices identified by the
+ * given properties and has the given edge properties.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_descriptor
+directed_graph<VP,EP,VS,ES>::add_edge(vertex_properties const& u,
+                                        vertex_properties const& v,
+                                        edge_properties const& ep)
+{
+    return add_edge(find_vertex(u), find_vertex(v), ep);
+}
+
+/**
+ * Add an edge to the graph that connects the two vertices identified by the
+ * given keys. The edge is either unlabeled or has default properties.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_descriptor
+directed_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
+                                        vertex_key const& v)
+{
+    return add_edge(u, v, edge_properties());
+}
+
+/**
+ * Add an edge to the graph that connects the two vertices identified by the
+ * given keys and has the given edge properties.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_descriptor
+directed_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
+                                        vertex_key const& v,
+                                        edge_properties const& ep)
+{
+    return add_edge(find_vertex(u), find_vertex(v), ep);
+}
+
+/**
+ * Return the number of vertices in the graph.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertices_size_type
+directed_graph<VP,EP,VS,ES>::num_vertices() const
+{
+    return _verts.size();
+}
+
+/**
+ * Return the number of edges in the graph.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edges_size_type
+directed_graph<VP,EP,VS,ES>::num_edges() const
+{
+    return _edges;
+}
+
+
+/**
  * Return the out degree of the given vertex.
  */
 template <BOOST_GRAPH_DG_PARAMS>
@@ -434,4 +536,6 @@
     return e.properties();
 }
 
+#undef BOOST_GRAPH_DG_PARAMS
+
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -4,28 +4,61 @@
 
 #include "property_list.hpp"
 #include "incidence_list.hpp"
+#include "out_list.hpp"
+#include "in_list.hpp"
 
 // The edge list does two things. First, it indicates that edges will
 // be stored in an incidence list (as opposed to a vector or set).
 // Second, this will indicate the use of a global property list.
 // Again, as opposed to a vector.
 
+/**
+ * The basic_edge_list is the outer part of the metafunctions that generate
+ * types for adjacency lists.
+ */
 template <
-    template <typename> class IncAlloc,
-    template <typename> class PropAlloc>
+    template <typename> class FirstAlloc,
+    template <typename> class SecondAlloc>
 struct basic_edge_list
 {
+    // The property store metafunction generates the underlying global store
+    // type for edge properties in undirected graphs.
     template <typename EdgeProps>
     struct property_store
     {
-        typedef property_list<EdgeProps, PropAlloc<EdgeProps> > type;
+        typedef SecondAlloc<EdgeProps> allocator;
+        typedef property_list<EdgeProps, allocator> type;
     };
 
+    // The incidence store metafunction generates the per-vertex storage type
+    // for undirected vertices.
     template <typename VertexDesc, typename PropDesc>
     struct incidence_store
     {
         typedef std::pair<VertexDesc, PropDesc> incidence_pair;
-        typedef incidence_list<incidence_pair, IncAlloc<incidence_pair> > type;
+        typedef FirstAlloc<incidence_pair> allocator;
+        typedef incidence_list<incidence_pair, allocator > type;
+    };
+
+    // The out store metafunction generates the type of list used to store
+    // out edges of a vertex in a directed graph.
+    template <typename VertexDesc, typename Props>
+    struct out_store
+    {
+        typedef std::pair<VertexDesc, Props> out_pair;
+        typedef FirstAlloc<out_pair> out_allocator;
+        typedef out_list<out_pair, out_allocator> type;
+    };
+
+    // The in store metafunction generates the type of list used to store
+    // incoming edges of directed graph. In edges are represented by the
+    // referencing vertex and an out edge descriptor.
+    template <typename VertexDesc, typename OutDesc>
+    struct in_store
+    {
+        typedef std::pair<VertexDesc, OutDesc> in_pair;
+        typedef SecondAlloc<in_pair> in_allocator;
+        typedef in_list<in_pair, in_allocator> type;
     };
 };
 

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -0,0 +1,50 @@
+
+#ifndef IN_LIST_HPP
+#define IN_LIST_HPP
+
+#include <list>
+
+/**
+ * The in-edge list references incoming edges from other vertices. Each edge
+ * can be uniquely identified by its source vertex and property descriptor.
+ *
+ * @param Edge A pair describing a vertex descriptor and out edgedescriptor.
+ * @param Alloc The allocator for edge pairs.
+ */
+template <typename Edge, typename Alloc>
+class in_list
+{
+    typedef std::list<Edge, Alloc> store_type;
+public:
+    typedef Edge in_pair;
+    typedef typename Edge::first_type vertex_descriptor;
+    typedef typename Edge::second_type edge_descriptor;
+
+    typedef typename store_type::const_iterator const_iterator;
+    typedef typename store_type::size_type size_type;
+
+    in_list()
+        : _edges()
+    { }
+
+    void add(in_pair);
+
+    /** Get the number of incoming edges (in degree). */
+    size_type size() const
+    { return _edges.size(); }
+
+private:
+    store_type _edges;
+};
+
+/**
+ * Add the given pair to the edge set.
+ */
+template <typename E, typename A>
+void
+in_list<E,A>::add(in_pair e)
+{
+    _edges.push_back(e);
+}
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -0,0 +1,128 @@
+
+#ifndef OUT_LIST_HPP
+#define OUT_LIST_HPP
+
+#include <list>
+
+#include "out_descriptor.hpp"
+
+/**
+ * The out list implements list-based, out-edge storage for directed graphs.
+ * out-edges are uniquely identified by their target vertex and property
+ * descriptor. List-based stores support fast inserts, slow finds, but do allow
+ * removals.
+ *
+ * The edge is required to be a pair containing a vertex descriptor and a edge
+ * property (not descriptor). This type defines the out_descriptor - an opaque
+ * reference to a target/property pair.
+ *
+ * @param Edge A pair describing a vertex descriptor and the edge properties.
+ * @param Alloc The allocator for edge pairs.
+ */
+template <typename Edge, typename Alloc>
+class out_list
+{
+    typedef std::list<Edge, Alloc> store_type;
+public:
+    typedef Edge out_pair;
+    typedef typename Edge::first_type vertex_descriptor;
+    typedef typename Edge::second_type edge_properties;
+
+    typedef typename store_type::iterator iterator;
+    typedef typename store_type::const_iterator const_iterator;
+    typedef typename store_type::size_type size_type;
+
+    typedef basic_out_descriptor<out_pair> out_descriptor;
+
+    inline out_list()
+        : _edges()
+    { }
+
+    std::pair<const_iterator, bool> allow(vertex_descriptor v) const;
+    out_descriptor add(out_pair);
+    iterator find(out_pair);
+    const_iterator find(out_pair) const;
+    void remove(out_pair);
+    void clear();
+
+    /** @name Iterators and Size */
+    //@{
+    inline const_iterator begin() const
+    { return _edges.begin(); }
+
+    inline const_iterator end() const
+    { return _edges.end(); }
+
+    /** Get the number of outgoing edges. */
+    inline size_type size() const
+    { return _edges.size(); }
+    //@{
+
+private:
+    store_type _edges;
+};
+
+/**
+ * Out lists always allow the insertion of new edges, unless configured by
+ * policy to do otherwise.
+ */
+template <typename E, typename A>
+std::pair<typename out_list<E,A>::const_iterator, bool>
+out_list<E,A>::allow(vertex_descriptor v) const
+{
+    return std::make_pair(_edges.end(), true);
+}
+
+/**
+ * Add the incident edge, returning the property descriptor of the added
+ * incidence pair.
+ */
+template <typename E, typename A>
+typename out_list<E,A>::out_descriptor
+out_list<E,A>::add(out_pair e)
+{
+    _edges.push_back(e);
+    return _edges.back();
+}
+
+/**
+ * Find the requested incidence pair in the list, returning an iterator to it.
+ */
+template <typename E, typename A>
+typename out_list<E,A>::iterator
+out_list<E,A>::find(out_pair e)
+{
+     return std::find(_edges.begin(), _edges.end(), e);
+}
+
+/**
+ * Find the requested incidence pair in the list, returning an iterator to it.
+ */
+template <typename E, typename A>
+typename out_list<E,A>::const_iterator
+out_list<E,A>::find(out_pair e) const
+{
+    return std::find(_edges.begin(), _edges.end(), e);
+}
+
+/**
+ * Remove the given incidence pair from the out list.
+ */
+template <typename E, typename A>
+void
+out_list<E,A>::remove(out_pair e)
+{
+    _edges.erase(find(e));
+}
+
+/**
+ * Remove all edges from the out list.
+ */
+template <typename E, typename A>
+void
+out_list<E,A>::clear()
+{
+    _edges.clear();
+}
+
+#endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/traits.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/traits.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/traits.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -2,33 +2,88 @@
 #ifndef TRAITS_HPP
 #define TRAITS_HPP
 
+#include <boost/utility.hpp>
+#include <boost/mpl/if.hpp>
+
+#include "undirected_graph.hpp"
+#include "directed_graph.hpp"
+
 namespace detail
 {
-    // This isn't quite so simple as it seems. I think we need to have the
-    // catch-all push the query back to a policy object and that policy needs
-    // to be explicit about whether or not it allows multiple edges.
     template <typename Store>
-    struct is_simple
-    { enum { value = false }; };
+    struct has_unique_elems
+    { BOOST_STATIC_CONSTANT(bool, value = false); };
 
     template <typename E, typename C, typename A>
-    struct is_simple< incidence_set<E,C,A> >
-    { enum { value = true }; };
+    struct has_unique_elems< incidence_set<E,C,A> >
+    { BOOST_STATIC_CONSTANT(bool, value = true); };
 
-};
+    template <typename Graph>
+    struct directed_parallel
+    {
+        BOOST_STATIC_CONSTANT(bool, value = false);
+    };
+
+    template <typename Graph>
+    struct undirected_parallel
+    {
+        BOOST_STATIC_CONSTANT(
+            bool,
+            value = has_unique_elems<typename Graph::incidence_store>::value);
+    };
+}
 
-/**
- * This metafunction determines if the graph allows multiple edges.
+/** @name Is Directed Trait
+ * Determine if the graph is directed or undirected.
  */
+//@{
 template <typename Graph>
-struct is_simple
-{ enum { value = detail::is_simple<typename Graph::incidence_store>::value }; };
+struct is_directed
+{
+    BOOST_STATIC_CONSTANT(bool, value = false);
+};
 
-/**
- * A helper function for the above.
+template <typename VP, typename EP, typename VS, typename ES>
+struct is_directed< directed_graph<VP,EP,VS,ES> >
+{
+    BOOST_STATIC_CONSTANT(bool, value = true);
+};
+
+template <typename VP, typename EP, typename VS, typename ES>
+struct is_directed< undirected_graph<VP,EP,VS,ES> >
+{
+    BOOST_STATIC_CONSTANT(bool, value = false);
+};
+
+template <typename Graph>
+inline bool is_directed_graph(Graph const& g)
+{ return is_directed<Graph>::value; }
+
+template <typename Graph>
+inline bool is_undirected_graph(Graph const& g)
+{ return !is_directed<Graph>::value; }
+//@}
+
+/** @name Has Parallels Edges Trait
+ * Determine if the graph allows parallel edges. There are two ways that this
+ * can be checked: either by the edge store or the policy.
  */
+//@{
+template <typename Graph>
+struct has_parallel_edges
+{
+    typedef typename boost::mpl::if_<
+            is_directed<Graph>,
+            detail::directed_parallel<Graph>,
+            detail::undirected_parallel<Graph>
+        >::type test;
+
+    BOOST_STATIC_CONSTANT(bool, value = test::value);
+};
+
 template <typename Graph>
-bool is_simple_graph(const Graph& g)
-{ return is_simple<Graph>::value; }
+inline bool allows_parallel_edges(const Graph& g)
+{ return has_parallel_edges<Graph>::value; }
+//@}
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -4,10 +4,7 @@
 
 #include "none.hpp"
 
-#include "descriptor.hpp"
-
 #include "undirected_vertex.hpp"
-#include "vertex_iterator.hpp"
 #include "vertex_vector.hpp"
 #include "vertex_list.hpp"
 #include "vertex_set.hpp"
@@ -147,13 +144,41 @@
     vertex_key const& key(vertex_descriptor) const;
     //@{
 
-    /** @name Edge Set
-     * These functions operate on the edges of the graph. This functions
-     * include the ability to add and remove edges.
+    /** @name Add Edge
+     * Add an edge, connecting two vertices, to the graph. There are a number of
+     * variations of this function, depending on the type of vertex store and
+     * whether or not the edges are labeled. Convenience functions are provided
+     * for graphs with UniqueVertices. Graphs with LabeledEdges can be added
+     * with edge properties. Convenience functions are equivalent to the
+     * expression add_edge(find_vertex(x), find_vertex(y), p) with x and y
+     * eithe vertex proeprties or vertex keys and p optional edge properties.
+     *
+     * ExtendableEdgeSet        add_edge(vertex_descriptor, vertex_descriptor)
+     *   && LabeledEdges        add_edge(vertex_descriptor, vertex_descriptor, edge_properties)
+     *
+     * LabeledUniqueVertices    add_edge(vertex_properties, vertex_properties)
+     *   && LabeledEdges        add_edge(vertex_properties, vertex_properties, edge_properties)
+     *
+     * MappedUniqueVertices     add_edge(vertex_key, vertex_key)
+     *   & LabeledEdges         add_edge(vertex_key, vertex_key, edge_properties)
      */
     //@{
+    // Unlabeled edge adders.
     edge_descriptor add_edge(vertex_descriptor, vertex_descriptor);
+    edge_descriptor add_edge(vertex_properties const&, vertex_properties const&);
+    edge_descriptor add_edge(vertex_key const&, vertex_key const&);
+
+    // Labeled edge adders.
     edge_descriptor add_edge(vertex_descriptor, vertex_descriptor, edge_properties const&);
+    edge_descriptor add_edge(vertex_properties const&, vertex_properties const&, edge_properties const&);
+    edge_descriptor add_edge(vertex_key const&, vertex_key const&, edge_properties const&);
+    //@}
+
+    /** @name Remove Edge(s)
+     * These functions operate on the edges of the graph. This functions
+     * include the ability to add and remove edges.
+     */
+    //@{
     void remove_edge(edge_descriptor);
     void remove_edges(vertex_descriptor, vertex_descriptor);
     //@}
@@ -433,6 +458,56 @@
 }
 
 /**
+ * Add an edge to the graph that connects the two vertices identified by the
+ * given properties. The edge is either unlabeled or has default properties.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
+undirected_graph<VP,EP,VS,ES>::add_edge(vertex_properties const& u,
+                                        vertex_properties const& v)
+{
+    return add_edge(u, v, edge_properties());
+}
+
+/**
+ * Add an edge to the graph that connects the two vertices identified by the
+ * given properties and has the given edge properties.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
+undirected_graph<VP,EP,VS,ES>::add_edge(vertex_properties const& u,
+                                        vertex_properties const& v,
+                                        edge_properties const& ep)
+{
+    return add_edge(find_vertex(u), find_vertex(v), ep);
+}
+
+/**
+ * Add an edge to the graph that connects the two vertices identified by the
+ * given keys. The edge is either unlabeled or has default properties.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
+undirected_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
+                                        vertex_key const& v)
+{
+    return add_edge(u, v, edge_properties());
+}
+
+/**
+ * Add an edge to the graph that connects the two vertices identified by the
+ * given keys and has the given edge properties.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
+undirected_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
+                                        vertex_key const& v,
+                                        edge_properties const& ep)
+{
+    return add_edge(find_vertex(u), find_vertex(v), ep);
+}
+
+/**
  * Remove only the given edge from graph. This disconnects both vertices in
  * the edge and removes the property from the graph.
  *
@@ -626,7 +701,5 @@
 
 #undef BOOST_GRAPH_UG_PARAMS
 
-#include "traits.hpp"
-
 #endif
 

Copied: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp (from r46477, /sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -1,6 +1,6 @@
 
-#ifndef DESCRIPTOR_HPP
-#define DESCRIPTOR_HPP
+#ifndef VERTEX_DESCRIPTOR_HPP
+#define VERTEX_DESCRIPTOR_HPP
 
 // Important notes about descriptors
 //
@@ -30,52 +30,79 @@
 // us to differentiate descriptors based on these types rather than their
 // simple descriptor types.
 
+namespace detail
+{
+    inline std::size_t invalid_value(std::size_t)
+    { return std::size_t(-1); }
+
+    void* invalid_value(void*)
+    { return 0; }
+}
+
+/**
+ * The basic vertex descriptor is a wrapper around an opaque reference to a
+ * vertex. This class is provided to get around overload problems for functions
+ * taking properties or keys when the types of those objects are the same as
+ * the underlying descriptor.
+ */
 template <typename D>
 class basic_vertex_descriptor
 {
 public:
     inline basic_vertex_descriptor()
-        : desc()
+        : _d(detail::invalid_value(D()))
+    { }
+
+    inline basic_vertex_descriptor(basic_vertex_descriptor const& x)
+        : _d(x._d)
     { }
 
-    inline basic_vertex_descriptor(D d)
-        : desc(d)
+    inline basic_vertex_descriptor(D const& d)
+        : _d(d)
     { }
 
     // Assignment copy.
     inline basic_vertex_descriptor& operator=(basic_vertex_descriptor const& d)
     {
-        desc = d.desc;
+        _d = d._d;
         return *this;
     }
 
     // value-type assignment.
     inline basic_vertex_descriptor& operator=(D d)
     {
-        desc = d;
+        _d = d;
         return *this;
     }
 
-    // Just to make the access a little prettier.
+    /** Get the underlying descriptor value. */
     inline D get() const
-    { return desc; }
+    { return _d; }
 
-    // Provides an implicit cast to bool. Returns true if the basic_vertex_descriptor
-    // is not the same as its default value.
+    /** Returns true if the descriptor is valid. */
     inline bool is_valid() const
-    { return desc != basic_vertex_descriptor().desc; }
+    { return _d != detail::invalid_value(D()); }
 
-    inline bool operator<(basic_vertex_descriptor const& d) const
-    { return desc < d.desc; }
+private:
+    D _d;
+};
 
-    inline bool operator==(basic_vertex_descriptor const& d) const
-    { return desc == d.desc; }
+template <typename D>
+bool
+operator<(basic_vertex_descriptor<D> const& a, basic_vertex_descriptor<D> const& b)
+{ return a.get() < b.get(); }
+
+template <typename D>
+inline bool
+operator==(basic_vertex_descriptor<D> const& a, basic_vertex_descriptor<D> const& b)
+{ return a.get() == b.get(); }
+
+template <typename D>
+inline bool
+operator!=(basic_vertex_descriptor<D> const& a, basic_vertex_descriptor<D> const& b)
+{ return a.get() != b.get(); }
 
-    inline bool operator!=(basic_vertex_descriptor const& d) const
-    { return desc != d.desc; }
 
-    D desc;
-};
 
 #endif
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -4,7 +4,8 @@
 
 #include <list>
 
-#include "descriptor.hpp"
+#include "vertex_descriptor.hpp"
+#include "vertex_iterator.hpp"
 
 // Forward declarations
 template <typename V, template <typename> class A> class vertex_list_elem;
@@ -22,7 +23,7 @@
 struct basic_vertex_list
 {
     typedef unused key_type;
-    typedef void* descriptor_type;
+    typedef basic_vertex_descriptor<void*> descriptor_type;
 
     template <typename Vertex>
     struct store
@@ -59,15 +60,17 @@
 };
 
 /**
+ * The implementation of the vertex list.
  *
- * FIXME: Track the size of the list, so that num_vertices() is constant.
+ * @param Vertex The type of stored vertex.
+ * @param Alloc The allocator for stored vertices.
  */
-template <typename Vertex, typename Allocator>
+template <typename Vertex, typename Alloc>
 class vertex_list_impl
 {
-    typedef std::list<Vertex, Allocator> vertex_store;
+    typedef std::list<Vertex, Alloc> vertex_store;
 public:
-    typedef void* vertex_descriptor;
+    typedef basic_vertex_descriptor<void*> vertex_descriptor;
 
     typedef Vertex vertex_type;
     typedef typename Vertex::vertex_properties vertex_properties;
@@ -107,10 +110,10 @@
     /** @name Vertex Accessors */
     //@{
     vertex_type& vertex(vertex_descriptor v)
-    { return *static_cast<vertex_type*>(v); }
+    { return *static_cast<vertex_type*>(v.get()); }
 
     vertex_type const& vertex(vertex_descriptor v) const
-    { return *static_cast<vertex_type*>(v); }
+    { return *static_cast<vertex_type*>(v.get()); }
     //@}
 
     /** @name Vertex Properties */
@@ -194,7 +197,7 @@
 vertex_list_impl<V,A>::remove(vertex_descriptor v)
 {
     --_size;
-    vertex_type* vp = static_cast<vertex_type*>(v);
+    vertex_type* vp = static_cast<vertex_type*>(v.get());
     _verts.erase(vp->iter);
 }
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -4,6 +4,9 @@
 
 #include <map>
 
+#include "vertex_descriptor.hpp"
+#include "vertex_iterator.hpp"
+
 // Forward declarations
 template <typename, typename, typename, template <typename> class> class vertex_map_elem;
 template <typename, typename, typename, typename> class vertex_map_impl;
@@ -32,7 +35,7 @@
 struct basic_vertex_map
 {
     typedef Key key_type;
-    typedef void* descriptor_type;
+    typedef basic_vertex_descriptor<void*> descriptor_type;
 
     template <typename Vertex>
     struct store
@@ -97,7 +100,7 @@
 {
     typedef std::map<Key, Vertex, Compare, Allocator> vertex_store;
 public:
-    typedef void* vertex_descriptor;
+    typedef basic_vertex_descriptor<void*> vertex_descriptor;
 
     typedef Vertex vertex_type;
     typedef typename Vertex::vertex_properties vertex_properties;
@@ -140,10 +143,10 @@
     /** @name Vertex Accessors */
     //@{
     vertex_type& vertex(vertex_descriptor v)
-    { return *static_cast<vertex_type*>(v); }
+    { return *static_cast<vertex_type*>(v.get()); }
 
     vertex_type const& vertex(vertex_descriptor v) const
-    { return *static_cast<vertex_type*>(v); }
+    { return *static_cast<vertex_type*>(v.get()); }
     //@}
 
     /** @name Property Accessors */

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -4,6 +4,9 @@
 
 #include <set>
 
+#include "vertex_descriptor.hpp"
+#include "vertex_iterator.hpp"
+
 // Forward declarations
 template <typename, template <typename> class, template <typename> class> class vertex_set_elem;
 template <typename, typename> class vertex_set_compare;
@@ -28,7 +31,7 @@
 struct basic_vertex_set
 {
     typedef unused key_type;
-    typedef void* descriptor_type;
+    typedef basic_vertex_descriptor<void*> descriptor_type;
 
     template <typename Vertex>
     struct store
@@ -119,7 +122,7 @@
 {
     typedef std::set<Vertex, Compare, Allocator> vertex_store;
 public:
-    typedef void* vertex_descriptor;
+    typedef basic_vertex_descriptor<void*> vertex_descriptor;
 
     typedef Vertex vertex_type;
     typedef typename Vertex::vertex_properties vertex_properties;
@@ -159,10 +162,10 @@
     /** @name Vertex Accessors */
     //@{
     vertex_type& vertex(vertex_descriptor v)
-    { return *static_cast<vertex_type*>(v); }
+    { return *static_cast<vertex_type*>(v.get()); }
 
     vertex_type const& vertex(vertex_descriptor v) const
-    { return *static_cast<vertex_type*>(v); }
+    { return *static_cast<vertex_type*>(v.get()); }
     //@}
 
     /** @name Property Accessors */

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp	2008-06-20 08:53:23 EDT (Fri, 20 Jun 2008)
@@ -5,6 +5,9 @@
 #include <vector>
 #include <algorithm>
 
+#include "vertex_descriptor.hpp"
+#include "vertex_iterator.hpp"
+
 // Forward declarations
 template <typename V, typename A> struct vertex_vector_impl;
 
@@ -22,7 +25,7 @@
 struct basic_vertex_vector
 {
     typedef unused key_type;
-    typedef std::size_t descriptor_type;
+    typedef basic_vertex_descriptor<std::size_t> descriptor_type;
 
     // The store metafunction generates the type used to store vertices in
     // either a directed or undirected graph. This metafunction takes the
@@ -58,7 +61,7 @@
 {
     typedef std::vector<Vertex, Allocator> vertex_store;
 public:
-    typedef std::size_t vertex_descriptor;
+    typedef basic_vertex_descriptor<std::size_t> vertex_descriptor;
 
     typedef Vertex vertex_type;
     typedef typename Vertex::vertex_properties vertex_properties;
@@ -100,10 +103,10 @@
     /** @name Vertex Accessors */
     //@{
     vertex_type& vertex(vertex_descriptor v)
-    { return _verts[v]; }
+    { return _verts[v.get()]; }
 
     vertex_type const& vertex(vertex_descriptor v) const
-    { return _verts[v]; }
+    { return _verts[v.get()]; }
     //@{
 
     /** @name Property Accessors */