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

From: asutton_at_[hidden]
Date: 2008-06-19 08:06:50

Author: asutton
Date: 2008-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
New Revision: 46504
URL: http://svn.boost.org/trac/boost/changeset/46504

Log:
Cleaned up the vertex_vector implementation.
Documented all of the vertex set operations for the undirected graph and
started adding some static asserts to the graph class to prevent unsupported
operations.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/none.hpp             |    20 ++                                      
   sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp    |     7                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp |   193 ++++++++++++++++++-                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp      |   211 ++++++---------------                   
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp       |   376 +++++++++++++++------------------------ 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp       |   340 ++++++++++-------------------------     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp    |   215 ++++++----------------                  
   7 files changed, 579 insertions(+), 783 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/none.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/none.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/none.hpp	2008-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -2,8 +2,26 @@
 #ifndef NONE_HPP
 #define NONE_HPP
 
-// The canonical none type.
+#include <boost/utility.hpp>
+
+/** The canonical none type. */
 struct none { };
 
+/** Like none, but not. */
+struct unused { };
+
+// Traits for the none type
+template <typename T>
+struct is_none { BOOST_STATIC_CONSTANT(bool, value = false); };
+
+template <>
+struct is_none<none> { BOOST_STATIC_CONSTANT(bool, value = true); };
+
+template <typename T>
+struct is_not_none { BOOST_STATIC_CONSTANT(bool, value = !is_none<T>::value); };
+
+template <>
+struct is_not_none<none> { BOOST_STATIC_CONSTANT(bool, value = !is_none<none>::value); };
+
 #endif
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp	2008-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -48,6 +48,11 @@
     size_type   _size;
 };
 
+// TODO: This eventually needs to be specialized for empty edges. Basically, if
+// you don't want edges, then we can just hand out integers that for each
+// edge - probably.
+#if 0
+
 /**
  * Partially specialize the property list for the case where the user does
  * not want properties. This will completely remove the property list from
@@ -60,6 +65,8 @@
     typedef std::size_t property_descriptor;
 };
 
+#endif
+
 
 template <typename P, typename A>
 property_list<P,A>::property_list()

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-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -17,6 +17,9 @@
 //   need to exist. We can just pretend to allocate them and return
 //   an integer "pseudo descriptor".
 
+// Note that the graph interface will fail to compile if a mapped graph is
+// requested whose key and property types are the same.
+
 #include "descriptor.hpp"
 
 #include "undirected_vertex.hpp"
@@ -24,12 +27,12 @@
 #include "vertex_vector.hpp"
 #include "vertex_list.hpp"
 #include "vertex_set.hpp"
+#include "vertex_map.hpp"
 
 #include "undirected_edge.hpp"
 #include "edge_vector.hpp"
 #include "edge_list.hpp"
 #include "edge_set.hpp"
-#include "edge_iterator.hpp"
 
 #include "adjacency_iterator.hpp"
 
@@ -83,29 +86,83 @@
     typedef typename vertex_store::vertex_range vertex_range;
     // FIXME: This is a bit hacky, but without constrained members, we need a key
     // type to enable mapped vertices.
-    typedef typename VertexStore::key_type key_type;
-
-    // Because edges are "distributed" among vertices, the edge iterators are
-    // somewhat special.
-    typedef basic_edge_iterator<this_type> edge_iterator;
-    typedef std::pair<edge_iterator, edge_iterator> edge_range;
+    typedef typename VertexStore::key_type vertex_key;
 
 
     // Constructors
     undirected_graph();
 
-    /** @name Vertex Set
-     * These functions operate (mostly) on the vertices of the graph. These
-     * functions include the ability to add, disconnect, and remove vertices.
+    /** @name Add Vertex
+     * Add a vertex to the graph. Add operations are determined by the concepts
+     * modeled by the vertex set.
+     *
+     * UnlabeledVertices        add_vertex()
+     * LabeledVerteces          add_vertex(vertex_properties)
+     * LabeledUniqueVertices    add_vertex(vertex_properties)
+     * MappedUniqueVertices     add_vertex(vertex_key)
      */
     //@{
     vertex_descriptor add_vertex();
     vertex_descriptor add_vertex(vertex_properties const&);
-    vertex_descriptor add_vertex(key_type const&, vertex_properties const&);
+    vertex_descriptor add_vertex(vertex_key const&, vertex_properties const&);
+    //@}
+
+    /** @name Find Vertex
+     * Find a vertex in the graph. These methods only exist for graphs that
+     * have UniqueVertices. These functions can also be used to find the first
+     * vertex of a non-unique vertices.
+     *
+     * LabeledUniqueVertices    find_vertex(vertex_properties)
+     * MappedUniqueVertices     find_vertex(vertex_key)
+     */
+    //@{
+    vertex_descriptor find_vertex(vertex_properties const&) const;
+    vertex_descriptor find_vertex(vertex_key const&) const;
+    //@{
+
+    /** @name Disconnect Vertex
+     * Disconnect a vertex from the graph by removing all of its incident edges.
+     * These functions only exist for graphs with ReducibleEdgeSets. Functions
+     * that take properties or keys are provided for convenience, but have
+     * additional dependencies and cost. These additonal functions are
+     * equivalent to disconnect_vertex(find_vertex(x)) where x is either a
+     * vertex_properties or vertex_key.
+     *
+     * ReducibleEdgeSet         disconnect_vertex(vertex_descriptor)
+     * LabeledUniqueVertices    disconnect_vertex(vertex_properties)
+     * MappedUniqueVertices     disconnect_vertex(vertex_key)
+     */
+    //@{
     void disconnect_vertex(vertex_descriptor);
+    void disconnect_vertex(vertex_properties const&);
+    void disconnect_vertex(vertex_key const&);
+    //@}
+
+    /** @name Remove Vertex
+     * Remove a vertex from the graph. These functions only exist for graphs
+     * with ReducibleVertexSets. Functions that take properties or keys are
+     * provided for convenience, but have additional requirements and cost.
+     * These additional functions are equivalent to remove_vertex(find_vertex(x))
+     * where x is either a vertex_properties or vertex_key.
+     *
+     * ReducibleVertexSet       remove_vertex(vertex_descriptor)
+     * LabeledUniqueVertices    remove_vertex(vertex_properties)
+     * MappedUniqueVertices     remove_vertex(vertex_key)
+     */
+    //@{
     void remove_vertex(vertex_descriptor);
+    void remove_vertex(vertex_properties const&);
+    void remove_vertex(vertex_key const&);
     //@}
 
+    /** @name Vertex Key
+     * Return the key for the given vertex. This is only provided for graphs
+     * with MappedVertices (can be multimapped).
+     */
+    //@{
+    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.
@@ -131,9 +188,9 @@
      * These function allow iteration over the edge set.
      */
     //@{
-    edge_range edges() const;
-    edge_iterator begin_edges() const;
-    edge_iterator end_edges() const;
+    // edge_range edges() const;
+    // edge_iterator begin_edges() const;
+    // edge_iterator end_edges() const;
     edges_size_type num_edges() const;
     //@}
 
@@ -152,9 +209,13 @@
     incident_edges_size_type degree(vertex_descriptor) const;
     //@{
 
-    // Property accesors
+    /** @name Property Accessors
+     * Access the properties of the given vertex or edge.
+     */
+    //@{
     vertex_properties& operator[](vertex_descriptor);
     edge_properties& operator[](edge_descriptor);
+    //@{
 
 private:
     property_store _props;
@@ -187,6 +248,44 @@
 }
 
 /**
+ * Add a new vertex with the given properties to the graph and map it to the
+ * given key.
+ *
+ * @requires VertexMap<Graph>
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
+undirected_graph<VP,EP,VS,ES>::add_vertex(vertex_key const& k, vertex_properties const& vp)
+{
+    return _verts.add(k, vp);
+}
+
+/**
+ * Find the vertex with the given properties, returning a descriptor to it.
+ *
+ * @requires LabeledUniqueVertex<Graph> ???
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
+undirected_graph<VP,EP,VS,ES>::find_vertex(vertex_properties const& vp) const
+{
+    BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+    return _verts.find(vp);
+}
+
+/**
+ * Find the vertex with the given properties, returning a descriptor to it.
+ *
+ * @requires MappedUniqueVertex<Graph>
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
+undirected_graph<VP,EP,VS,ES>::find_vertex(vertex_key const& k) const
+{
+    return _verts.find(k);
+}
+
+/**
  * Disconnect the vertex from the graph. This removes all edges incident to
  * the vertex, but will not remove the vertex itself.
  */
@@ -217,6 +316,35 @@
 }
 
 /**
+ * Disconnect the vertex having the given properties from the graph.
+ *
+ * @requires UniqueLabeledVertex<Graph>
+ *
+ * @todo What does this do for multiset vertex stores.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_properties const& vp)
+{
+    BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+    disconnect_vertex(find_vertex(vp));
+}
+
+/**
+ * Disconnect the vertex having the given key from the graph.
+ *
+ * @requires UniqueMappedVertex<Graph>
+ *
+ * @todo What does this do for multimap vertex stores.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_key const& k)
+{
+    disconnect_vertex(find_vertex(k));
+}
+
+/**
  * Remove the vertex from the graph. This will disconnect the vertex from the
  * graph prior to remove.
  */
@@ -229,6 +357,41 @@
 }
 
 /**
+ * Remove the vertex from the graph identified by the given properties.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_properties const& vp)
+{
+    BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+    disconnect_vertex(vp);
+    _verts.remove(vp);
+}
+
+/**
+ * Remove the vertex from the graph identified by the given key.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_key const& k)
+{
+    disconnect_vertex(k);
+    _verts.remove(k);
+}
+
+/**
+ * Return the key associated with the given vertex. This function is only
+ * available for graphs with mapped vertices.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_key const&
+undirected_graph<VP,EP,VS,ES>::key(vertex_descriptor v) const
+{
+    return _verts.key(v);
+}
+
+
+/**
  * Create an edge, connecting the vertices u and v.
  */
 template <BOOST_GRAPH_UG_PARAMS>

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-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -21,14 +21,15 @@
 template <template <typename> class Allocator>
 struct basic_vertex_list
 {
-    typedef none key_type;
+    typedef unused key_type;
     typedef void* descriptor_type;
 
     template <typename Vertex>
     struct store
     {
         typedef vertex_list_elem<Vertex, Allocator> stored_vertex;
-        typedef vertex_list_impl<stored_vertex, Allocator<stored_vertex> > type;
+        typedef Allocator<stored_vertex> allocator_type;
+        typedef vertex_list_impl<stored_vertex, allocator_type > type;
     };
 };
 
@@ -83,26 +84,47 @@
     // Add/remove vertices.
     vertex_descriptor add();
     vertex_descriptor add(vertex_properties const& vp);
-
-    // Remove vertices.
+    vertex_descriptor find(vertex_properties const& vp);
     void remove(vertex_descriptor v);
+    void remove(vertex_properties const& vp);
 
-    // Number of vertices.
-    size_type size() const;
-
-    // Vertex iteration.
-    vertex_range vertices() const;
-    vertex_iterator begin_vertices() const;
-    vertex_iterator end_vertices() const;
-
-    // Vertex accessors.
-    vertex_type& vertex(vertex_descriptor);
-    vertex_type const& vertex(vertex_descriptor) const;
-    vertex_properties& properties(vertex_descriptor);
-    vertex_properties const& properties(vertex_descriptor) const;
+    /** Return the number of vertices in the set. */
+    size_type size() const
+    { return _size; }
+
+    /** @name Vertex Iterators */
+    //@{
+    vertex_iterator begin_vertices() const
+    { return _verts.begin(); }
+
+    vertex_iterator end_vertices() const
+    { return _verts.end(); }
+
+    vertex_range vertices() const
+    { return std::make_pair(begin_vertices(), end_vertices()); }
+    //@}
+
+    /** @name Vertex Accessors */
+    //@{
+    vertex_type& vertex(vertex_descriptor v)
+    { return *static_cast<vertex_type*>(v); }
+
+    vertex_type const& vertex(vertex_descriptor v) const
+    { return *static_cast<vertex_type*>(v); }
+    //@}
+
+    /** @name Vertex Properties */
+    //@{
+    vertex_properties& properties(vertex_descriptor v)
+    { return vertex(v).properties(); }
+
+    vertex_properties const& properties(vertex_descriptor v) const
+    { return vertex(v).properties(); }
+    //@}
 
 private:
     vertex_store _verts;
+    size_type _size;
 };
 
 #define BOOST_GRAPH_VL_PARAMS \
@@ -114,6 +136,7 @@
 template <BOOST_GRAPH_VL_PARAMS>
 vertex_list_impl<V,A>::vertex_list_impl()
     : _verts()
+    , _size(0)
 { }
 
 /**
@@ -140,12 +163,27 @@
 typename vertex_list_impl<V,A>::vertex_descriptor
 vertex_list_impl<V,A>::add(vertex_properties const& vp)
 {
-    typename vertex_store::iterator i = _verts.insert(_verts.end(), vertex_type(vp));
+    ++_size;
+    iterator i = _verts.insert(_verts.end(), vertex_type(vp));
     i->iter = i;
     return &(*i);
 }
 
 /**
+ * Find the vertex with the given properties. If there are multiple vertices
+ * with the given properties, only the first is returned.
+ *
+ * @complexity O(V)
+ * @requires EqualityComparable<VertexProps>
+ */
+template <typename V, typename A>
+typename vertex_list_impl<V,A>::vertex_descriptor
+vertex_list_impl<V,A>::find(vertex_properties const& vp)
+{
+    return &const_cast<vertex_type&>(*std::find(_verts.begin(), _verts.end(), vp));
+}
+
+/**
  * Remove a vertex from the set. Removing a vertex will invalidate all vertex
  * descriptors and iterators to the removed vertex.
  *
@@ -155,145 +193,26 @@
 void
 vertex_list_impl<V,A>::remove(vertex_descriptor v)
 {
+    --_size;
     vertex_type* vp = static_cast<vertex_type*>(v);
     _verts.erase(vp->iter);
 }
 
 /**
- * Return an iterator range over the vertices in this graph.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_range
-vertex_list_impl<V,A>::vertices() const
-{
-    return std::make_pair(begin_vertices(), end_vertices());
-}
-
-/**
- * Return an iterator to the first vertex in the list.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_iterator
-vertex_list_impl<V,A>::begin_vertices() const
-{
-    return _verts.begin();
-}
-
-/**
- * Return an iterator past the end of the vertices in the list.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_iterator
-vertex_list_impl<V,A>::end_vertices() const
-{
-    return _verts.end();
-}
-
-/**
- * Return the number of vertices in the store.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::size_type
-vertex_list_impl<V,A>::size() const
-{
-    return _verts.size();
-}
-
-/**
- * Get access to the given vertex.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_type&
-vertex_list_impl<V,A>::vertex(vertex_descriptor v)
-{
-    return *static_cast<vertex_type*>(v);
-}
-
-/**
- * Get access to the given vertex.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_type const&
-vertex_list_impl<V,A>::vertex(vertex_descriptor v) const
-{
-    return *static_cast<vertex_type*>(v);
-}
-
-/**
- * Get the properties ofthe given vertex.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_properties&
-vertex_list_impl<V,A>::properties(vertex_descriptor v)
-{
-    return vertex(v).properties();
-}
-
-#undef BOOST_GRAPH_VL_PARAMS
-
-#if 0
-
-/**
- * Return the number of vertices in the vertex store.
+ * Remove the vertex with the given properties from the list. This searches
+ * the list for the first element with the given vertex and erases it. If there
+ * are multiple elements with these properties, only the first is removed.
  *
  * @complexity O(V)
- *
- * @todo I'm not sure about the interface I'd like to build for list storage.
- * If we don't include a lot of splice-style operations, then it's not a big
- * deal to manage the size of this list internally.
- */
-template <typename V, template <typename> class A>
-typename vertex_list_impl<V,A>::vertices_size_type
-vertex_list_impl<V,A>::num_vertices() const
-{
-    return _verts.size();
-}
-
-/**
- * Return the iterator range for the graph.
- */
-template <typename V, template <typename> class A>
-std::pair<
-    typename vertex_list_impl<V,A>::vertex_iterator,
-    typename vertex_list_impl<V,A>::vertex_iterator
->
-vertex_list_impl<V,A>::vertices() const
-{
-    return std::make_pair(_verts.begin(), _verts.end());
-}
-
-/**
- * Return the iterator for the begining of the vertices.
- */
-template <typename V, template <typename> class A>
-typename vertex_list_impl<V,A>::vertex_iterator
-vertex_list_impl<V,A>::begin_vertices() const
-{
-    return _verts.begin();
-}
-
-/**
- * Return the iterator for the begining of the vertices.
- */
-template <typename V, template <typename> class A>
-typename vertex_list_impl<V,A>::vertex_iterator
-vertex_list_impl<V,A>::end_vertices() const
-{
-    return _verts.end();
-}
-
-
-/**
- * Access the properties ofthe given vertex.
  */
-template <typename V, template <typename> class A>
-typename vertex_list_impl<V,A>::vertex_properties const&
-vertex_list_impl<V,A>::properties(vertex_descriptor v) const
+template <typename V, typename A>
+void
+vertex_list_impl<V,A>::remove(vertex_properties const& vp)
 {
-    return *vertex(v);
+    remove(find(vp));
 }
 
-#endif
+#undef BOOST_GRAPH_VL_PARAMS
 
 #endif
 

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-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -1,54 +1,79 @@
 
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_MAP_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_MAP_HPP
+#ifndef VERTEX_MAP_HPP
+#define VERTEX_MAP_HPP
 
 #include <map>
 
-#include <boost/graphs/adjacency_list/descriptor.hpp>
-#include <boost/graphs/adjacency_list/vs/mapped_vertex_iterator.hpp>
-
-namespace boost {
-namespace graphs {
-namespace adj_list {
-
 // Forward declarations
-template <typename V, typename K, template <typename> class C, template <typename> class A> class vertex_map_elem;
-template <typename V, typename K, typename C, typename A> class vertex_map_impl;
+template <typename, typename, typename, template <typename> class> class vertex_map_elem;
+template <typename, typename, typename, typename> class vertex_map_impl;
 
-template <typename Key, template <typename> class Compare, template <typename> class Allocator>
+/**
+ * This metafunction defines the implementation requirements of a mapping of
+ * vertices to the keys that describe them. This is function takes three
+ * parameters: the type of key, a comparator template, and vertex allocator.
+ *
+ * The Compare parameter must be a unary template class rather than a fully
+ * instantiated type. This makes it easier to pass arbitrary template functions
+ * (e.g., less and greater) instead of instantiated types.
+ *
+ * The Alloc parameter is also a unary template class. In this case, the caller
+ * does not know the final type of the allocator object. It us ultimately
+ * instantiated as an allocator of key/vertex pairs.
+ *
+ * @param Key The key type of the vertex map can be any LessThanComparable type.
+ * @param Compare A unary template class that implements a comparison of keys.
+ * @param Alloc An allocator for key/value pairs of the underliyng map.
+ */
+template <
+        typename Key,
+        template <typename> class Compare,
+        template <typename> class Alloc>
 struct basic_vertex_map
 {
-    typedef basic_vertex_descriptor<void*> descriptor_type;
+    typedef Key key_type;
+    typedef void* descriptor_type;
 
     template <typename Vertex>
     struct store
     {
-        typedef vertex_map_elem<Vertex, Key, Compare, Allocator> stored_vertex;
-        typedef std::pair<const Key, stored_vertex> stored_value;
-        typedef vertex_map_impl<stored_vertex, Key, Compare<Key>, Allocator<stored_value> > type;
+        // Build the key comparator (note: independent of vertex!)
+        typedef Compare<key_type> compare_type;
+
+        // Build the stored vertex type.
+        typedef vertex_map_elem<Vertex, Key, compare_type, Alloc> stored_vertex;
+
+        // Build the allocator
+        typedef Alloc<stored_vertex> allocator_type;
+
+        // Build the underlying store
+        typedef vertex_map_impl<stored_vertex, key_type, compare_type, allocator_type> type;
     };
 };
 
+/**
+ * The most common vertex set allows parameterization over the comparator used
+ * to sort vertices and uses the standard omnibus allocator.
+ */
 template <typename Key, template <typename> class Compare = std::less>
 struct vertex_map : basic_vertex_map<Key, Compare, std::allocator> { };
 
-// Extend the notion of a vertex for set storage so that we can store each
-// vertex's iterator with current vertex. This is used to provide constant
-// time access to the correct position in the underliying store.
+/**
+ * Extend the notion of a vertex for map storage so that we can store each
+ * vertex's iterator with current vertex. This is used to provide constant
+ * time access to the correct position in the underliying store.
+ */
 template <
-        typename Vertex,
-        typename Key,
-        template <typename> class Compare,
-        template <typename> class Alloc
-    >
+    typename Vertex,
+    typename Key,
+    typename Compare,
+    template <typename> class Alloc>
 class vertex_map_elem
     : public Vertex
 {
     typedef vertex_map_elem<Vertex, Key, Compare, Alloc> this_type;
 public:
-    typedef typename std::map<
-            Key, this_type, Compare<Key>, Alloc< std::pair<Key, this_type> >
-        >::iterator iterator;
+    typedef typename std::map<Key, this_type, Compare, Alloc<this_type> >::iterator iterator;
 
     inline vertex_map_elem(typename Vertex::vertex_properties const& vp)
         : Vertex(vp)
@@ -59,272 +84,157 @@
 };
 
 /**
- * The vertex_map_impl provides a list-based implementation of vertex storage
- * for an adjacency list. List-based storage is best for graphs with
- * unidentified vertices and requirements for fast vertex addition and deletion.
- *
- * This class requires that the graph's vertex properties be less than
- * comparable since the ordering of vertices in the set is based on that
- * implementation of the ordering. Note that the vertex type provides a built
- * in ordering using operator<() that delegates the call to the properties.
+ * Implementation of the vertex set. This requires that vertices (actually
+ * their properties) are less-than comparable.
  *
- * Adding vertices to a list does not invalidate any vertex or edge descriptors.
- * Removing vertices will invalidate descriptors referencing the removed
- * vertex. All insertions and removals occur in constant time. However, getting
- * the number of vertices is linear.
- *
- * @require LessThanComparable<Vertex::properties_type>
+ * @param Vertex The vertex type stored by the class.
+ * @param Key The type of key mapping to vertices.
+ * @param Compare An ordering over keys.
+ * @param Alloc The allocator for Key/Vertex pairs.
  */
 template <typename Vertex, typename Key, typename Compare, typename Allocator>
 class vertex_map_impl
 {
     typedef std::map<Key, Vertex, Compare, Allocator> vertex_store;
 public:
-    typedef Key key_type;
+    typedef void* vertex_descriptor;
+
     typedef Vertex vertex_type;
     typedef typename Vertex::vertex_properties vertex_properties;
-    typedef typename Vertex::vertex_descriptor vertex_descriptor;
-    typedef typename vertex_store::size_type vertices_size_type;
-    typedef mapped_vertex_iterator<vertex_store> vertex_iterator;
+    typedef typename vertex_store::size_type size_type;
+    typedef typename vertex_store::iterator iterator;
+    typedef typename vertex_store::const_iterator const_iterator;
+
+    typedef Key key_type;
+
+
+    typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+    typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
 
     // Constructors
     vertex_map_impl();
 
-    // Add or insert a vertex.
-    vertex_descriptor add_vertex(key_type const& k, vertex_properties const& vp);
-    std::pair<vertex_descriptor, bool> insert_vertex(key_type const& k, vertex_properties const& vp);
-
-    // Remove a vertex.
-    void remove_vertex(vertex_descriptor v);
-
-    // Find a vertex
-    vertex_descriptor find_vertex(key_type const& k) const;
-
-    // Number of vertices.
-    vertices_size_type num_vertices() const;
-
-    // Vertex iteration.
-    std::pair<vertex_iterator, vertex_iterator> vertices() const;
-    vertex_iterator begin_vertices() const;
-    vertex_iterator end_vertices() const;
-
-    // Vertex accessors.
-    vertex_type& vertex(vertex_descriptor v);
-    vertex_type const& vertex(vertex_descriptor v) const;
-    vertex_descriptor descriptor(vertex_type const& v) const;
-    key_type const& key(vertex_descriptor v) const;
-
-    // Property accessors.
-    vertex_properties& properties(vertex_descriptor v);
-    vertex_properties const& properties(vertex_descriptor v) const;
-
+    vertex_descriptor add(key_type const& k, vertex_properties const& vp);
+    vertex_descriptor find(key_type const& vp) const;
+    void remove(vertex_descriptor);
+    void remove(key_type const&);
+
+    key_type const& key(vertex_descriptor) const;
+
+    /** Return the number of vertices in the map. */
+    inline size_type size() const
+    { return _verts.size(); }
+
+    /** @name Vertex Iteration */
+    //@{
+    inline vertex_iterator begin_vertices() const
+    { return _verts.begin(); }
+
+    inline vertex_iterator end_vertices() const
+    { return _verts.end(); }
+
+    vertex_range vertices() const
+    { return std::make_pair(begin_vertices(), end_vertices()); }
+    //@}
+
+    /** @name Vertex Accessors */
+    //@{
+    vertex_type& vertex(vertex_descriptor v)
+    { return *static_cast<vertex_type*>(v); }
+
+    vertex_type const& vertex(vertex_descriptor v) const
+    { return *static_cast<vertex_type*>(v); }
+    //@}
+
+    /** @name Property Accessors */
+    //@{
+    vertex_properties& properties(vertex_descriptor v)
+    { return vertex(v).properties(); }
+
+    vertex_properties const& properties(vertex_descriptor v) const
+    { return vertex(v).properties(); }
+    //@}
 
 private:
     vertex_store _verts;
 };
 
-#define BOOST_GRAPHS_VM_PARAMS \
-    typename V, typename K, typename C, typename A
-
-template <BOOST_GRAPHS_VM_PARAMS>
+template <typename V, typename K, typename C, typename A>
 vertex_map_impl<V,K,C,A>::vertex_map_impl()
     : _verts()
 { }
 
-#undef BOOST_GRAPHS_VM_PARAMS
-
-#if 0
-
 /**
- * Add a vertex to the store with the key and properties. If the key is mapped
- * to a vertex, do nothing. Return a descriptor to the existing or new vertex.
+ * Add the vertex with the given properties. If there is already a vertex with
+ * these properties, then this returns the descriptor of the existing vertex
+ * and does not insert a new vertex.
  *
- * @complexity O(log(V))
+ * @complexity O(lg(V))
  */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
+template <typename V, typename K, typename C, typename A>
 typename vertex_map_impl<V,K,C,A>::vertex_descriptor
-vertex_map_impl<V,K,C,A>::add_vertex(const K& k, vertex_properties const& vp)
-{
-    return insert_vertex(k, vp).first;
-}
-
-/**
- * Add a vertex to the store with the given properties. If not specified, the
- * vertex is created with default properties and return a descriptor to the
- * inserted vertex. If the vertex exists, the second element of the returned
- * pair is false.
- *
- * @complexity O(log(V))
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-std::pair<typename vertex_map_impl<V,K,C,A>::vertex_descriptor, bool>
-vertex_map_impl<V,K,C,A>::insert_vertex(key_type const& k, vertex_properties const& vp)
+vertex_map_impl<V,K,C,A>::add(key_type const& k, vertex_properties const& vp)
 {
-    std::pair<vertex_descriptor, bool> ret;
-    std::pair<typename vertex_store::iterator, bool> ins =
-            _verts.insert(make_pair(k, vertex_type(vp)));
+    // Try to insert the vertex into the map.
+    vertex_descriptor ret;
+    std::pair<iterator, bool> ins = _verts.insert(std::make_pair(k, vertex_type(vp)));
     if(ins.second) {
-        // Yikes... so dirty. Normally, we can't modify an object via its
-        // iterator since that would indicate a change to the key. However,
-        // the key is based on the properties of the vertex, not the part of
-        // the object that we're going to change.
         vertex_type& v = ins.first->second;
         v.iter = ins.first;
-        ret.first = &v;
+        ret = &v;
     }
     else {
-        ret.first = &(ins.first->second);
+        ret = &ins.first->second;
     }
-    ret.second = ins.second;
-
     return ret;
 }
 
 /**
- * Find a vertex given a key. If the key does not exist, return an invalid
- * descriptor.
+ * Find the vertex in the map with the given key.
+ *
+ * @complexity O(log(V))
  */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
+template <typename V, typename K, typename C, typename A>
 typename vertex_map_impl<V,K,C,A>::vertex_descriptor
-vertex_map_impl<V,K,C,A>::find_vertex(key_type const& k) const
+vertex_map_impl<V,K,C,A>::find(key_type const& k) const
 {
-    vertex_descriptor ret;
-    typename vertex_store::const_iterator iter = _verts.find(k);
-    if(iter != _verts.end()) {
-        // Because the function is const, the resulting vertex should also be
-        // const. Unfortunately, this isn't really going to work for me.
-        vertex_type& v = const_cast<vertex_type&>(iter->second);
-        ret = &v;
-    }
-    return ret;
+    return &const_cast<vertex_type&>(_verts.find(k)->second);
 }
 
 /**
- * Remove a vertex from the store.
- *
- * Removing a vertex will invalidate all vertex and edge descriptors.
+ * Remove a vertex from the map. Removing a vertex will invalidate all
+ * descriptors and iterators to the vertex being removed.
  *
- * @complexity O(|V|)
+ * @complexity O(log(V))
  */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
+template <typename V, typename K, typename C, typename A>
 void
-vertex_map_impl<V,K,C,A>::remove_vertex(vertex_descriptor v)
+vertex_map_impl<V,K,C,A>::remove(vertex_descriptor v)
 {
-    vertex_type* vp = static_cast<vertex_type*>(v);
-    _verts.erase(vp->iter);
+    _verts.erase(vertex(v).iter);
 }
 
 /**
- * Return the number of vertices in the vertex store.
+ * Remove the vertex with the given key from the map. This operation finds
+ * the vertex before removing it.
  *
- * @complexity O(V)
- *
- * @todo I'm not sure about the interface I'd like to build for list storage.
- * If we don't include a lot of splice-style operations, then it's not a big
- * deal to manage the size of this list internally.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertices_size_type
-vertex_map_impl<V,K,C,A>::num_vertices() const
-{
-    return _verts.size();
-}
-
-/**
- * Return the iterator range for the graph.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-std::pair<
-    typename vertex_map_impl<V,K,C,A>::vertex_iterator,
-    typename vertex_map_impl<V,K,C,A>::vertex_iterator
->
-vertex_map_impl<V,K,C,A>::vertices() const
-{
-    return std::make_pair(_verts.begin(), _verts.end());
-}
-
-/**
- * Get a vertex iterator to the beginning iterator of the vertices.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_iterator
-vertex_map_impl<V,K,C,A>::begin_vertices() const
-{ return _verts.begin(); }
-
-/**
- * Get a vertex iterator to an iterator past the end of the vertices.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_iterator
-vertex_map_impl<V,K,C,A>::end_vertices() const
-{ return _verts.end(); }
-
-/**
- * Get access to the given vertex.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_type&
-vertex_map_impl<V,K,C,A>::vertex(vertex_descriptor v)
-{
-    return *static_cast<vertex_type*>(v.desc);
-}
-
-/**
- * Get access to the given vertex.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_type const&
-vertex_map_impl<V,K,C,A>::vertex(vertex_descriptor v) const
-{
-    return *static_cast<vertex_type*>(v.desc);
-}
-
-/**
- * Return a descriptor for the given vertex.
+ * @complexity O(log(V))
  */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_descriptor
-vertex_map_impl<V,K,C,A>::descriptor(vertex_type const& v) const
+template <typename V, typename K, typename C, typename A>
+void
+vertex_map_impl<V,K,C,A>::remove(key_type const& k)
 {
-    return &const_cast<vertex_type&>(v);
+    remove(find(k));
 }
 
 /**
- * Get the key of a vertex descriptor.
+ * Return the key for the given vertex.
  */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
+template <typename V, typename K, typename C, typename A>
 typename vertex_map_impl<V,K,C,A>::key_type const&
 vertex_map_impl<V,K,C,A>::key(vertex_descriptor v) const
 {
-    vertex_type& vert = *static_cast<vertex_type*>(v.desc);
-    return vert.iter->first;
+    return vertex(v).iter->first;
 }
 
-
-/**
- * Get the properties of the given vertex.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_properties&
-vertex_map_impl<V,K,C,A>::properties(vertex_descriptor v)
-{
-    return *vertex(v);
-}
-
-/**
- * Get the properties of the given vertex.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_properties const&
-vertex_map_impl<V,K,C,A>::properties(vertex_descriptor v) const
-{
-    return *vertex(v);
-}
-
-#endif
-
-} /* namespace adj_list */
-} /* namesapce graphs */
-} /* namespace boost */
-
 #endif

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-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -6,25 +6,45 @@
 
 // Forward declarations
 template <typename, template <typename> class, template <typename> class> class vertex_set_elem;
+template <typename, typename> class vertex_set_compare;
 template <typename, typename, typename> class vertex_set_impl;
 
 /**
  * This metafunction defines the implementation requirements of a set of
- * verties.
+ * vertices. This function allos the parameterization of vertex comparability
+ * by allowing the caller to specify the comparator.
+ *
+ * The Compare parameter must be a unary template class. This lets us specify
+ * arbitrary function objects by name without having to explicitly instantiate
+ * them.
+ *
+ * The Alloc parameter is also a unary template class. In this case, the caller
+ * does not actually know what the final instantiated type is going to be.
+ *
+ * @param Compare A unary template class that compares vertex properties.
+ * @param Alloc A unary template class that allocates vertices.
  */
 template <template <typename> class Compare, template <typename> class Alloc>
 struct basic_vertex_set
 {
-    typedef none key_type;
+    typedef unused key_type;
     typedef void* descriptor_type;
 
     template <typename Vertex>
     struct store
     {
+        // Build the stored vertex type.
         typedef vertex_set_elem<Vertex, Compare, Alloc> stored_vertex;
-        typedef Compare<stored_vertex> comp_type;
-        typedef Alloc<stored_vertex> alloc_type;
-        typedef vertex_set_impl<stored_vertex, comp_type, alloc_type> type;
+
+        // Build the vertex comparator.
+        typedef Compare<typename stored_vertex::vertex_properties> vertex_compare;
+        typedef vertex_set_compare<stored_vertex, vertex_compare> compare_type;
+
+        // Build the allocator.
+        typedef Alloc<stored_vertex> allocator_type;
+
+        // Build the vertex set implementation.
+        typedef vertex_set_impl<stored_vertex, compare_type, allocator_type> type;
     };
 };
 
@@ -57,15 +77,42 @@
         , iter()
     { }
 
-    inline bool operator<(this_type const& x) const
-    { return Vertex::operator<(static_cast<Vertex const&>(x)); }
-
     iterator iter;
 };
 
 /**
+ * A forwarding comparator for the vertex forwards the comparison to the given
+ * comparator. This type is used internally to forward comparisons of vertices
+ * to the property comparison provided by the edge set parameter.
+ *
+ * @param StoredVertex The type of vertex being compared
+ * @param Compare An ordering over vertex properties.
+ */
+template <typename StoredVertex, typename Compare>
+struct vertex_set_compare
+{
+    inline vertex_set_compare()
+        : comp(Compare())
+    { }
+
+    inline vertex_set_compare(vertex_set_compare const& x)
+        : comp(x.comp)
+    { }
+
+    inline bool operator()(StoredVertex const& a, StoredVertex const& b) const
+    { return comp(a.properties(), b.properties()); }
+
+    Compare comp;
+};
+
+
+/**
  * Implementation of the vertex set. This requires that vertices (actually
  * their properties) are less-than comparable.
+ *
+ * @param Vertex The type of vertex stored by the set.
+ * @param Compare An ordering of vertices (should delegate to properties).
+ * @param Allocator The allocator for stored vertices.
  */
 template <typename Vertex, typename Compare, typename Allocator>
 class vertex_set_impl
@@ -89,27 +136,43 @@
 
     // Add vertices. Note that you can't add without properties.
     vertex_descriptor add(vertex_properties const& vp);
-
-    // Remove vertices.
+    vertex_descriptor find(vertex_properties const& vp) const;
     void remove(vertex_descriptor v);
+    void remove(vertex_properties const& v);
 
-    // Find the given vertex.
-    const_iterator find(vertex_descriptor v) const;
-    const_iterator find(vertex_properties const& vp);
-
-    // Number of vertices.
-    size_type size() const;
-
-    // Vertex iteration.
-    vertex_range vertices() const;
-    vertex_iterator begin_vertices() const;
-    vertex_iterator end_vertices() const;
-
-    // Vertex accessors.
-    vertex_type& vertex(vertex_descriptor);
-    vertex_type const& vertex(vertex_descriptor) const;
-    vertex_properties& properties(vertex_descriptor);
-    vertex_properties const& properties(vertex_descriptor) const;
+    /** Return the number of vertices in the set. */
+    inline size_type size() const
+    { return _verts.size(); }
+
+    /** @name Vertex Iteration */
+    //@{
+    vertex_iterator begin_vertices() const
+    { return _verts.begin(); }
+
+    vertex_iterator end_vertices() const
+    { return _verts.end(); }
+
+    vertex_range vertices() const
+    { return std::make_pair(begin_vertices(), end_vertices()); }
+    //@}
+
+    /** @name Vertex Accessors */
+    //@{
+    vertex_type& vertex(vertex_descriptor v)
+    { return *static_cast<vertex_type*>(v); }
+
+    vertex_type const& vertex(vertex_descriptor v) const
+    { return *static_cast<vertex_type*>(v); }
+    //@}
+
+    /** @name Property Accessors */
+    //@{
+    vertex_properties& properties(vertex_descriptor v)
+    { return vertex(v).properties(); }
+
+    vertex_properties const& properties(vertex_descriptor v) const
+    { return vertex(v).properties(); }
+    //@{
 
 private:
     vertex_store _verts;
@@ -150,240 +213,43 @@
 }
 
 /**
- * Remove a vertex from the set. Removing a vertex will invalidate all
- * descriptors and iterators to the vertex being removed.
- *
- * @complexity O(log(V))
- */
-template <BOOST_GRAPH_VS_PARAMS>
-void
-vertex_set_impl<V,C,A>::remove(vertex_descriptor v)
-{
-    vertex_type* vp = static_cast<vertex_type*>(v);
-    _verts.erase(vp->iter);
-}
-
-/**
- * Find a vertex in the set.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::const_iterator
-vertex_set_impl<V,C,A>::find(vertex_descriptor v) const
-{
-    return find(vertex(v).properties());
-}
-
-/**
- * Return an iterator range over the vertices in this graph.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_range
-vertex_set_impl<V,C,A>::vertices() const
-{
-    return std::make_pair(begin_vertices(), end_vertices());
-}
-
-/**
- * Return an iterator to the first vertex in the set.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_iterator
-vertex_set_impl<V,C,A>::begin_vertices() const
-{
-    return _verts.begin();
-}
-
-/**
- * Return an iterator past the end of the vertices in the set.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_iterator
-vertex_set_impl<V,C,A>::end_vertices() const
-{
-    return _verts.end();
-}
-
-/**
- * Return the number of vertices in this vertex set.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::size_type
-vertex_set_impl<V,C,A>::size() const
-{
-    return _verts.size();
-}
-
-/**
- * Get access to the given vertex.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_type&
-vertex_set_impl<V,C,A>::vertex(vertex_descriptor v)
-{
-    return *static_cast<vertex_type*>(v);
-}
-
-/**
- * Get access to the given vertex.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_type const&
-vertex_set_impl<V,C,A>::vertex(vertex_descriptor v) const
-{
-    return *static_cast<vertex_type*>(v);
-}
-
-/**
- * Get the properties of the given vertex.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_properties&
-vertex_set_impl<V,C,A>::properties(vertex_descriptor v)
-{
-    return vertex(v).properties();
-}
-
-#undef BOOST_GRAPH_VS_PARAMS
-
-#if 0
-
-/**
- * Add a vertex to the store with the given properties. If not specified, the
- * vertex is created with default properties. Note that vertices are not mapped
- * or ordered so multiple, equivalent vertices can be added to the graph.
+ * Find the descriptor with the given properties.
  *
  * @complexity O(log(V))
  */
 template <BOOST_GRAPH_VS_PARAMS>
 typename vertex_set_impl<V,C,A>::vertex_descriptor
-vertex_set_impl<V,C,A>::add_vertex(vertex_properties const& vp)
+vertex_set_impl<V,C,A>::find(vertex_properties const& vp) const
 {
-    return insert_vertex(vp).first;
+    return &const_cast<vertex_type&>(*_verts.find(vp));
 }
 
 /**
- * Add a vertex to the store with the given properties. If not specified, the
- * vertex is created with default properties and return a descriptor to the
- * inserted vertex. If the vertex exists, the second element of the returned
- * pair is false.
+ * Remove a vertex from the set. Removing a vertex will invalidate all
+ * descriptors and iterators to the vertex being removed.
  *
  * @complexity O(log(V))
  */
 template <BOOST_GRAPH_VS_PARAMS>
-std::pair<typename vertex_set_impl<V,C,A>::vertex_descriptor, bool>
-vertex_set_impl<V,C,A>::insert_vertex(vertex_properties const& vp)
+void
+vertex_set_impl<V,C,A>::remove(vertex_descriptor v)
 {
-    std::pair<vertex_descriptor, bool> ret;
-    std::pair<typename vertex_store::iterator, bool> ins =
-            _verts.insert(vertex_type(vp));
-    if(ins.second) {
-        // Yikes... so dirty. Normally, we can't modify an object via its
-        // iterator since that would indicate a change to the key. However,
-        // the key is based on the properties of the vertex, not the part of
-        // the object that we're going to change.
-        vertex_type& v = const_cast<vertex_type&>(*(ins.first));
-        v.iter = ins.first;
-        ret.first = &v;
-    }
-    else {
-        ret.first = &const_cast<vertex_type&>(*ins.first);
-    }
-    ret.second = ins.second;
-
-    return ret;
+    _verts.erase(vertex(v).iter);
 }
 
 /**
- * Remove the vertex identified by the given properties from the store.
+ * Remove the vertex identified by the given properties from the set. This
+ * finds the vertex before removing it.
  *
  * @complexity O(log(V))
  */
 template <BOOST_GRAPH_VS_PARAMS>
 void
-vertex_set_impl<V,C,A>::remove_vertex(vertex_properties const& vp)
-{4
-    remove_vertex(find(vp));
-}
-
-/**
- * Find a vertex by its properties.
- *
- * @complexity O(log(V))
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_descriptor
-vertex_set_impl<V,C,A>::find_vertex(vertex_properties const& vp) const
-{
-    // This is a little gross... We have to tempoararily construct an empty
-    // vertex with the given properties in order for the find operations to
-    // work.
-    vertex_descriptor ret;
-    typename vertex_store::iterator iter = _verts.find(vertex_type(vp));
-    if(iter != _verts.end()) {
-        ret = &const_cast<vertex_type&>(*iter);
-    }
-    return ret;
-}
-
-/**
- * Return the number of vertices in the vertex store.
- *
- * @complexity O(V)
- *
- * @todo I'm not sure about the interface I'd like to build for list storage.
- * If we don't include a lot of splice-style operations, then it's not a big
- * deal to manage the size of this list internally.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertices_size_type
-vertex_set_impl<V,C,A>::num_vertices() const
+vertex_set_impl<V,C,A>::remove(vertex_properties const& vp)
 {
-    return _verts.size();
+    remove(find(vp));
 }
 
-/**
- * Return the iterator range for the graph.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-std::pair<
-    typename vertex_set_impl<V,C,A>::vertex_iterator,
-    typename vertex_set_impl<V,C,A>::vertex_iterator
->
-vertex_set_impl<V,C,A>::vertices() const
-{
-    return std::make_pair(_verts.begin(), _verts.end());
-}
-
-/**
- * Get a vertex iterator to the beginning iterator of the vertices.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_iterator
-vertex_set_impl<V,C,A>::begin_vertices() const
-{
-    return _verts.begin();
-}
-
-/**
- * Get a vertex iterator to an iterator past the end of the vertices.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_iterator
-vertex_set_impl<V,C,A>::end_vertices() const
-{
-    return _verts.end();
-}
-
-/**
- * Access the properties of the given vertex.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_properties const&
-vertex_set_impl<V,C,A>::properties(vertex_descriptor v) const
-{
-    return *vertex(v);
-}
-
-#endif
+#undef BOOST_GRAPH_VS_PARAMS
 
 #endif

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-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -3,17 +3,25 @@
 #define VERTEX_VECTOR_HPP
 
 #include <vector>
+#include <algorithm>
 
 // Forward declarations
 template <typename V, typename A> struct vertex_vector_impl;
 
 /**
+ * The vertex vector stores vertices in a vector, allowing for fast inserts
+ * and iteration, but slow finds and removals.
  *
+ * The Alloc parameter is a unary template class responsible for allocating
+ * the stored vertices. We use a template rather than a type because the caller
+ * does not know the actual types being allocated.
+ *
+ * @param Alloc A unary template class that will allocate stored vertices.
  */
-template <template <typename> class Allocator>
+template <template <typename> class Alloc>
 struct basic_vertex_vector
 {
-    typedef none key_type;
+    typedef unused key_type;
     typedef std::size_t descriptor_type;
 
     // The store metafunction generates the type used to store vertices in
@@ -22,7 +30,9 @@
     template <typename Vertex>
     struct store
     {
-        typedef vertex_vector_impl<Vertex, Allocator<Vertex> > type;
+        typedef Vertex stored_vertex;
+        typedef Alloc<stored_vertex> allocator_type;
+        typedef vertex_vector_impl<stored_vertex, allocator_type> type;
     };
 };
 
@@ -59,32 +69,54 @@
     // Constructors
     vertex_vector_impl();
 
-    // Add/remove vertex.
+    /** @name Add Vertex */
+    //@{
     vertex_descriptor add();
-    vertex_descriptor add(vertex_properties const& vp);
+    vertex_descriptor add(vertex_properties const&);
+    //@}
 
-    // Number of vertices.
-    size_type size() const;
+    /** Return the vertex with the given properties */
+    vertex_descriptor find(vertex_properties const&) const;
 
-    // Vertex iteration.
-    vertex_range vertices() const;
-    vertex_iterator begin_vertices() const;
-    vertex_iterator end_vertices() const;
-
-    // Vertex/vertex property accessors.
-    vertex_type& vertex(vertex_descriptor v);
-    vertex_type const& vertex(vertex_descriptor v) const;
-    vertex_properties& properties(vertex_descriptor);
-    vertex_properties const& properties(vertex_descriptor) const;
+    /** Rerturn the number of vertices in the vector. */
+    size_type size() const
+    { return _verts.size(); }
+
+    /** @name Vertex Iterators */
+    //@{
+    vertex_iterator begin_vertices() const
+    { return _verts.begin(); }
+
+    vertex_iterator end_vertices() const
+    { return _verts.end(); }
+
+    vertex_range vertices() const
+    { return std::make_pair(begin_vertices(), end_vertices()); }
+    //@}
+
+    /** @name Vertex Accessors */
+    //@{
+    vertex_type& vertex(vertex_descriptor v)
+    { return _verts[v]; }
+
+    vertex_type const& vertex(vertex_descriptor v) const
+    { return _verts[v]; }
+    //@{
+
+    /** @name Property Accessors */
+    //@{
+    vertex_properties& properties(vertex_descriptor v)
+    { return vertex(v).properties(); }
+
+    vertex_properties const& properties(vertex_descriptor v) const
+    { return vertex(v).properties(); }
+    //@{
 
 private:
     vertex_store _verts;
 };
 
-#define BOOST_GRAPH_VV_PARAMS \
-    typename V, typename A
-
-template <BOOST_GRAPH_VV_PARAMS>
+template <typename V, typename A>
 vertex_vector_impl<V,A>::vertex_vector_impl()
     : _verts()
 { }
@@ -94,9 +126,9 @@
  * the descriptor to the added vertex. Adding a vertex does not invalidate
  * any vertices or edges.
  *
- * @complexity O(1) amortized
+ * @complexity O(~1)
  */
-template <BOOST_GRAPH_VV_PARAMS>
+template <typename V, typename A>
 typename vertex_vector_impl<V,A>::vertex_descriptor
 vertex_vector_impl<V,A>::add()
 {
@@ -107,9 +139,9 @@
  * Add a vertex to the store with the given properties. Adding a vertex does
  * not invalidate any other descriptors.
  *
- * @complexity O(1) amortized
+ * @complexity O(~1)
  */
-template <BOOST_GRAPH_VV_PARAMS>
+template <typename V, typename A>
 typename vertex_vector_impl<V,A>::vertex_descriptor
 vertex_vector_impl<V,A>::add(vertex_properties const& vp)
 {
@@ -119,135 +151,16 @@
 }
 
 /**
- * Return an iterator range over the vertices in this graph.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_range
-vertex_vector_impl<V,A>::vertices() const
-{
-    return std::make_pair(begin_vertices(), end_vertices());
-}
-
-/**
- * Return an iterator to the first vertex in the vector.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_iterator
-vertex_vector_impl<V,A>::begin_vertices() const
-{
-    return vertex_iterator(_verts, _verts.begin());
-}
-
-/**
- * Return an iterator past the end of the vertices in the vector.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_iterator
-vertex_vector_impl<V,A>::end_vertices() const
-{
-    return vertex_iterator(_verts, _verts.end());
-}
-
-/**
- * Return the number of vertices in the store.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::size_type
-vertex_vector_impl<V,A>::size() const
-{
-    return _verts.size();
-}
-
-/**
- * Get access to the underlying vertex.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_type&
-vertex_vector_impl<V,A>::vertex(vertex_descriptor v)
-{
-    return _verts[v];
-}
-
-/**
- * Get access to the underlying vertex.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_type const&
-vertex_vector_impl<V,A>::vertex(vertex_descriptor v) const
-{
-    return _verts[v];
-}
-
-/**
- * Get the properties of the given vertex.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_properties&
-vertex_vector_impl<V,A>::properties(vertex_descriptor v)
-{
-    return vertex(v).properties();
-}
-
-#undef BOOST_GRAPH_VV_PARAMS
-
-#if 0
-
-/**
- * Return the number of vertices in the vertex store.
+ * Find the vertex with the given properties.
  *
- * @complexity constant
- */
-template <typename V, template <typename> class A>
-typename vertex_vector_impl<V,A>::vertices_size_type
-vertex_vector_impl<V,A>::num_vertices() const
-{
-    return _verts.size();
-}
-
-/**
- * Return the iterator range for the graph.
+ * @complexity O(V)
  */
-template <typename V, template <typename> class A>
-std::pair<
-    typename vertex_vector_impl<V,A>::vertex_iterator,
-    typename vertex_vector_impl<V,A>::vertex_iterator
->
-vertex_vector_impl<V,A>::vertices() const
-{
-    return std::make_pair(begin_vertices(), end_vertices());
-}
-
-/**
- * Get an iterator to the beginning of the vertices.
- */
-template <typename V, template <typename> class A>
-typename vertex_vector_impl<V,A>::vertex_iterator
-vertex_vector_impl<V,A>::begin_vertices() const
-{
-    return vertex_iterator(_verts, _verts.begin());
-}
-
-/**
- * Get an iterator past the end of the vertices.
- */
-template <typename V, template <typename> class A>
-typename vertex_vector_impl<V,A>::vertex_iterator
-vertex_vector_impl<V,A>::end_vertices() const
-{
-    return vertex_iterator(_verts, _verts.end());
-}
-
-
-/**
- * Get access to the properties of the given vertex.
- */
-template <typename V, template <typename> class A>
-typename vertex_vector_impl<V,A>::vertex_properties const&
-vertex_vector_impl<V,A>::properties(vertex_descriptor v) const
+template <typename V, typename A>
+typename vertex_vector_impl<V,A>::vertex_descriptor
+vertex_vector_impl<V,A>::find(vertex_properties const& vp) const
 {
-    return *vertex(v);
+    return std::distance(_verts.begin(),
+                         std::find(_verts.begin(), _verts.end(), vp));
 }
 
 #endif
-
-#endif