[Boost-commit] svn:boost r49849 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost/graphs include/boost/graphs/adjacency_list include/boost/graphs/adjacency_list/es include/boost/graphs/adjacency_list/vs test

Subject: [Boost-commit] svn:boost r49849 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost/graphs include/boost/graphs/adjacency_list include/boost/graphs/adjacency_list/es include/boost/graphs/adjacency_list/vs test
From: asutton_at_[hidden]
Date: 2008-11-20 10:32:47

Author: asutton
Date: 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
New Revision: 49849
URL: http://svn.boost.org/trac/boost/changeset/49849

Log:
Started rewriting the edge store for undirected graphs
Added:
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/association.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/sequence.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/edge.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge_store.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_edge.hpp |   171 ++++++++++++--------------------------- 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp    |   139 ++++++++++++++++++++-----------         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp         |     6 -                                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp          |     9 +                                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp          |     4                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp       |     6 -                                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp                          |    19 ---                                     
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt                                     |     2                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp                                   |    61 ++++++++-----                           
   9 files changed, 192 insertions(+), 225 deletions(-)

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,95 @@
+
+#ifndef BOOST_GRAPH_ADJLIST_EDGE_STORE_TRAITS_HPP
+#define BOOST_GRAPH_ADJLIST_EDGE_STORE_TRAITS_HPP
+
+#include <boost/concept_check.hpp>
+
+#include <boost/containers.hpp>
+#include <boost/descriptors.hpp>
+
+#include <boost/graphs/label.hpp>
+#include <boost/graphs/edge.hpp>
+
+// Include specializations for the label and edge interfaces.
+#include <boost/graphs/adjacency_list/es/sequence.hpp>
+#include <boost/graphs/adjacency_list/es/association.hpp>
+
+// The edge store interface defines generic operations on an edge store for
+// undirected graphs.
+
+// NOTE: Directed graphs do not use a global edge store. They use out and in
+// edge stores and have a completely different interface.
+
+// TODO: There is a significant overlap between the sequence selectors for
+// vertex and edge stores. These could easily be integrated into a kind of
+// general purpose selector mechanism. For now, they're separate.
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+template <typename Store>
+struct edge_store_traits
+{
+    typedef typename Store::value_type edge_type;
+};
+
+namespace es {
+
+namespace detail {
+    template <typename Store, typename Ends, typename Label>
+    inline typename edge_store_traits<Store>::edge_type
+    make_edge(Store const&, Ends e, Label&& l)
+    { return typename edge_store_traits<Store>::edge_type(e, l); }
+
+    template <typename Store, typename Ends, typename Label>
+    inline typename Store::iterator
+    dispatch_insert(Store& store, Ends e, Label&& l, sequence_tag)
+    { return store.insert(store.end(), make_edge(store, e, l)); }
+
+    // This re-orders the endpoints before inerting in order to guarantee a
+    // canonical ordering edges, and preserving uniqueness, if required.
+    // TODO: Is there a way to convert Comp<pair<VD,VD>> to Comp<VD>? Yeah, but
+    // it's kind of nasty and uses template template parameters.
+    template <typename Store, typename Ends, typename Label>
+    inline typename Store::iterator
+    dispatch_insert(Store& store, Ends e, Label&& l, pair_associative_container_tag)
+    {
+        if(!(e.first < e.second)) swap(e.first, e.second);
+        return container_insert(store, make_edge(store, e, l));
+    }
+}
+
+/** Insert . */
+template <typename Store, typename Ends, typename Label>
+inline typename descriptor_traits<Store>::descriptor_type
+insert(Store& store, Ends e, Label&& l)
+{ return make_descriptor(store, detail::dispatch_insert(store, e, l, container_category(store))); }
+
+/** Return the number of edges in the edge store. */
+template <typename Store>
+typename Store::size_type size(Store const& store)
+{ return store.size(); }
+
+/** @name Edge Label
+ * Return a lable for the given edge.
+ */
+//@{
+template <typename Store>
+inline typename label_traits<typename edge_store_traits<Store>::edge_type>::label_type&
+label(Store& store, typename descriptor_traits<Store>::descriptor_type d)
+{ return graphs::label(*make_iterator(store, d)); }
+
+template <typename Store>
+inline typename label_traits<typename edge_store_traits<Store>::edge_type>::label_type const&
+label(Store const& store, typename descriptor_traits<Store>::descriptor_type d)
+{ return graphs::label(*make_iterator(store, d)); }
+//@}
+
+} /* namespace es */
+
+} } } /* namespace boost::graphs::adjacency_list */
+
+// Type selectors
+#include <boost/graphs/adjacency_list/es/vector.hpp>
+#include <boost/graphs/adjacency_list/es/set.hpp>
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/association.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/association.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,38 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_ES_ASSOCIATION_HPP
+#define BOOST_GRAPHS_ADJLIST_ES_ASSOCIATION_HPP
+
+namespace boost { namespace graphs {
+
+// Specializations to support labels for undirected edges for edge vectors,
+// and lists.
+
+template <typename VertexDesc, typename EdgeLabel>
+struct label_traits<std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel>>
+{
+    typedef EdgeLabel label_type;
+};
+
+template <typename VertexDesc, typename EdgeLabel>
+inline EdgeLabel&
+label(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel>& edge)
+{ return edge.second; }
+
+template <typename VertexDesc, typename EdgeLabel>
+inline EdgeLabel const&
+label(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel> const& edge)
+{ return edge.second; }
+
+// Specializations of the edge interface for edge sequences (vectors and lists).
+
+// NOTE: I'm un-consting the key type for an associative container. Will this
+// cause problems later? Possibly.
+template <typename VertexDesc, typename EdgeLabel>
+struct edge_traits<std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel>>
+{
+    typedef std::pair<VertexDesc, VertexDesc> end_pair;
+};
+
+} } /* namespace boost::graphs */
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/sequence.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/sequence.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,41 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_ES_SEQUENCE_HPP
+#define BOOST_GRAPHS_ADJLIST_ES_SEQUENCE_HPP
+
+namespace boost { namespace graphs {
+
+// Specializations to support labels for undirected edges for edge vectors,
+// and lists.
+
+// TODO: I'm a little worried about the possibility of type collisions with
+// directed graphs. It would be nice if I could specialize on an extra piece
+// of information here. Also, the difference between this and associative
+// specializations is the const-ness of the ends.
+
+template <typename VertexDesc, typename EdgeLabel>
+struct label_traits<std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel>>
+{
+    typedef EdgeLabel label_type;
+};
+
+template <typename VertexDesc, typename EdgeLabel>
+inline EdgeLabel&
+label(std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel>& edge)
+{ return edge.second; }
+
+template <typename VertexDesc, typename EdgeLabel>
+inline EdgeLabel const&
+label(std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel> const& edge)
+{ return edge.second; }
+
+// Specializations of the edge interface for edge sequences (vectors and lists).
+
+template <typename VertexDesc, typename EdgeLabel>
+struct edge_traits<std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel>>
+{
+    typedef std::pair<VertexDesc, VertexDesc> end_pair;
+};
+
+} } /* namespace boost::graphs */
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,40 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_ES_SET_HPP
+#define BOOST_GRAPHS_ADJLIST_ES_SET_HPP
+
+#include <map>
+
+#include <boost/graphs/edge.hpp>
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+
+/**
+ * @param Compare A unary template class that compares the ends of edges. The
+ * argument type for this function is Pair<VertexDesc, VertexDesc>.
+ * @param Alloc A unary template class that allocates edges.
+ */
+template <
+    template <typename> class Compare = std::less,
+    template <typename> class Alloc = std::allocator>
+struct edge_set
+{
+    typedef typename descriptor_traits<
+        std::set<int, Compare<int>, Alloc<int>>
+    >::descriptor_type edge_descriptor;
+
+    // This quietly implements a map, not a set because we'll be using the
+    // endpoints as keys to the label.
+    template <typename Ends, typename Label>
+    struct edge_store
+    {
+        typedef Compare<Ends> compare;
+        typedef Alloc<std::pair<Ends, Label>> allocator;
+    public:
+        typedef std::map<Ends, Label, compare, allocator> type;
+    };
+};
+
+} } } /* namespace boost::graphs::adjacency_list */
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,33 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_ES_VECTOR_HPP
+#define BOOST_GRAPHS_ADJLIST_ES_VECTOR_HPP
+
+#include <vector>
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+/**
+ * @param Alloc A unary template class that will allocate stored vertices.
+ */
+template <template <typename> class Alloc = std::allocator>
+struct edge_vector
+{
+    typedef typename descriptor_traits<
+        std::vector<int, Alloc<int>>
+    >::descriptor_type edge_descriptor;
+
+    // Ends must be a pair of vertices.
+    template <typename Ends, typename Label>
+    struct edge_store
+    {
+    private:
+        typedef std::pair<Ends, Label> edge;
+        typedef Alloc<edge> allocator;
+    public:
+        typedef std::vector<edge, allocator> type;
+    };
+};
+
+} } } /* namespace boost::graphs::adjacency_list */
+
+#endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_edge.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_edge.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -4,114 +4,81 @@
 
 #include <iosfwd>
 
-#include <boost/unordered_pair.hpp>
-#include <boost/graphs/directional_edge.hpp>
+#include <boost/functional/hash.hpp>
+
+#include <boost/graphs/edge.hpp>
 
 namespace boost { namespace graphs { namespace adjacency_list {
 
 /**
- * This structure implements an unordered edge - sort of. Because the undirected
- * adjacency list class doesn't ever store a concrete edge type, this edge
- * type simply aggregates descriptors in such a way that it defines an edge.
- * This means that this class can also act (and does) as a descriptor itself.
+ * This structure implements an undirected edge. An undirected edge maintains
+ * a pair of vertices and an edge label.
  */
-template <typename VertexDesc, typename PropDesc>
+template <typename EdgeLabel, typename VertexDesc>
 class undirected_edge
 {
 public:
+    typedef EdgeLabel label_type;
+
     typedef VertexDesc vertex_descriptor;
-    typedef PropDesc label_descriptor;
-    typedef unordered_pair<vertex_descriptor> edge_pair;
+    typedef std::pair<vertex_descriptor, vertex_descriptor> ends_pair;
 
     /** @name Constructors */
     //@{
-    inline undirected_edge()
+    undirected_edge()
         : _ends(), _label()
     { }
 
-    inline undirected_edge(vertex_descriptor u, vertex_descriptor v, label_descriptor p)
-        : _ends(u, v), _label(p)
+    undirected_edge(vertex_descriptor u, vertex_descriptor v,  label_type const& l)
+        : _ends(u, v), _label(l)
     { }
 
-    inline undirected_edge(std::pair<vertex_descriptor, vertex_descriptor> const& e, label_descriptor p)
-        : _ends(e.first, e.second), _label(p)
+    undirected_edge(ends_pair const& e, label_type const& l)
+        : _ends(e.first, e.second), _label(l)
     { }
-
-    inline undirected_edge(unordered_pair<vertex_descriptor, vertex_descriptor> const& e, label_descriptor p)
-        : _ends(e), _label(p)
-    { }
-    //@}
-
-    /** @name Descriptor-like Functions
-     * These allow you to treat the edge descriptor like a typical descriptor.
-     * That is, it can be tested for null status (which defers to the _labelerty
-     * descriptor).
-     */
-    //@{
-    inline bool is_null() const
-    { return _label.is_null(); }
-
-    inline operator bool() const
-    { return !is_null(); }
-    //@}
-
-    inline label_descriptor label() const
-    { return _label; }
-
-    inline edge_pair const& edge() const
-    { return _ends; }
-
-    /** @name End Points
-     * Provide access to the end points of the undirected edge. Because the
-     * _ends of this edge are unordered, they do not provide a source and target
-     * interface. See the rooted_undirected_edge class for a variant of this
-     * type that imposes a source/target interface on these edges.
-     */
-    //@{
-    inline vertex_descriptor first() const
-    { return _ends.first(); }
-
-    inline vertex_descriptor second() const
-    { return _ends.second(); }
-
-    inline vertex_descriptor opposite(vertex_descriptor v) const
-    { return v == first() ? second() : first(); }
-    //@}
-
-    /** Return true if the edge connects the two vertices. */
-    inline bool connects(vertex_descriptor u, vertex_descriptor v) const
-    { return make_unordered_pair(u, v) == _ends; }
-
-
-    /** @name Equality Comparable */
-    //@{
-    inline bool operator==(undirected_edge const& x) const
-    { return (_ends == x._ends) && (_label == x._label); }
-
-    inline bool operator!=(undirected_edge const& x) const
-    { return !operator==(x); }
     //@}
 
-    /** @name Less Than Comparable */
-    //@{
-    inline bool operator<(undirected_edge const& x) const
-    { return std::make_pair(_ends, _label) < std::make_pair(x._ends < x._label); }
-
-    inline bool operator>(undirected_edge const& x) const
-    { return x.operator<(*this); }
+    label_type& label()                 { return _label; }
+    label_type const& label() const     { return _label; }
 
-    inline bool operator<=(undirected_edge const& x) const
-    { return !x.operator<(*this); }
-
-    inline bool operator>=(undirected_edge const& x) const
-    { return !operator<(x); }
-    //@}
+    ends_pair const& ends() const       { return _ends; }
 
 private:
-    edge_pair           _ends;
-    label_descriptor    _label;
+    ends_pair       _ends;
+    label_type      _label;
 };
 
+/** @name Equality Comparable */
+//@{
+template <typename L, typename VD>
+inline bool operator==(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return (a.ends() == b.ends()) && (a.label() == b.label()); }
+
+template <typename L, typename VD>
+inline bool operator!=(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return !(a == b); }
+//@}
+
+/** @name Less Than Comparable */
+//@{
+template <typename L, typename VD>
+inline bool operator<(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return std::make_pair(a.ends(), a.label()) < std::make_pair(b.ends(), b.label()); }
+
+template <typename L, typename VD>
+inline bool operator>(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return b < a; }
+
+template <typename L, typename VD>
+inline bool operator<=(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return !(b < a); }
+
+template <typename L, typename VD>
+inline bool operator>=(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return !(a < b); }
+//@}
+
+
 template <typename V, typename P>
 std::ostream& operator<<(std::ostream& os, undirected_edge<V,P> const& e)
 { return os << "{" << e.first() << " " << e.second() << "}"; }
@@ -124,10 +91,7 @@
 template <typename V, typename P>
 inline std::size_t
 hash_value(undirected_edge<V,P> const& e)
-{
-    using boost::hash;
-    return hash_value(e.label());
-}
+{ return hash_value(e.label()); }
 
 /**
  * The undirected edge iterator simply wraps the iterator over the global edge
@@ -199,37 +163,6 @@
     iterator    iter;
 };
 
-} /* namespace adjacency_list */
-
-namespace detail
-{
-    // Provide an implementation of directionality for undirected edges.
-    template <typename Vert, typename Prop>
-    struct directional_edge_adapter<adjacency_list::undirected_edge<Vert,Prop>>
-        : adjacency_list::undirected_edge<Vert,Prop>
-    {
-        inline directional_edge_adapter()
-            : adjacency_list::undirected_edge<Vert, Prop>(), src()
-        { }
-
-        inline directional_edge_adapter(adjacency_list::undirected_edge<Vert,Prop> e, Vert s)
-            : adjacency_list::undirected_edge<Vert,Prop>(e), src(s)
-        { }
-
-        inline directional_edge_adapter(Vert s, Vert t)
-            : adjacency_list::undirected_edge<Vert,Prop>(s, t), src(s)
-        { }
-
-        inline Vert source() const
-        { return src; }
-
-        inline Vert target() const
-        { return this->opposite(src); }
-
-        Vert src;
-    };
-}
-
-} } /* namespace boost::graphs */
+} } } /* namespace boost::graphs::adjacency_list */
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -8,23 +8,22 @@
 #include <boost/descriptors.hpp>
 
 #include <boost/graphs/label.hpp>
-#include <boost/graphs/adjacency_list/vs/vector.hpp>
 
 // The Vertex Store defines the generic interface for working with a vertex
 // set for both directed and undirected adjacency lists. Its primary goal is
 // to provide generic interfaces that abstract common operations on these
 // sets. Important kinds of types are:
 // - Store - the selected container. Must model Container.
-// - Iterator - a non-const iterator into the store.
+// - Descriptor - a descriptor into the store
+// - Result - pair<Descriptor, bool>
 // - Size - the size type of the container
 // - Vertex - a type of vertex. Can be labelled.
 // - Label - a vertex label
 // - Key - a key maapping to a vertex.
-// - Result - pair<Iterator, bool>
 //
 // Supported operations are:
-// - Iterator   vs_add_vertex       (Store, Vertex)
-// - Iterator   vs_add_vertex       (Store, Key, Vertex)
+// - Descriptor vs_add_vertex       (Store, Vertex)
+// - Descriptor vs_add_vertex       (Store, Key, Vertex)
 // - Result     vs_try_add_vertex   (Store, Vertex)
 // - Result     vs_try_add_vertex   (Store, Key, Vertex)
 // - Iterator   vs_find_vertex      (Store, Label)
@@ -34,30 +33,25 @@
 
 namespace boost { namespace graphs { namespace adjacency_list {
 
-namespace detail
+/**
+ * The vertex_store_traits relates associated types with a kind of vertex store.
+ * Mostly, this is useful in cases where we have to get the vertex type from
+ * simple and pair associative containers.
+ */
+template <typename Store>
+struct vertex_store_traits
 {
-    // Try to add the vertex to an associative container. This is a simple
-    // delegation to the container.
-    template <typename Store, typename Vertex>
-    inline std::pair<typename Store::iterator, bool>
-    dispatch_vs_try_add(Store& store, Vertex&& v, associative_container_tag)
-    { return store.insert(v); }
+    typedef typename Store::value_type vertex_type;
+};
 
-    // Try to add the vertex to a sequential container. Here, we want to search
-    // for the vertex (linear time operation) and either insert at the end
-    // or return an existing iterator.
-    template <typename Store, typename Vertex>
-    inline std::pair<typename Store::iterator, bool>
-    dispatch_vs_try_add(Store& store, Vertex&& v, sequence_tag)
-    {
-        typename Store::iterator i = vs_find_vertex(store, label(v));
-        return std::make_pair(i, i == store.end());
-    }
+namespace vs {
+
+namespace detail {
 
     // Iterate and compare for sequences.
     template <typename Store, typename Label>
     inline typename Store::iterator
-    dispatch_vs_find(Store& store, Label const& l, sequence_tag)
+    dispatch_find(Store& store, Label const& l, sequence_tag)
     {
         return std::find_if(
             store.begin(),
@@ -69,20 +63,38 @@
     // have to use the basic find command.
     template <typename Store, typename Label>
     inline typename Store::iterator
-    dispatch_vs_find(Store& store, Label const& l, associative_container_tag)
+    dispatch_find(Store& store, Label const& l, associative_container_tag)
     { return store.find(l); }
 
+
+    // Try to add the vertex to an associative container. This is a simple
+    // delegation to the container.
+    template <typename Store, typename Vertex>
+    inline std::pair<typename Store::iterator, bool>
+    dispatch_try_insert(Store& store, Vertex&& v, associative_container_tag)
+    { return store.insert(v); }
+
+    // Try to add the vertex to a sequential container. Here, we want to search
+    // for the vertex (linear time operation) and either insert at the end
+    // or return an existing iterator.
+    template <typename Store, typename Vertex>
+    inline std::pair<typename Store::iterator, bool>
+    dispatch_try_insert(Store& store, Vertex&& v, sequence_tag)
+    {
+        typename Store::iterator i = dispatch_find(store, label(v), sequence_tag());
+        return std::make_pair(i, i == store.end());
+    }
+
     // Explicitly remove the ability use this function, by failing a concept
     // check when it is instantiated.
     template <typename Store>
-    void dispatch_vs_remove(Store&, typename Store::iterator, vector_tag)
+    void dispatch_remove(Store&, typename Store::iterator, vector_tag)
     { function_requires(Integer<Store>()); }
 
     template <typename Store, typename Tag>
-    void dispatch_vs_remove(Store& store, typename Store::iterator i, Tag)
+    void dispatch_remove(Store& store, typename Store::iterator i, Tag)
     { store.erase(i); }
 
-
 } /* namespace detail */
 
 /** @name Add Vertex
@@ -93,15 +105,15 @@
 //@{
 /** Insert a vertex into the container. */
 template <typename Store, typename Vertex>
-inline typename Store::iterator
-vs_add_vertex(Store& store, Vertex&& v)
-{ return container_insert(store, v); }
+inline typename descriptor_traits<Store>::descriptor_type
+insert(Store& store, Vertex&& v)
+{ return make_descriptor(store, container_insert(store, v)); }
 
 /** Insert a vertex into the container, mapped to the given key. */
 template <typename Store, typename Key, typename Vertex>
-inline typename Store::iterator
-vs_add_vertex(Store& store, Key const& k, Vertex&& v)
-{ return container_insert(store, std::make_pair(k, v)); }
+inline typename descriptor_traits<Store>::descriptor_type
+insert(Store& store, Key const& k, Vertex&& v)
+{ return make_descriptor(store, container_insert(store, std::make_pair(k, v))); }
 //@}
 
 /** @name Try to Add Vertex
@@ -112,35 +124,47 @@
  */
 //@{
 template <typename Store, typename Vertex>
-inline std::pair<typename Store::iterator, bool>
-vs_try_add_vertex(Store& store, Vertex&& v)
-{ return detail::dispatch_vs_try_add(store, v, container_category(store)); }
+inline std::pair<typename descriptor_traits<Store>::descriptor_type, bool>
+try_insert(Store& store, Vertex&& v)
+{
+    std::pair<typename Store::iterator, bool> x =
+        detail::dispatch_try_insert(store, v, container_category(store));
+    return std::make_pair(make_descriptor(store, x.first), x.second);
+}
 
 // There are no mapped linear sequences, so we can just rely on the fact that
 // this is a pair associative container. In fact, this actually requires that
 // Store model the UniqueAssociativeContainer concept.
 template <typename Store, typename Key, typename Vertex>
-inline std::pair<typename Store::iterator, bool>
-vs_try_add_vertex(Store& store, Key const& k, Vertex&& v)
-{ return store.insert(std::make_pair(k, v)); }
+inline std::pair<typename descriptor_traits<Store>::descriptor_type, bool>
+try_insert(Store& store, Key const& k, Vertex&& v)
+{
+    std::pair<typename Store::iterator, bool> x =
+        store.insert(std::make_pair(k, v));
+    return std::make_pair(make_descriptor(store, x.first), x.second);
+}
 //@}
 
 /** @name Find Vertex
  * Return an iterator to the vertex that matches the given label. This is
  * only applicable to labelled vertex types. The returned iterator will be
  * equivalent to store.end() if no such vertex is found.
+ *
+ * If the store is a pair associative container (e.g., map), then this function
+ * will find the vertex mapped to the given key. Otherwise, it tries to find
+ * the vertex with the given label.
  */
 //@{
-template <typename Store, typename Label>
-inline typename Store::iterator
-vs_find_vertex(Store& store, Label const& l)
-{ return detail::dispatch_vs_find(store, l, container_category(store)); }
+template <typename Store, typename LabelOrKey>
+inline typename descriptor_traits<Store>::descriptor_type
+find(Store& store, LabelOrKey const& lk)
+{ return make_descriptor(store, detail::dispatch_find(store, lk, container_category(store))); }
 
 // Does not return a const iterator!
-template <typename Store, typename Label>
-inline typename Store::iterator
-vs_find_vertex(Store const& store, Label const& l)
-{ return detail::dispatch_vs_find(const_cast<Store&>(store), l, container_category(store)); }
+template <typename Store, typename LabelOrKey>
+inline typename descriptor_traits<Store>::descriptor_type
+find(Store const& store, LabelOrKey const& lk)
+{ return find(const_cast<Store&>(store), lk, container_category(store)); }
 //@}
 
 /**
@@ -150,20 +174,33 @@
  */
 //@{
 template <typename Store>
-void vs_remove_vertex(Store& store, typename Store::iterator i)
-{ detail::dispatch_vs_remove(store, i, container_category(store)); }
+void remove(Store& store, typename descriptor_traits<Store>::descriptor_type d)
+{ detail::dispatch_remove(store, make_iterator(store, d), container_category(store)); }
 //@}
 
 /** Return the number of elements in the vertex store. */
 template <typename Store>
-typename Store::size_type vs_size(Store const& store)
+typename Store::size_type size(Store const& store)
 { return store.size(); }
 
 /** Return true if the store is empty. */
 template <typename Store>
-bool vs_empty(Store const& store)
+bool empty(Store const& store)
 { return store.empty(); }
 
+/** Clear the vertex store. */
+template <typename Store>
+void clear(Store& store)
+{ store.clear(); }
+
+} /* namespace vs */
+
 } } } /* namespace boost::graphs::adjacency_list */
 
+// Include type selectors for the different vertex store implementations
+#include <boost/graphs/adjacency_list/vs/vector.hpp>
+#include <boost/graphs/adjacency_list/vs/list.hpp>
+#include <boost/graphs/adjacency_list/vs/set.hpp>
+#include <boost/graphs/adjacency_list/vs/map.hpp>
+
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -2,11 +2,7 @@
 #ifndef BOOST_GRAPHS_ADJLIST_VS_LIST_HPP
 #define BOOST_GRAPHS_ADJLIST_VS_LIST_HPP
 
-#include <list>
-
-#include <boost/none.hpp>
 #include <boost/counted_list.hpp>
-#include <boost/graphs/adjacency_list/vertex_store.hpp>
 
 namespace boost { namespace graphs { namespace adjacency_list {
 
@@ -16,7 +12,7 @@
 template <template <typename> class Alloc = std::allocator>
 struct vertex_list
 {
-    typedef unused key_type;
+    typedef void key_type;
 
     typedef typename descriptor_traits<
         std::list<int, Alloc<int>>

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -5,7 +5,6 @@
 #include <map>
 
 #include <boost/none.hpp>
-#include <boost/graphs/adjacency_list/vertex_store.hpp>
 
 namespace boost { namespace graphs { namespace adjacency_list {
 
@@ -35,6 +34,14 @@
     };
 };
 
+// Specialize the vertex store traits to refer to the mapped type instead
+// of the value type.
+template <typename Key, typename Value, typename Compare, typename Alloc>
+struct vertex_store_traits<std::map<Key, Value, Compare, Alloc>>
+{
+    typedef typename std::map<Key, Value, Compare, Alloc>::mapped_type vertex_type;
+};
+
 } } } /* namespace boost::graphs::adjacency_list */
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -4,9 +4,7 @@
 
 #include <set>
 
-#include <boost/none.hpp>
 #include <boost/graphs/label.hpp>
-#include <boost/graphs/adjacency_list/vertex_store.hpp>
 
 namespace boost { namespace graphs { namespace adjacency_list {
 
@@ -20,7 +18,7 @@
     template <typename> class Alloc = std::allocator>
 struct vertex_set
 {
-    typedef unused key_type;
+    typedef void key_type;
 
     typedef typename descriptor_traits<
         std::set<int, Compare<int>, Alloc<int>>

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -3,10 +3,6 @@
 #define BOOST_GRAPHS_ADJLIST_VS_VECTOR_HPP
 
 #include <vector>
-#include <algorithm>
-
-#include <boost/none.hpp>
-#include <boost/graphs/adjacency_list/vertex_store.hpp>
 
 namespace boost { namespace graphs { namespace adjacency_list {
 
@@ -16,7 +12,7 @@
 template <template <typename> class Alloc = std::allocator>
 struct vertex_vector
 {
-    typedef unused key_type;
+    typedef void key_type;
 
     typedef typename descriptor_traits<
         std::vector<int, Alloc<int>>

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/edge.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/edge.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,24 @@
+
+#ifndef BOOST_GRAPHS_EDGE_HPP
+#define BOOST_GRAPHS_EDGE_HPP
+
+#include <boost/none.hpp>
+
+namespace boost { namespace graphs {
+
+// The edge interface...
+
+/**
+ * The edge traits class provides information about the end points and semantics
+ * of edges, but not their labels.
+ */
+template <typename Edge>
+struct edge_traits
+{
+    typedef typename Edge::end_pair end_pair;
+};
+
+} } /* namespace boost::graphs */
+
+
+#endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -20,32 +20,19 @@
     typedef typename Object::label_type label_type;
 };
 
-/**
- * Metafunction that returns true if the labeled objects type is none. This
- * should actually be significantly better adapted - for example with arbitrary
- * types for which label_traits does not exist.
- */
-template <typename Object>
-struct has_label
-{
-    enum { value = is_same<typename label_traits<Object>::label_type, none>::value };
-};
-
-/**
+/** @name Label Access
  * Return a reference to the object's label. The generic implementation requires
  * the object to have a non-const label() member.
  */
+//@{
 template <typename Object>
 typename label_traits<Object>::label_type& label(Object& x)
 { return x.label(); }
 
-/**
- * Return a const reference to the object's label. The generic implementation
- * requires the object to have a const label() member.
- */
 template <typename Object>
 typename label_traits<Object>::label_type const& label(Object const& x)
 { return x.label(); }
+//@}
 
 /**
  * This is a simple template wrapper for building comparison functors for

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -1,5 +1,5 @@
 
 include_directories(${Graphs_INCLUDE_DIRS} ${Boost_INCLUDE_DIRS})
 
-add_exec(hello hello.cpp)
 add_exec(vertex_store vertex_store.cpp)
+add_exec(edge_store edge_store.cpp)

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge_store.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge_store.cpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,41 @@
+
+#include <iostream>
+#include <string>
+
+#include <boost/graphs/adjacency_list/vertex_store.hpp>
+#include <boost/graphs/adjacency_list/edge_store.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+using namespace boost::graphs;
+using namespace boost::graphs::adjacency_list;
+
+template <typename Store>
+void test()
+{
+    typedef typename edge_store_traits<Store>::edge_type Edge;
+    typedef typename edge_traits<Edge>::end_pair Ends;
+    typedef typename descriptor_traits<Store>::descriptor_type EdgeDesc;
+
+    Store store;
+
+    EdgeDesc e1 = es::insert(store, Ends(0, 1), 0.5);
+    EdgeDesc e2 = es::insert(store, Ends(0, 2), 1.5);
+    BOOST_ASSERT(es::size(store) == 2u);
+    cout << es::label(store, e1) << endl;
+    cout << es::label(store, e2) << endl;
+}
+
+int main()
+{
+    typedef vertex_vector<>::vertex_descriptor VertexDesc;
+    typedef std::pair<VertexDesc, VertexDesc> Ends;
+
+    typedef edge_vector<>::edge_store<Ends, double>::type EV;
+    typedef edge_set<>::edge_store<Ends, double>::type EM;
+
+    test<EV>();
+    test<EM>();
+}

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp	2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -3,14 +3,9 @@
 #include <string>
 
 #include <boost/graphs/adjacency_list/vertex_store.hpp>
-#include <boost/graphs/adjacency_list/vertex_vector.hpp>
-#include <boost/graphs/adjacency_list/vertex_list.hpp>
-#include <boost/graphs/adjacency_list/vertex_set.hpp>
-#include <boost/graphs/adjacency_list/vertex_map.hpp>
 
 #include "typestr.hpp"
 
-
 using namespace std;
 using namespace boost;
 using namespace boost::graphs::adjacency_list;
@@ -44,45 +39,63 @@
 template <typename Store>
 void add_verts(Store& store, simple_container_tag)
 {
-    typedef typename Store::iterator Iterator;
-    typedef typename Store::value_type Vertex;
-    vs_add_vertex(store, Vertex("b"));
-    Iterator iter = vs_add_vertex(store, Vertex("a"));
-
-    vs_remove_vertex(store, iter);
+    typedef typename descriptor_traits<Store>::descriptor_type Descriptor;
+    typedef typename vertex_store_traits<Store>::vertex_type Vertex;
+    vs::insert(store, Vertex("b"));
+    vs::insert(store, Vertex("a"));
 
     // Try to re-add a vertex.
-    pair<Iterator, bool> i = vs_try_add_vertex(store, Vertex("b"));
-    cout << "re-add: " << i.second << "\n";
+    pair<Descriptor, bool> i = vs::try_insert(store, Vertex("b"));
+    BOOST_ASSERT(!i.second);
 }
 
 template <typename Store>
 void add_verts(Store& store, pair_container_tag)
 {
-    typedef typename Store::iterator Iterator;
-    typedef typename Store::mapped_type Vertex;
-    vs_add_vertex(store, "a", Vertex());
-    vs_add_vertex(store, "b", Vertex());
+    typedef typename descriptor_traits<Store>::descriptor_type Descriptor;
+    typedef typename vertex_store_traits<Store>::vertex_type Vertex;
+    vs::insert(store, "a", Vertex());
+    vs::insert(store, "b", Vertex());
 
     // Try to re-add a vertex.
-    pair<Iterator, bool> i = vs_try_add_vertex(store, string("b"), Vertex());
-    cout << "re-add: " << i.second << "\n";
+    pair<Descriptor, bool> i = vs::try_insert(store, string("b"), Vertex());
+    BOOST_ASSERT(!i.second);
 }
 
+template <typename Store, typename Tag>
+void remove_vert(Store& store, Tag t)
+{
+    typedef typename descriptor_traits<Store>::descriptor_type Descriptor;
+    Descriptor d = vs::find(store, string("b"));
+    BOOST_ASSERT(d);
+    size_t n = vs::size(store);
+    vs::remove(store, d);
+    BOOST_ASSERT(vs::size(store) == n - 1);
+}
+
+// No-op for vectors... Can't remove vertices.
+template <typename Store>
+void remove_vert(Store& store, vector_tag)
+{ }
+
 template <typename Store>
 void test()
 {
     typedef typename Store::value_type Vertex;
-    typedef typename descriptor_traits<Store>::descriptor_type VertexDesc;
-    typedef typename Store::iterator StoreIterator;
+    typedef typename descriptor_traits<Store>::descriptor_type Descriptor;
 
     Store store;
 
     add_verts(store, container_arity(container_category(store)));
+    BOOST_ASSERT(!vs::empty(store));
+    BOOST_ASSERT(vs::size(store));
 
     // Find a verts
-    StoreIterator i = vs_find_vertex(store, string("b"));
-    cout << "test: " << distance(store.begin(), i) << endl;
+    Descriptor d = vs::find(store, string("b"));
+    BOOST_ASSERT(d);
+
+    // Check the removal of vertices
+    remove_vert(store, container_category(store));
 }
 
 int main()
@@ -92,7 +105,7 @@
     typedef vertex_set<>::vertex_store<my_vertex>::type VS;
     typedef vertex_map<string>::vertex_store<my_vertex>::type VM;
 
-    // test<VV>();
+    test<VV>();
     test<VL>();
     test<VS>();
     test<VM>();