[Boost-commit] svn:boost r46195 - sandbox/SOC/2008/graphs/branches/iu/boost/graphs

From: asutton_at_[hidden]
Date: 2008-06-06 13:12:20

Author: asutton
Date: 2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
New Revision: 46195
URL: http://svn.boost.org/trac/boost/changeset/46195

Log:
Continued developing the undirected graph. Need to revisit edge addition since
the current imple doesn't actually obey the rules for edge sets. Probably end
up with some kind of "partial" edge addition.

Figured out an interesting approach to remove all edges from a graph.

Moved all the different vertex iterators to a vertex_iterator file.

Added:
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_iterator.hpp   (contents, props changed)
Removed:
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/indexed_vertex_iterator.hpp
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/mapped_vertex_iterator.hpp
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/simple_vertex_iterator.hpp
Text files modified: 
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/descriptor.hpp       |    29 ----                                    
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge_set.hpp         |    30 ++++                                    
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp   |    92 ++++++++++++--                          
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp    |   160 +++++++++++++++++-------                
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp |    18 +-                                      
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/none.hpp             |    10 +                                       
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp    |   119 +++++++++++++++----                     
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_vector.hpp  |    12 +                                       
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp |   200 +++++++++++++++++++++++++++++--         
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp           |    74 +++++++++++                             
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_list.hpp      |   162 ++++++++++++++++---------               
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_set.hpp       |   250 ++++++++++++++++++++++++--------------- 
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_vector.hpp    |    83 +++++++++----                           
   13 files changed, 907 insertions(+), 332 deletions(-)

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/descriptor.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -2,8 +2,6 @@
 #ifndef DESCRIPTOR_HPP
 #define DESCRIPTOR_HPP
 
-#include "unordered_pair.hpp"
-
 // Important notes about descriptors
 //
 // A descriptor is basically an opaque reference to an object. It's kind of
@@ -79,32 +77,5 @@
     D desc;
 };
 
-// We actually need a specialized undirected vertex descriptor that is capable of
-// representing an edge, given a source vertex, a target vertex and a reference
-// to the edge properties.
-template <typename VertexDesc, typename PropDesc>
-class undirected_edge_descriptor
-{
-public:
-    undirected_edge_descriptor()
-        : edge()
-        , prop()
-    { }
-
-    undirected_edge_descriptor(VertexDesc u, VertexDesc v, PropDesc p)
-        : edge(u, v)
-        , prop(p)
-    { }
-
-    bool operator<(undirected_edge_descriptor const& x)
-    {
-        return edge < x.edge || (!(x.edge < edge) && prop < x.prop);
-    }
-
-private:
-    unordered_pair<VertexDesc> edge;
-    PropDesc prop;
-};
-
 #endif
 

Added: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,69 @@
+
+#ifndef EDGE_HPP
+#define EDGE_HPP
+
+#include "unordered_pair.hpp"
+
+/**
+ * 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.
+ */
+template <typename VertexDesc, typename PropDesc>
+class undirected_edge
+{
+public:
+    typedef VertexDesc vertex_descriptor;
+    typedef PropDesc property_descriptor;
+    typedef unordered_pair<vertex_descriptor> edge_pair;
+
+    inline undirected_edge();
+    inline undirected_edge(vertex_descriptor u, vertex_descriptor v, property_descriptor p);
+
+    inline edge_pair const& edge() const;
+    inline property_descriptor property() const;
+
+    inline bool operator<(undirected_edge const& x);
+
+private:
+    edge_pair _edge;
+    PropDesc _prop;
+};
+
+template <typename VD, typename PD>
+undirected_edge<VD,PD>::undirected_edge()
+    : _edge()
+    , _prop()
+{ }
+
+template <typename VD, typename PD>
+undirected_edge<VD,PD>::undirected_edge(vertex_descriptor u,
+                                        vertex_descriptor v,
+                                        property_descriptor p)
+    : _edge(u, v)
+    , _prop(p)
+{ }
+
+template <typename VD, typename PD>
+typename undirected_edge<VD,PD>::edge_pair const&
+undirected_edge<VD,PD>::edge() const
+{
+    return _edge;
+}
+
+template <typename VD, typename PD>
+typename undirected_edge<VD,PD>::property_descriptor
+undirected_edge<VD,PD>::property() const
+{
+    return _prop;
+}
+
+template <typename VD, typename PD>
+bool
+undirected_edge<VD,PD>::operator<(undirected_edge const& x)
+{
+    return _edge < x._edge || (!(x._edge < _edge) && _prop < x._prop);
+}
+
+#endif

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge_set.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -3,10 +3,20 @@
 #define EDGE_SET_HPP
 
 #include "property_list.hpp"
+#include "incidence_set.hpp"
 
-// An edge set denotes a) that incident edges are stored in a set for
-// each vertex and b) that properties are stored in a list.
-
+/**
+ * The edge set metafunction defines the basic facets of set-based edge
+ * storage. Edge sets are best used to implement simple graphs (that do not
+ * allow multiple edges).
+ *
+ * There are three parmaters to this function:
+ * Compare - A function that compares vertex descriptors
+ * IncAlloc - An allocator for the edge set
+ * PropAlloc - An allocator for the global property set.
+ *
+ * Note that the edge set uses a map for the incidence store.
+ */
 template <
     template <typename> class Compare,
     template <typename> class IncAlloc,
@@ -18,8 +28,22 @@
     {
         typedef property_list<EdgeProps, PropAlloc<EdgeProps> > type;
     };
+
+    template <typename VertexDesc, typename PropDesc>
+    struct incidence_store
+    {
+        typedef std::pair<VertexDesc, PropDesc> value;
+        typedef Compare<VertexDesc> compare;
+        typedef IncAlloc<value> alloc;
+        typedef incidence_set<value, compare, alloc> type;
+    };
 };
 
+/**
+ * The most common edge set uses standard allocators and allows parameterization
+ * of the comparison function. The comparison function must operate on vertex
+ * descriptors.
+ */
 template <template <typename> class Compare = std::less>
 struct edge_set : basic_edge_set<Compare, std::allocator, std::allocator> { };
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -1,10 +1,18 @@
 
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_LIST_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_LIST_HPP
+#ifndef INCIDENCE_LIST_HPP
+#define INCIDENCE_LIST_HPP
 
 #include <list>
 #include <algorithm>
 
+/**
+ * The incidence vector stores incident "edges" of a vertex. In actuality,
+ * this stores pairs containing an adjacent vertex descriptor and a property
+ * descriptor, that points to the edges global properties. This pair uniquely
+ * identifies incident edges of the vertex.
+ *
+ * This type allows constant time insertions, and linear search and remove.
+ */
 template <typename IncEdge, typename Alloc>
 class incidence_list
 {
@@ -18,16 +26,20 @@
     typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
+    typedef none incidence_iterator;
+
     // Constructors
     incidence_list();
 
-    void add(incidence_pair);
+    inline void add(incidence_pair);
+
+    inline iterator find(incidence_pair);
+    inline const_iterator find(incidence_pair) const;
 
-    iterator find(incidence_pair);
-    const_iterator find(incidence_pair) const;
+    inline void remove(incidence_pair);
+    template <typename Eraser> inline void remove(vertex_descriptor, Eraser);
 
-    void remove(incidence_pair);
-    void clear();
+    inline void clear();
 
     size_type size() const;
 
@@ -36,13 +48,68 @@
 };
 
 #define BOOST_GRAPHS_IL_PARAMS \
-    typename IE, typename A
+    typename E, typename A
 
 template <BOOST_GRAPHS_IL_PARAMS>
-incidence_list<IE,A>::incidence_list()
+incidence_list<E,A>::incidence_list()
     : _edges()
 { }
 
+template <BOOST_GRAPHS_IL_PARAMS>
+void
+incidence_list<E,A>::add(incidence_pair p)
+{
+    _edges.push_back(p);
+}
+
+/**
+ * Remove the incidence pair from the list. This operation is linear with
+ * respect to the number of incident edges.
+ *
+ * @require EqualityComparable<vertex_descriptor>
+ * @require EqualityComparable<property_descriptor>
+ * @complexity O(d)
+ */
+template <BOOST_GRAPHS_IL_PARAMS>
+void
+incidence_list<E,A>::remove(incidence_pair p)
+{
+    // Find the pair in the list and erase it.
+    iterator iter = std::find(_edges.begin(), _edges.end(), p);
+    this->_edges.erase(iter);
+}
+
+/**
+ * Remove the all edges connecting the adjacent vertex from the list. This
+ * operations is exactly linear w.r.t. the number of incident edges.
+ *
+ * @require EqualityComparable<vertex_descriptor>
+ * @require EqualityComparable<property_descriptor>
+ * @complexity Theta(d)
+ */
+template <BOOST_GRAPHS_IL_PARAMS>
+template <typename Eraser>
+void
+incidence_list<E,A>::remove(vertex_descriptor v, Eraser erase)
+{
+    iterator i = _edges.begin(), end = _edges.end();
+    for( ; i != end; ) {
+        if(i->first == v) {
+            i = _edges.erase(i);
+        }
+        else {
+            ++i;
+        }
+    }
+}
+
+template <BOOST_GRAPHS_IL_PARAMS>
+typename incidence_list<E,A>::size_type
+incidence_list<E,A>::size() const
+{
+    return _edges.size();
+}
+
 #if 0
 
 // Functions
@@ -75,13 +142,6 @@
 
 template <typename E>
 void
-vertex_edge_list<E>::remove(edge_descriptor e)
-{
-    this->_store.erase(find(e));
-}
-
-template <typename E>
-void
 vertex_edge_list<E>::clear()
 {
     this->_store.clear();

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -1,96 +1,160 @@
 
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_INCIDENCE_HPP
+#ifndef INCIDENCE_SET_HPP
+#define INCICENCE_SET_HPP
 
-#include <set>
-
-#include <boost/graphs/adjacency_list/is/incidence_store.hpp>
-
-namespace boost {
-namespace graphs {
-namespace adj_list {
+#include <map>
 
 /**
- * The vertex edge set provides set-based storage for edges connected to
- * vertices. This type supports insertions, find, and removal in logarithmic
- * time. Vertex edge sets only work for simple graphs since they preclude the
- * possibility of parallel edges.
+ * The incidence vector stores incident "edges" of a vertex. In actuality,
+ * this stores pairs containing an adjacent vertex descriptor and a property
+ * descriptor, that points to the edges global properties. This pair uniquely
+ * identifies incident edges of the vertex.
+ *
+ * This type allows logarithmic time insertions, searches, and removals.
  */
-template <typename Edge>
-class vertex_edge_set
-    : public vertex_edge_store< std::set<Edge> >
+template <typename IncEdge, typename Compare, typename Alloc>
+class incidence_set
 {
-    typedef vertex_edge_store< std::set<Edge> > base_type;
 public:
-    typedef Edge edge_descriptor;
-    typedef typename base_type::iterator iterator;
-    typedef typename base_type::const_iterator const_iterator;
-    typedef typename base_type::size_type size_type;
+    typedef IncEdge incidence_pair;
+    typedef typename IncEdge::first_type vertex_descriptor;
+    typedef typename IncEdge::second_type property_descriptor;
+private:
+    // Actually, the incident set, as it fundamentally implements a simple
+    // graph is based on a map keyed on the adjacenct vertex and mapped to
+    // the edge properties that describe it.
+    // We're basically undwinding and rebuilding the edge pair for this map.
+    typedef std::map<vertex_descriptor, property_descriptor, Compare, Alloc> store_type;
+public:
+    typedef typename store_type::iterator iterator;
+    typedef typename store_type::const_iterator const_iterator;
+    typedef typename store_type::size_type size_type;
+
+    typedef none incidence_iterator;
 
     // Constructors
-    vertex_edge_set();
+    incidence_set();
+
+    inline void add(incidence_pair);
+
+    inline iterator find(incidence_pair);
+    inline const_iterator find(incidence_pair) const;
+
+    inline void remove(incidence_pair);
+
+    template <typename Eraser>
+    inline void remove(vertex_descriptor, Eraser);
 
-    // Add/Find/Remove interface.
-    inline void add(edge_descriptor e);
-    inline iterator find(edge_descriptor e);
-    inline const_iterator find(edge_descriptor e) const;
-    inline void remove(edge_descriptor e);
     inline void clear();
+
     inline size_type size() const;
+
+private:
+    store_type _edges;
 };
 
 // Functions
 
-template <typename E>
-vertex_edge_set<E>::vertex_edge_set()
-    : base_type()
+#define BOOST_GRAPH_IS_PARAMS \
+    typename E, typename C, typename A
+
+template <BOOST_GRAPH_IS_PARAMS>
+incidence_set<E,C,A>::incidence_set()
+    : _edges()
 { }
 
-template <typename E>
+/**
+ * Add the incidence pair to the set.
+ *
+ * @complexity O(lg(d))
+ */
+template <BOOST_GRAPH_IS_PARAMS>
 void
-vertex_edge_set<E>::add(edge_descriptor e)
+incidence_set<E,C,A>::add(incidence_pair p)
 {
-    this->_store.insert(e);
+    _edges.insert(p);
+}
+
+/**
+ * Remove the incidence pair from the set.
+ *
+ * @complexity O(lg(d))
+ */
+template <BOOST_GRAPH_IS_PARAMS>
+void
+incidence_set<E,C,A>::remove(incidence_pair p)
+{
+    // The erase function takes a key! Not the entire pair.
+    _edges.erase(p.first);
 }
 
+/**
+ * Remove the incident edge indicated by the given vertex and invoke the
+ * erase function on the associated property descriptor.
+ */
+template <BOOST_GRAPH_IS_PARAMS>
+template <typename Erase>
+void
+incidence_set<E,C,A>::remove(vertex_descriptor v, Erase erase)
+{
+    // Find the mapped property descriptor before erasing the edge.
+    iterator iter = _edges.find(v);
+    property_descriptor p = iter->second;
+    _edges.erase(iter);
+
+    // Invoke the eraser to remove the corresponding global property.
+    erase(p);
+}
+
+/**
+ * Return the number of incident edges (degree) in the set.
+ */
+template <BOOST_GRAPH_IS_PARAMS>
+typename incidence_set<E,C,A>::size_type
+incidence_set<E,C,A>::size() const
+{
+    return _edges.size();
+}
+
+#undef BOOST_GRAPH_IS_PARAMS
+
+#if 0
+
 template <typename E>
-typename vertex_edge_set<E>::iterator
-vertex_edge_set<E>::find(edge_descriptor e)
+void
+incidence_set<E>::add(edge_descriptor e)
 {
-    return this->_store.find(e);
+    this->_store.insert(e);
 }
 
 template <typename E>
-typename vertex_edge_set<E>::const_iterator
-vertex_edge_set<E>::find(edge_descriptor e) const
+typename incidence_set<E>::iterator
+incidence_set<E>::find(edge_descriptor e)
 {
     return this->_store.find(e);
 }
 
 template <typename E>
-void
-vertex_edge_set<E>::remove(edge_descriptor e)
+typename incidence_set<E>::const_iterator
+incidence_set<E>::find(edge_descriptor e) const
 {
-    this->_store.erase(e);
+    return this->_store.find(e);
 }
 
 template <typename E>
 void
-vertex_edge_set<E>::clear()
+incidence_set<E>::clear()
 {
     this->_store.clear();
 }
 
 template <typename E>
-typename vertex_edge_set<E>::size_type
-vertex_edge_set<E>::size() const
+typename incidence_set<E>::size_type
+incidence_set<E>::size() const
 {
     return this->_store.size();
 }
 
-
-} /* namespace adj_list */
-} /* namespace graphs */
-} /* namespace boost */
+#endif
 
 #endif

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -5,10 +5,13 @@
 #include <vector>
 
 /**
- * The vertex edge vector provides vector-based storage for edges connected to
- * vertices. This type supports insertions in constant time, and find and
- * remove are supported in linear time. The remove operation will invalidate
- * vertex edge iterators (i.e., in, out, incident, adjacency).
+ * The incidence vector stores incident "edges" of a vertex. In actuality,
+ * this stores pairs containing an adjacent vertex descriptor and a property
+ * descriptor, that points to the edges global properties. This pair uniquely
+ * identifies incident edges of the vertex.
+ *
+ * This type allows constant-time edge addition and a linear search. Removal
+ * is not supported.
  */
 template <typename IncEdge, typename Alloc>
 class incidence_vector
@@ -23,17 +26,16 @@
     typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
+    typedef none incidence_iterator;
+
     // Constructors
     incidence_vector();
 
     void add(incidence_pair);
- 
+
     iterator find(incidence_pair);
     const_iterator find(incidence_pair) const;
 
-    void remove(incidence_pair);
-    void clear();
-
     size_type size() const;
 
 private:

Deleted: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/indexed_vertex_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/indexed_vertex_iterator.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
+++ (empty file)
@@ -1,156 +0,0 @@
-
-#ifndef INDEXED_VERTEX_ITERATOR
-#define INDEXED_VERTEX_ITERATOR
-
-#include <algorithm>
-
-/**
- * The indexed vertex iterator provides a vertex iterator for stores whose
- * descriptors cannot be pointers (i.e., vectors). By virtue of the fact that
- * Store is required to be a vector of something, this is a random access
- * iterator.
- */
-template <typename Store>
-class indexed_vertex_iterator
-{
-    typedef typename Store::const_iterator iterator;
-public:
-    typedef typename Store::value_type vertex_type;
-    typedef typename vertex_type::descriptor_type vertex_descriptor;
-
-    typedef typename iterator::iterator_category iterator_category;
-    typedef typename iterator::difference_type difference_type;
-    typedef vertex_descriptor value_type;
-    typedef vertex_descriptor reference;
-    typedef vertex_descriptor pointer;
-
-    // Constructors
-    inline indexed_vertex_iterator();
-    inline indexed_vertex_iterator(indexed_vertex_iterator const& x);
-    inline indexed_vertex_iterator(Store const& s, iterator const& x);
-
-    // Assignment and increment
-    inline indexed_vertex_iterator& operator=(indexed_vertex_iterator const& x);
-    inline indexed_vertex_iterator& operator+=(difference_type n);
-    inline indexed_vertex_iterator& operator-=(difference_type n);
-    inline indexed_vertex_iterator& operator++();
-    inline indexed_vertex_iterator& operator--();
-
-    inline indexed_vertex_iterator operator+(difference_type n) const;
-    inline indexed_vertex_iterator operator-(difference_type n) const;
-    inline difference_type operator-(indexed_vertex_iterator const& x) const;
-
-    inline reference operator*();
-
-    inline bool operator==(indexed_vertex_iterator const& x) const;
-    inline bool operator!=(indexed_vertex_iterator const& x) const;
-
-private:
-    Store const* store;
-    iterator iter;
-};
-
-template <typename S>
-indexed_vertex_iterator<S>::indexed_vertex_iterator()
-    : store(0)
-    , iter()
-{ }
-
-template <typename S>
-indexed_vertex_iterator<S>::indexed_vertex_iterator(indexed_vertex_iterator const& x)
-    : store(x.store)
-    , iter(x.iter)
-{ }
-
-template <typename S>
-indexed_vertex_iterator<S>::indexed_vertex_iterator(S const& s, iterator const& x)
-    : store(&s)
-    , iter(x)
-{ }
-
-template <typename S>
-indexed_vertex_iterator<S>&
-indexed_vertex_iterator<S>::operator=(indexed_vertex_iterator const& x)
-{
-    iter = x.iter;
-    store = x.store;
-    return *this;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>&
-indexed_vertex_iterator<S>::operator+=(difference_type n)
-{
-    iter += n;
-    return *this;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>&
-indexed_vertex_iterator<S>::operator-=(difference_type n)
-{
-    iter -= n;
-    return *this;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>&
-indexed_vertex_iterator<S>::operator++()
-{
-    ++iter;
-    return *this;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>&
-indexed_vertex_iterator<S>::operator--()
-{
-    --iter;
-    return *this;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>
-indexed_vertex_iterator<S>::operator+(difference_type n) const
-{
-    return iter + n;
-}
-
-template <typename S>
-indexed_vertex_iterator<S>
-indexed_vertex_iterator<S>::operator-(difference_type n) const
-{
-    return iter - n;
-}
-
-template <typename S>
-typename indexed_vertex_iterator<S>::difference_type
-indexed_vertex_iterator<S>::operator-(indexed_vertex_iterator const& x) const
-{
-    return iter - x.iter;
-}
-
-template <typename S>
-typename indexed_vertex_iterator<S>::reference
-indexed_vertex_iterator<S>::operator*()
-{
-    // The returned descriptor is simply the distance from the beginning of
-    // the underlying store to the end.
-    return std::distance(store->begin(), iter);
-}
-
-template <typename S>
-bool
-indexed_vertex_iterator<S>::operator==(indexed_vertex_iterator const& x) const
-{
-     return (store == x.store) && (iter == x.iter);
-}
-
-template <typename S>
-bool
-indexed_vertex_iterator<S>::operator!=(indexed_vertex_iterator const& x) const
-{
-    return (store == x.store) && (iter != x.iter);
-}
-
-#endif

Deleted: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/mapped_vertex_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/mapped_vertex_iterator.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
+++ (empty file)
@@ -1,110 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_MAPPED_VERTEX_ITERATOR_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_MAPPED_VERTEX_ITERATOR_HPP
-
-namespace boost {
-namespace graphs {
-namespace adj_list {
-
-/**
- * The mapped vertex iterator provides a vertex iterator pair associative
- * storage containers. This essintially wraps a store iterator, providing
- * the ability to dererence to descriptors. Because this iterator is taken
- * from pair associative structures, it is bidirectional but not random access.
- */
-template <typename Store>
-class mapped_vertex_iterator
-{
-    typedef typename Store::const_iterator iterator;
-public:
-    typedef typename Store::mapped_type vertex_type;
-    typedef typename vertex_type::descriptor_type vertex_descriptor;
-
-    typedef typename iterator::iterator_category iterator_category;
-    typedef typename iterator::difference_type difference_type;
-    typedef vertex_descriptor value_type;
-    typedef vertex_descriptor reference;
-    typedef vertex_descriptor pointer;
-
-    inline mapped_vertex_iterator();
-    inline mapped_vertex_iterator(mapped_vertex_iterator const& x);
-    inline mapped_vertex_iterator(iterator const& x);
-
-    inline mapped_vertex_iterator& operator=(mapped_vertex_iterator const& x);
-    inline mapped_vertex_iterator& operator++();
-    inline mapped_vertex_iterator& operator--();
-
-    inline reference operator*();
-
-    inline bool operator==(mapped_vertex_iterator const& x) const;
-    inline bool operator!=(mapped_vertex_iterator const& x) const;
-
-private:
-    iterator iter;
-};
-
-template <typename S>
-mapped_vertex_iterator<S>::mapped_vertex_iterator()
-    : iter()
-{ }
-
-template <typename S>
-mapped_vertex_iterator<S>::mapped_vertex_iterator(mapped_vertex_iterator const& x)
-    : iter(x.iter)
-{ }
-
-template <typename S>
-mapped_vertex_iterator<S>::mapped_vertex_iterator(iterator const& x)
-    : iter(x)
-{ }
-
-template <typename S>
-mapped_vertex_iterator<S>&
-mapped_vertex_iterator<S>::operator=(mapped_vertex_iterator const& x)
-{
-    iter = x.iter;
-    return *this;
-}
-
-template <typename S>
-mapped_vertex_iterator<S>&
-mapped_vertex_iterator<S>::operator++()
-{
-    ++iter;
-    return *this;
-}
-
-template <typename S>
-mapped_vertex_iterator<S>&
-mapped_vertex_iterator<S>::operator--()
-{
-    --iter;
-    return *this;
-}
-
-template <typename S>
-typename mapped_vertex_iterator<S>::reference
-mapped_vertex_iterator<S>::operator*()
-{
-    return &const_cast<vertex_type&>(iter->second);
-}
-
-template <typename S>
-bool
-mapped_vertex_iterator<S>::operator==(mapped_vertex_iterator const& x) const
-{
-    return iter == x.iter;
-}
-
-template <typename S>
-bool
-mapped_vertex_iterator<S>::operator!=(mapped_vertex_iterator const& x) const
-{
-    return iter != x.iter;
-}
-
-} /* namespace adj_list */
-} /* namespace graph */
-} /* namespace boost */
-
-#endif

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/none.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/none.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/none.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -5,5 +5,15 @@
 // The canonical none type.
 struct none { };
 
+// A little weird, but there are times when it makes sense to create noop
+// operations. This takes a single parameter.
+template <typename T>
+struct noop
+{
+    typedef void result_type;
+    void operator()(T const&)
+    { }
+};
+
 #endif
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -7,10 +7,11 @@
 // Forward descriptor
 template <typename Iter> class proplist_descriptor;
 
-// The property list implements global list of properties for node-based
-// edge storage. Note that we can get away with only a list because the
-// edge addition logic is implemented by the incidence list.
-
+/**
+ * The property list implements global list of properties for node-based edge
+ * storage. Note that we can get away with only a list because the edge
+ * addition logic is implemented by the incidence list.
+ */
 template <typename Props, typename Alloc>
 class property_list
 {
@@ -19,15 +20,27 @@
     typedef Props property_type;
     typedef proplist_descriptor<typename store_type::iterator> property_descriptor;
 
-    property_list();
+    inline property_list();
+
+    // Add properties
+    inline property_descriptor add();
+    inline property_descriptor add(property_type const&);
+
+    // Remove properties
+    inline void remove(property_descriptor);
 
-    property_descriptor add();
-    property_descriptor add(property_type const&);
+    // Property access.
+    inline property_type& properties(property_descriptor);
 
 private:
     store_type _props;
 };
 
+/**
+ * Partially specialize the property list for the case where the user does
+ * not want properties. This will completely remove the property list from
+ * the graph, instead creating a simple index enumerator.
+ */
 template <typename Alloc>
 class property_list<none, Alloc>
 {
@@ -35,30 +48,15 @@
     typedef std::size_t property_descriptor;
 };
 
-// The proplist descriptor provides a wrapper around a list iterator
-// that provides comparability for the underlying iterator. Note that
-// the comparison has little to do with actual ordering of eleemnts.
-// This is to say that i < j !=> *i < *j. This just provides a mechanism
-// for ordering the descriptors.
-
-template <typename Iter>
-class proplist_descriptor
-{
-    proplist_descriptor(Iter const& iter)
-        : iter(iter)
-    { }
-
-    bool operator <(proplist_descriptor const& x) const
-    { return &*iter < &*x.iter; } 
-
-    Iter iter;
-};
 
 template <typename P, typename A>
 property_list<P,A>::property_list()
     : _props()
 { }
 
+/**
+ * Add an empty or default property to the list.
+ */
 template <typename P, typename A>
 typename property_list<P,A>::property_descriptor
 property_list<P,A>::add()
@@ -66,6 +64,9 @@
     return add(property_type());
 }
 
+/**
+ * Add the specified properties to the list.
+ */
 template <typename P, typename A>
 typename property_list<P,A>::property_descriptor
 property_list<P,A>::add(property_type const& p)
@@ -73,6 +74,74 @@
     return _props.insert(_props.end(), p);
 }
 
+/**
+ * Remove the indicated property from the list. This invalidates any
+ * descriptors and iterators to the given property, but no others.
+ *
+ * @complexity O(1)
+ */
+template <typename P, typename A>
+void
+property_list<P,A>::remove(property_descriptor p)
+{
+    _props.erase(p.iter);
+}
+
+/**
+ * Return the properties corresponding to the given descriptor.
+ */
+template <typename P, typename A>
+typename property_list<P,A>::property_type&
+property_list<P,A>::properties(property_descriptor p)
+{
+    return *p.iter;
+}
+
+/**
+ * The proplist descriptor provides a wrapper around a list iterator that
+ * provides comparability for the underlying iterator. Note that the comparison
+ * has little to do with actual ordering of elements. This is to say that
+ * i \< j !=> *i \< *j. This just provides a mechanism for ordering the
+ * descriptors.
+ */
+template <typename Iter>
+struct proplist_descriptor
+{
+    inline proplist_descriptor(Iter const&);
+
+    inline bool operator==(proplist_descriptor const&) const;
+    inline bool operator<(proplist_descriptor const&) const;
+
+    Iter iter;
+};
+
+template <typename I>
+proplist_descriptor<I>::proplist_descriptor(I const& iter)
+    : iter(iter)
+{ }
+
+template <typename I>
+bool
+proplist_descriptor<I>::operator==(proplist_descriptor const& x) const
+{
+    return iter == x.iter;
+}
+
+template <typename I>
+bool
+proplist_descriptor<I>::operator<(proplist_descriptor const& x) const
+{
+    return &*iter < &*x.iter;
+}
+
+// Property list algorithm objects
+template <typename PropList>
+struct eraser
+{
+    eraser(PropList& props)
+    { }
+};
+
 
 #endif
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_vector.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -21,6 +21,8 @@
     property_descriptor add();
     property_descriptor add(property_type const&);
 
+    property_type& properties(property_descriptor);
+
 private:
     store_type _props;
 };
@@ -52,5 +54,15 @@
     return _props.size() - 1;
 }
 
+/**
+ * Return the properties corresponding to the given descriptor.
+ */
+template <typename P, typename A>
+typename property_vector<P,A>::property_type&
+property_vector<P,A>::properties(property_descriptor p)
+{
+    return _props[p];
+}
+
 #endif
 

Deleted: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/simple_vertex_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/simple_vertex_iterator.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
+++ (empty file)
@@ -1,103 +0,0 @@
-
-#ifndef SIMPLE_VERTEX_ITERATOR_HPP
-#define SIMPLE_VERTEX_ITERATOR_HPP
-
-#include <iterator>
-
-/**
- * The value vertex iterator provides a vertex iterator unique associative
- * containers and sequences that don't invalidate memory on insertions
- * (lists).
- */
-template <typename Store>
-class simple_vertex_iterator
-{
-    typedef typename Store::const_iterator iterator;
-public:
-    typedef typename Store::value_type vertex_type;
-    typedef typename vertex_type::descriptor_type vertex_descriptor;
-
-    typedef typename iterator::iterator_category iterator_category;
-    typedef typename iterator::difference_type difference_type;
-    typedef vertex_descriptor value_type;
-    typedef vertex_descriptor reference;
-    typedef vertex_descriptor pointer;
-
-    inline simple_vertex_iterator();
-    inline simple_vertex_iterator(simple_vertex_iterator const& x);
-    inline simple_vertex_iterator(iterator const& x);
-
-    inline simple_vertex_iterator& operator=(simple_vertex_iterator const& x);
-    inline simple_vertex_iterator& operator++();
-    inline simple_vertex_iterator& operator--();
-
-    inline reference operator*();
-
-    inline bool operator==(simple_vertex_iterator const& x) const;
-    inline bool operator!=(simple_vertex_iterator const& x) const;
-
-private:
-    iterator iter;
-};
-
-template <typename S>
-simple_vertex_iterator<S>::simple_vertex_iterator()
-    : iter()
-{ }
-
-template <typename S>
-simple_vertex_iterator<S>::simple_vertex_iterator(simple_vertex_iterator const& x)
-    : iter(x.iter)
-{ }
-
-template <typename S>
-simple_vertex_iterator<S>::simple_vertex_iterator(iterator const& x)
-    : iter(x)
-{ }
-
-template <typename S>
-simple_vertex_iterator<S>&
-simple_vertex_iterator<S>::operator=(simple_vertex_iterator const& x)
-{
-    iter = x.iter;
-    return *this;
-}
-
-template <typename S>
-simple_vertex_iterator<S>&
-simple_vertex_iterator<S>::operator++()
-{
-    ++iter;
-    return *this;
-}
-
-template <typename S>
-simple_vertex_iterator<S>&
-simple_vertex_iterator<S>::operator--()
-{
-    --iter;
-    return *this;
-}
-
-template <typename S>
-typename simple_vertex_iterator<S>::reference
-simple_vertex_iterator<S>::operator*()
-{
-    return &const_cast<vertex_type&>(*iter);
-}
-
-template <typename S>
-bool
-simple_vertex_iterator<S>::operator==(simple_vertex_iterator const& x) const
-{
-    return iter == x.iter;
-}
-
-template <typename S>
-bool
-simple_vertex_iterator<S>::operator!=(simple_vertex_iterator const& x) const
-{
-    return iter != x.iter;
-}
-
-#endif

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -2,6 +2,8 @@
 #ifndef UNDIRECTED_GRAPH_HPP
 #define UNDIRECTED_GRAPH_HPP
 
+#include <boost/bind.hpp>
+
 #include "none.hpp"
 
 // Various issues...
@@ -17,11 +19,15 @@
 //   need to exist. We can just pretend to allocate them and return
 //   an integer "pseudo descriptor".
 
+#include "descriptor.hpp"
+
 #include "vertex.hpp"
+#include "vertex_iterator.hpp"
 #include "vertex_vector.hpp"
 #include "vertex_list.hpp"
+#include "vertex_set.hpp"
 
-#include "descriptor.hpp"
+#include "edge.hpp"
 #include "edge_vector.hpp"
 #include "edge_list.hpp"
 #include "edge_set.hpp"
@@ -48,12 +54,13 @@
     // store and the edge descriptor is actually fairly complicated.
     typedef typename VertexStore::descriptor_type vertex_descriptor;
     typedef typename property_store::property_descriptor property_descriptor;
-    typedef undirected_edge_descriptor<vertex_descriptor, property_descriptor> edge_descriptor;
+    typedef undirected_edge<vertex_descriptor, property_descriptor> edge_descriptor;
 
     // Generate the incidence list. The incidence list for a single vertex
     // contains a pair: the opposite edge and a property descriptor.
     typedef typename EdgeStore::template incidence_store<vertex_descriptor, property_descriptor>::type incidence_store;
-    typedef typename incidence_store::size_type incidence_size_type;
+    typedef typename incidence_store::size_type incident_edges_size_type;
+    typedef typename incidence_store::incidence_iterator incident_edge_iterator;
 
     // Generate the vertex type over the given properties and the incidence
     // store. Then, turn around and use that to generate the vertex store and its
@@ -61,6 +68,8 @@
     typedef vertex<vertex_properties, incidence_store> vertex_type;
     typedef typename VertexStore::template store<vertex_type>::type vertex_store;
     typedef typename vertex_store::size_type vertices_size_type;
+    typedef typename vertex_store::vertex_iterator vertex_iterator;
+    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.
@@ -74,68 +83,223 @@
     vertex_descriptor add_vertex(vertex_properties const&);
     vertex_descriptor add_vertex(key_type const&, vertex_properties const&);
 
+    // Remove vertices
+    void remove_vertex(vertex_descriptor);
+
     // Add edges
     edge_descriptor add_edge(vertex_descriptor, vertex_descriptor);
     edge_descriptor add_edge(vertex_descriptor, vertex_descriptor, edge_properties const&);
 
+    void remove_edge(edge_descriptor);
+    void remove_edges(vertex_descriptor, vertex_descriptor);
+
+    vertex_range vertices() const;
+    vertex_iterator begin_vertices() const;
+    vertex_iterator end_vertices() const;
     vertices_size_type num_vertices() const;
 
-    incidence_size_type degree() const;
+    incident_edges_size_type degree(vertex_descriptor) const;
+
+    vertex_properties& operator[](vertex_descriptor);
+    edge_properties& operator[](edge_descriptor);
 
 private:
     property_store _props;
     vertex_store _verts;
 };
 
-#define BOOST_GRAPHS_UG_PARAMS \
+#define BOOST_GRAPH_UG_PARAMS \
     typename VP, typename EP, typename VS, typename ES
 
-template <BOOST_GRAPHS_UG_PARAMS>
+template <BOOST_GRAPH_UG_PARAMS>
 undirected_graph<VP,EP,VS,ES>::undirected_graph()
     : _props()
     , _verts()
 { }
 
-template <BOOST_GRAPHS_UG_PARAMS>
+template <BOOST_GRAPH_UG_PARAMS>
 typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
 undirected_graph<VP,EP,VS,ES>::add_vertex()
 {
     return _verts.add();
 }
 
-template <BOOST_GRAPHS_UG_PARAMS>
+template <BOOST_GRAPH_UG_PARAMS>
 typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
 undirected_graph<VP,EP,VS,ES>::add_vertex(vertex_properties const& vp)
 {
     return _verts.add(vp);
 }
 
-template <BOOST_GRAPHS_UG_PARAMS>
+/**
+ * Remove the vertex from the graph. This will disconnect the vertex from the
+ * graph prior to remove.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_descriptor v)
+{
+    _verts.remove(v);
+}
+
+/**
+ * Create an edge, connecting the vertices u and v.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
 typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
 undirected_graph<VP,EP,VS,ES>::add_edge(vertex_descriptor u, vertex_descriptor v)
 {
     // Start by getting a property descriptor for the edge.
     property_descriptor p = _props.add();
-    vertex_type& vert = _verts.vertex(u);
-    vert.connect(v, p);
+    vertex_type& src = _verts.vertex(u);
+    vertex_type& tgt = _verts.vertex(v);
+    src.connect(v, p);
+    tgt.connect(u, p);
 
-    return edge_descriptor();
+    return edge_descriptor(u, v, p);
 }
 
-template <BOOST_GRAPHS_UG_PARAMS>
+/**
+ * Create an edge with the given properties that connects the vertices u and v.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
+undirected_graph<VP,EP,VS,ES>::add_edge(vertex_descriptor u,
+                                        vertex_descriptor v,
+                                        edge_properties const& ep)
+{
+    // Start by getting a property descriptor for the edge.
+    property_descriptor p = _props.add(ep);
+    vertex_type& src = _verts.vertex(u);
+    vertex_type& tgt = _verts.vertex(v);
+    src.connect(v, p);
+    tgt.connect(u, p);
+
+    return edge_descriptor(u, v, p);
+}
+
+/**
+ * Remove only the given edge from graph. This disconnects both vertices in
+ * the edge and removes the property from the graph.
+ *
+ * @requires HasRemove<edge_store>
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
+{
+    // Cache some useful info for the erasure.
+    property_descriptor p = e.property();
+    vertex_descriptor u = e.edge().first();
+    vertex_descriptor v = e.edge().second();
+    vertex_type& src = _verts.vertex(u);
+    vertex_type& tgt = _verts.vertex(v);
+
+    // Disconnect the incidence ends and then remove the property from
+    // the global property store.
+    src.disconnect(v, p);
+    tgt.disconnect(u, p);
+    _props.remove(p);
+}
+
+/**
+ * This removes all distinct edges connecting the vertices u and v.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor u,
+                                            vertex_descriptor v)
+{
+    using boost::bind;
+    using boost::ref;
+
+    // The implementation of this function is... not pretty because of the
+    // number of efficient ways to do this for both lists, sets and maps.
+    // Remember that we have to remove the same basic edge structures from
+    // both source and target, but only need to remove the global properties
+    // once.
+
+    vertex_type& src = _verts.vertex(u);
+    vertex_type& tgt = _verts.vertex(v);
+
+    // Disconnect v from the src, removing global properties,. Then disconnect
+    // u from tgt, but don't actually do anything with the properties (they're
+    // already gone!).
+    src.disconnect(v, bind(&property_store::remove, ref(_props), _1));
+    tgt.disconnect(u, bind(noop<property_descriptor>(), _1));
+}
+
+/**
+ * Return an iterator range over the vertices of the graph.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_range
+undirected_graph<VP,EP,VS,ES>::vertices() const
+{
+    return _verts.vertices();
+}
+
+/**
+ * Return an iterator to the first iterator in the graph.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_iterator
+undirected_graph<VP,EP,VS,ES>::begin_vertices() const
+{
+    return _verts.begin_vertices();
+}
+
+/**
+ * Return an iterator past the end of the vertices in the graph.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_iterator
+undirected_graph<VP,EP,VS,ES>::end_vertices() const
+{
+    return _verts.end_vertices();
+}
+
+/**
+ * Return the number of iterators in this graph.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
 typename undirected_graph<VP,EP,VS,ES>::vertices_size_type
 undirected_graph<VP,EP,VS,ES>::num_vertices() const
-{ 
-    return _verts.size(); 
+{
+    return _verts.size();
 }
 
-template <BOOST_GRAPHS_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::incidence_size_type
+/**
+ * Return the degree (number of incdent edges) of the given vertex.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::incident_edges_size_type
 undirected_graph<VP,EP,VS,ES>::degree(vertex_descriptor v) const
 {
+    return _verts.vertex(v).degree();
+}
+
+/**
+ * Return the properties for the given vertex.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_properties&
+undirected_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v)
+{
+    return _verts.properties(v);
+}
+
+/**
+ * Return the properties for the given edge.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::edge_properties&
+undirected_graph<VP,EP,VS,ES>::operator[](edge_descriptor e)
+{
+    return _props.properties(e.prop);
 }
 
-#undef BOOST_GRAPHS_UG_PARAMS
+#undef BOOST_GRAPH_UG_PARAMS
 
 #endif
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -2,7 +2,7 @@
 #ifndef VERTEX_HPP
 #define VERTEX_HPP
 
-// A vertex, at least for an undirected graph, is simply an repository 
+// A vertex, at least for an undirected graph, is simply an repository
 // for the vertex' properties and an interface for the its incidence
 // list.
 //
@@ -19,10 +19,20 @@
     typedef typename incidence_store::vertex_descriptor vertex_descriptor;
     typedef typename incidence_store::property_descriptor property_descriptor;
 
-    vertex();
-    vertex(vertex_properties const& vp);
+    typedef typename incidence_store::size_type incidence_size_type;
 
-    void connect(vertex_descriptor, property_descriptor);
+    inline vertex();
+    inline vertex(vertex_properties const& vp);
+
+    inline void connect(vertex_descriptor, property_descriptor);
+    inline void disconnect(vertex_descriptor, property_descriptor);
+    template <typename Eraser> inline void disconnect(vertex_descriptor, Eraser);
+
+    inline incidence_size_type degree() const;
+
+    inline vertex_properties& properties();
+
+    inline bool operator<(vertex const&) const;
 
 private:
     vertex_properties _props;
@@ -41,6 +51,9 @@
     , _edges()
 { }
 
+/**
+ * Connect this vertex to the vertex v with edge properties p.
+ */
 template <typename VP, typename IS>
 void
 vertex<VP,IS>::connect(vertex_descriptor v, property_descriptor p)
@@ -48,5 +61,58 @@
     _edges.add(make_pair(v, p));
 }
 
+/**
+ * Disconnect the incidedent edge given by the vertex v with edge properties p.
+ */
+template <typename VP, typename IS>
+void
+vertex<VP,IS>::disconnect(vertex_descriptor v, property_descriptor p)
+{
+    _edges.remove(make_pair(v, p));
+}
+
+template <typename VP, typename IS>
+template <typename Eraser>
+void
+vertex<VP,IS>::disconnect(vertex_descriptor v, Eraser erase)
+{
+    _edges.remove(v, erase);
+}
+
+/**
+ * Return the degree (number of incident edges) of this vertex.
+ */
+template <typename VP, typename IS>
+typename vertex<VP,IS>::incidence_size_type
+vertex<VP,IS>::degree() const
+{
+    return _edges.size();
+}
+
+/**
+ * Return the properties associated with this vertex (if any).
+ */
+template <typename VP, typename IS>
+typename vertex<VP,IS>::vertex_properties&
+vertex<VP,IS>::properties()
+{
+    return _props;
+}
+
+/**
+ * The default comparison of vertices always delegates the comparison to the
+ * stored vertex properties. This allows developers to express custom
+ * comparitors with respect to the properties and have the vertex sets or other
+ * vertex ordering operations work as they might expect.
+ *
+ * @requires LessThanComparable<vertex_properties>.
+ */
+template <typename VP, typename IS>
+bool
+vertex<VP,IS>::operator<(vertex const& v) const
+{
+    return _props < v._props;
+}
+
 #endif
 

Added: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_iterator.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -0,0 +1,369 @@
+
+#ifndef VERTEX_ITERATOR_HPP
+#define VERTEX_ITERATOR_HPP
+
+// This file is a little gross. Basically, I'm cramming three different classes
+// and their implementations into it. This file contains:
+// 1. indexed_vertex_iterator
+// 2. simple_vertex_iterator
+// 3. mapped_vertex_iterator
+// Functions for these follow all the class definitions.
+// TODO Consider inlining all the functions for some degree of brevity.
+
+/**
+ * The indexed vertex iterator provides a vertex iterator for stores whose
+ * descriptors cannot be pointers (i.e., vectors). By virtue of the fact that
+ * Store is required to be a vector of something, this is a random access
+ * iterator.
+ */
+template <typename Store>
+class indexed_vertex_iterator
+{
+    typedef typename Store::const_iterator iterator;
+public:
+    typedef typename Store::value_type vertex_type;
+    typedef typename vertex_type::vertex_descriptor vertex_descriptor;
+
+    typedef typename iterator::iterator_category iterator_category;
+    typedef typename iterator::difference_type difference_type;
+    typedef vertex_descriptor value_type;
+    typedef vertex_descriptor reference;
+    typedef vertex_descriptor pointer;
+
+    // Constructors
+    inline indexed_vertex_iterator();
+    inline indexed_vertex_iterator(indexed_vertex_iterator const& x);
+    inline indexed_vertex_iterator(Store const& s, iterator const& x);
+
+    // Assignment and increment
+    inline indexed_vertex_iterator& operator=(indexed_vertex_iterator const& x);
+    inline indexed_vertex_iterator& operator+=(difference_type n);
+    inline indexed_vertex_iterator& operator-=(difference_type n);
+    inline indexed_vertex_iterator& operator++();
+    inline indexed_vertex_iterator& operator--();
+
+    inline indexed_vertex_iterator operator+(difference_type n) const;
+    inline indexed_vertex_iterator operator-(difference_type n) const;
+    inline difference_type operator-(indexed_vertex_iterator const& x) const;
+
+    inline reference operator*();
+
+    inline bool operator==(indexed_vertex_iterator const& x) const;
+    inline bool operator!=(indexed_vertex_iterator const& x) const;
+
+private:
+    Store const* store;
+    iterator iter;
+};
+
+/**
+ * The value vertex iterator provides a vertex iterator unique associative
+ * containers and sequences that don't invalidate memory on insertions
+ * (lists).
+ */
+template <typename Store>
+class simple_vertex_iterator
+{
+    typedef typename Store::const_iterator iterator;
+public:
+    typedef typename Store::value_type vertex_type;
+    typedef typename vertex_type::vertex_descriptor vertex_descriptor;
+
+    typedef typename iterator::iterator_category iterator_category;
+    typedef typename iterator::difference_type difference_type;
+    typedef vertex_descriptor value_type;
+    typedef vertex_descriptor reference;
+    typedef vertex_descriptor pointer;
+
+    inline simple_vertex_iterator();
+    inline simple_vertex_iterator(simple_vertex_iterator const& x);
+    inline simple_vertex_iterator(iterator const& x);
+
+    inline simple_vertex_iterator& operator=(simple_vertex_iterator const& x);
+    inline simple_vertex_iterator& operator++();
+    inline simple_vertex_iterator& operator--();
+
+    inline reference operator*();
+
+    inline bool operator==(simple_vertex_iterator const& x) const;
+    inline bool operator!=(simple_vertex_iterator const& x) const;
+
+private:
+    iterator iter;
+};
+
+
+/**
+ * The mapped vertex iterator provides a vertex iterator pair associative
+ * storage containers. This essintially wraps a store iterator, providing
+ * the ability to dererence to descriptors. Because this iterator is taken
+ * from pair associative structures, it is bidirectional but not random access.
+ */
+template <typename Store>
+class mapped_vertex_iterator
+{
+    typedef typename Store::const_iterator iterator;
+public:
+    typedef typename Store::mapped_type vertex_type;
+    typedef typename vertex_type::vertex_descriptor vertex_descriptor;
+
+    typedef typename iterator::iterator_category iterator_category;
+    typedef typename iterator::difference_type difference_type;
+    typedef vertex_descriptor value_type;
+    typedef vertex_descriptor reference;
+    typedef vertex_descriptor pointer;
+
+    inline mapped_vertex_iterator();
+    inline mapped_vertex_iterator(mapped_vertex_iterator const& x);
+    inline mapped_vertex_iterator(iterator const& x);
+
+    inline mapped_vertex_iterator& operator=(mapped_vertex_iterator const& x);
+    inline mapped_vertex_iterator& operator++();
+    inline mapped_vertex_iterator& operator--();
+
+    inline reference operator*();
+
+    inline bool operator==(mapped_vertex_iterator const& x) const;
+    inline bool operator!=(mapped_vertex_iterator const& x) const;
+
+private:
+    iterator iter;
+};
+
+//
+// Indexed Vertex Iterator Functions
+//
+
+template <typename S>
+indexed_vertex_iterator<S>::indexed_vertex_iterator()
+    : store(0)
+    , iter()
+{ }
+
+template <typename S>
+indexed_vertex_iterator<S>::indexed_vertex_iterator(indexed_vertex_iterator const& x)
+    : store(x.store)
+    , iter(x.iter)
+{ }
+
+template <typename S>
+indexed_vertex_iterator<S>::indexed_vertex_iterator(S const& s, iterator const& x)
+    : store(&s)
+    , iter(x)
+{ }
+
+template <typename S>
+indexed_vertex_iterator<S>&
+indexed_vertex_iterator<S>::operator=(indexed_vertex_iterator const& x)
+{
+    iter = x.iter;
+    store = x.store;
+    return *this;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>&
+indexed_vertex_iterator<S>::operator+=(difference_type n)
+{
+    iter += n;
+    return *this;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>&
+indexed_vertex_iterator<S>::operator-=(difference_type n)
+{
+    iter -= n;
+    return *this;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>&
+indexed_vertex_iterator<S>::operator++()
+{
+    ++iter;
+    return *this;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>&
+indexed_vertex_iterator<S>::operator--()
+{
+    --iter;
+    return *this;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>
+indexed_vertex_iterator<S>::operator+(difference_type n) const
+{
+    return iter + n;
+}
+
+template <typename S>
+indexed_vertex_iterator<S>
+indexed_vertex_iterator<S>::operator-(difference_type n) const
+{
+    return iter - n;
+}
+
+template <typename S>
+typename indexed_vertex_iterator<S>::difference_type
+indexed_vertex_iterator<S>::operator-(indexed_vertex_iterator const& x) const
+{
+    return iter - x.iter;
+}
+
+template <typename S>
+typename indexed_vertex_iterator<S>::reference
+indexed_vertex_iterator<S>::operator*()
+{
+    // The returned descriptor is simply the distance from the beginning of
+    // the underlying store to the end.
+    return std::distance(store->begin(), iter);
+}
+
+template <typename S>
+bool
+indexed_vertex_iterator<S>::operator==(indexed_vertex_iterator const& x) const
+{
+     return (store == x.store) && (iter == x.iter);
+}
+
+template <typename S>
+bool
+indexed_vertex_iterator<S>::operator!=(indexed_vertex_iterator const& x) const
+{
+    return (store == x.store) && (iter != x.iter);
+}
+
+
+//
+// Simple Vertex Iterator Functions
+//
+
+template <typename S>
+simple_vertex_iterator<S>::simple_vertex_iterator()
+    : iter()
+{ }
+
+template <typename S>
+simple_vertex_iterator<S>::simple_vertex_iterator(simple_vertex_iterator const& x)
+    : iter(x.iter)
+{ }
+
+template <typename S>
+simple_vertex_iterator<S>::simple_vertex_iterator(iterator const& x)
+    : iter(x)
+{ }
+
+template <typename S>
+simple_vertex_iterator<S>&
+simple_vertex_iterator<S>::operator=(simple_vertex_iterator const& x)
+{
+    iter = x.iter;
+    return *this;
+}
+
+template <typename S>
+simple_vertex_iterator<S>&
+simple_vertex_iterator<S>::operator++()
+{
+    ++iter;
+    return *this;
+}
+
+template <typename S>
+simple_vertex_iterator<S>&
+simple_vertex_iterator<S>::operator--()
+{
+    --iter;
+    return *this;
+}
+
+template <typename S>
+typename simple_vertex_iterator<S>::reference
+simple_vertex_iterator<S>::operator*()
+{
+    return &const_cast<vertex_type&>(*iter);
+}
+
+template <typename S>
+bool
+simple_vertex_iterator<S>::operator==(simple_vertex_iterator const& x) const
+{
+    return iter == x.iter;
+}
+
+template <typename S>
+bool
+simple_vertex_iterator<S>::operator!=(simple_vertex_iterator const& x) const
+{
+    return iter != x.iter;
+}
+
+//
+// Mapped Vertex Iterator Functions
+
+template <typename S>
+mapped_vertex_iterator<S>::mapped_vertex_iterator()
+    : iter()
+{ }
+
+template <typename S>
+mapped_vertex_iterator<S>::mapped_vertex_iterator(mapped_vertex_iterator const& x)
+    : iter(x.iter)
+{ }
+
+template <typename S>
+mapped_vertex_iterator<S>::mapped_vertex_iterator(iterator const& x)
+    : iter(x)
+{ }
+
+template <typename S>
+mapped_vertex_iterator<S>&
+mapped_vertex_iterator<S>::operator=(mapped_vertex_iterator const& x)
+{
+    iter = x.iter;
+    return *this;
+}
+
+template <typename S>
+mapped_vertex_iterator<S>&
+mapped_vertex_iterator<S>::operator++()
+{
+    ++iter;
+    return *this;
+}
+
+template <typename S>
+mapped_vertex_iterator<S>&
+mapped_vertex_iterator<S>::operator--()
+{
+    --iter;
+    return *this;
+}
+
+template <typename S>
+typename mapped_vertex_iterator<S>::reference
+mapped_vertex_iterator<S>::operator*()
+{
+    return &const_cast<vertex_type&>(iter->second);
+}
+
+template <typename S>
+bool
+mapped_vertex_iterator<S>::operator==(mapped_vertex_iterator const& x) const
+{
+    return iter == x.iter;
+}
+
+template <typename S>
+bool
+mapped_vertex_iterator<S>::operator!=(mapped_vertex_iterator const& x) const
+{
+    return iter != x.iter;
+}
+
+
+#endif

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_list.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -5,16 +5,23 @@
 #include <list>
 
 #include "descriptor.hpp"
-#include "simple_vertex_iterator.hpp"
 
 // Forward declarations
 template <typename V, template <typename> class A> class vertex_list_elem;
 template <typename V, typename A> class vertex_list_impl;
 
+/**
+ * This metafunctiopn defines the basic elements of a vertex list.
+ *
+ * FIXME: We can probably rebuild the descriptor as an iterator into the
+ * underlying store by defining it as a buffer the same size as a fake store
+ * iterator and then re-casting the buffered data as an iterator whenever we
+ * need it. That's a bit hacky, but it gets rid of redundant storage.
+ */
 template <template <typename> class Allocator>
 struct basic_vertex_list
 {
-    typedef void* key_type;
+    typedef none key_type;
     typedef void* descriptor_type;
 
     template <typename Vertex>
@@ -25,8 +32,15 @@
     };
 };
 
+/**
+ * The default vertex list uses the standard allocator.
+ */
 struct vertex_list : basic_vertex_list<std::allocator> { };
 
+/**
+ * Pad the vertex type with an iterator back into the list. See above for a
+ * way around this.
+ */
 template <typename Vertex, template <typename> class Alloc>
 class vertex_list_elem
     : public Vertex
@@ -44,14 +58,6 @@
 };
 
 /**
- * The basic_vertex_list 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.
- *
- * 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.
  *
  * FIXME: Track the size of the list, so that num_vertices() is constant.
  */
@@ -61,11 +67,15 @@
     typedef std::list<Vertex, Allocator> vertex_store;
 public:
     typedef void* vertex_descriptor;
+
     typedef Vertex vertex_type;
     typedef typename Vertex::vertex_properties vertex_properties;
     typedef typename vertex_store::size_type size_type;
-    typedef simple_vertex_iterator<vertex_store> iterator;
-    typedef std::pair<iterator, iterator> range;
+    typedef typename vertex_store::iterator iterator;
+    typedef typename vertex_store::const_iterator const_iterator;
+
+    typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+    typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
 
     // Constructors
     vertex_list_impl();
@@ -81,9 +91,9 @@
     size_type size() const;
 
     // Vertex iteration.
-    range vertices() const;
-    iterator begin() const;
-    iterator end() const;
+    vertex_range vertices() const;
+    vertex_iterator begin_vertices() const;
+    vertex_iterator end_vertices() const;
 
     // Vertex accessors.
     vertex_type& vertex(vertex_descriptor);
@@ -95,13 +105,13 @@
     vertex_store _verts;
 };
 
-#define BOOST_GRAPHS_VL_PARAMS \
+#define BOOST_GRAPH_VL_PARAMS \
     typename V, typename A
 
 /**
  * Construct an empty vertex list.
  */
-template <BOOST_GRAPHS_VL_PARAMS>
+template <BOOST_GRAPH_VL_PARAMS>
 vertex_list_impl<V,A>::vertex_list_impl()
     : _verts()
 { }
@@ -111,7 +121,7 @@
  *
  * @complexity O(1)
  */
-template <BOOST_GRAPHS_VL_PARAMS>
+template <BOOST_GRAPH_VL_PARAMS>
 typename vertex_list_impl<V,A>::vertex_descriptor
 vertex_list_impl<V,A>::add()
 {
@@ -126,7 +136,7 @@
  *
  * @complexity O(1)
  */
-template <BOOST_GRAPHS_VL_PARAMS>
+template <BOOST_GRAPH_VL_PARAMS>
 typename vertex_list_impl<V,A>::vertex_descriptor
 vertex_list_impl<V,A>::add(vertex_properties const& vp)
 {
@@ -136,32 +146,93 @@
 }
 
 /**
+ * Remove a vertex from the set. Removing a vertex will invalidate all vertex
+ * descriptors and iterators to the removed vertex.
+ *
+ * @complexity O(1)
+ */
+template <BOOST_GRAPH_VL_PARAMS>
+void
+vertex_list_impl<V,A>::remove(vertex_descriptor v)
+{
+    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_GRAPHS_VL_PARAMS>
+template <BOOST_GRAPH_VL_PARAMS>
 typename vertex_list_impl<V,A>::size_type
 vertex_list_impl<V,A>::size() const
 {
     return _verts.size();
 }
 
-#if 0
+/**
+ * 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);
+}
 
 /**
- * Remove a vertex from the store.
- *
- * Removing a vertex will invalidate all vertex and edge descriptors.
- *
- * @complexity O(|V|)
+ * Get access to the given vertex.
  */
-template <typename V, template <typename> class A>
-void
-vertex_list_impl<V,A>::remove_vertex(vertex_descriptor v)
+template <BOOST_GRAPH_VL_PARAMS>
+typename vertex_list_impl<V,A>::vertex_type const&
+vertex_list_impl<V,A>::vertex(vertex_descriptor v) const
 {
-    vertex_type* vp = static_cast<vertex_type*>(v);
-    _verts.erase(vp->iter);
+    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.
  *
@@ -211,35 +282,6 @@
     return _verts.end();
 }
 
-/**
- * Get access to the given vertex.
- */
-template <typename V, template <typename> class A>
-typename vertex_list_impl<V,A>::vertex_type&
-vertex_list_impl<V,A>::vertex(vertex_descriptor v)
-{
-    return *static_cast<vertex_type*>(v.desc);
-}
-
-/**
- * Get access to the given vertex.
- */
-template <typename V, template <typename> class A>
-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.desc);
-}
-
-/**
- * Access the properties ofthe given vertex.
- */
-template <typename V, template <typename> class A>
-typename vertex_list_impl<V,A>::vertex_properties&
-vertex_list_impl<V,A>::properties(vertex_descriptor v)
-{
-    return *vertex(v);
-}
 
 /**
  * Access the properties ofthe given vertex.

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_set.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -1,43 +1,48 @@
 
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_SET_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_SET_HPP
+#ifndef VERTEX_SET_HPP
+#define VERTEX_SET_HPP
 
 #include <set>
-#include <tr1/unordered_map>
-
-#include <boost/graphs/adjacency_list/descriptor.hpp>
-#include <boost/graphs/adjacency_list/vs/simple_vertex_iterator.hpp>
-
-namespace boost {
-namespace graphs {
-namespace adj_list {
 
 // Forward declarations
-template <typename V, template <typename> class C, template <typename> class A> class vertex_set_elem;
-template <typename V, typename C, typename A> class vertex_set_impl;
+template <typename, template <typename> class, template <typename> class> class vertex_set_elem;
+template <typename, typename, typename> class vertex_set_impl;
 
-template <template <typename> class Compare, template <typename> class Allocator>
+/**
+ * This metafunction defines the implementation requirements of a set of
+ * verties.
+ */
+template <template <typename> class Compare, template <typename> class Alloc>
 struct basic_vertex_set
 {
-    typedef basic_vertex_descriptor<void*> descriptor_type;
+    typedef none key_type;
+    typedef void* descriptor_type;
 
     template <typename Vertex>
     struct store
     {
-        typedef vertex_set_elem<Vertex, Compare, Allocator> stored_vertex;
-        typedef vertex_set_impl<stored_vertex, Compare<stored_vertex>, Allocator<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;
     };
 };
 
+/**
+ * The most common vertex set allows parameterization over the comparator used
+ * to sort vertices and uses the standard omnibus allocator.
+ */
 template <template <typename> class Compare = std::less>
 struct vertex_set : basic_vertex_set<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 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.
+ */
 template <typename Vertex,
-        template <typename> class Compare,
-        template <typename> class Alloc>
+    template <typename> class Compare,
+    template <typename> class Alloc>
 class vertex_set_elem
     : public Vertex
 {
@@ -52,35 +57,30 @@
         , iter()
     { }
 
+    inline bool operator<(this_type const& x) const
+    { return Vertex::operator<(static_cast<Vertex const&>(x)); }
+
     iterator iter;
 };
 
 /**
- * The vertex_set_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.
- *
- * 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>
+ * Implementation of the vertex set. This requires that vertices (actually
+ * their properties) are less-than comparable.
  */
 template <typename Vertex, typename Compare, typename Allocator>
 class vertex_set_impl
 {
     typedef std::set<Vertex, Compare, Allocator> vertex_store;
 public:
+    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 typename vertex_store::size_type size_type;
+    typedef typename vertex_store::iterator iterator;
+    typedef typename vertex_store::const_iterator const_iterator;
+
+
     typedef simple_vertex_iterator<vertex_store> vertex_iterator;
     typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
 
@@ -88,21 +88,19 @@
     vertex_set_impl();
 
     // Add vertices. Note that you can't add without properties.
-    vertex_descriptor add_vertex(vertex_properties const& vp);
-    std::pair<vertex_descriptor, bool> insert_vertex(vertex_properties const& vp);
+    vertex_descriptor add(vertex_properties const& vp);
 
     // Remove vertices.
-    void remove_vertex(vertex_descriptor v);
-    void remove_vertex(vertex_properties const& v);
+    void remove(vertex_descriptor v);
 
     // Find a vertex based on its properties.
-    vertex_descriptor find_vertex(vertex_properties const& vp) const;
+    vertex_descriptor find(vertex_properties const& vp) const;
 
     // Number of vertices.
-    vertices_size_type num_vertices() const;
+    size_type size() const;
 
     // Vertex iteration.
-    std::pair<vertex_iterator, vertex_iterator> vertices() const;
+    vertex_range vertices() const;
     vertex_iterator begin_vertices() const;
     vertex_iterator end_vertices() const;
 
@@ -117,15 +115,124 @@
 };
 
 
-#define BOOST_GRAPHS_VS_PARAMS \
+#define BOOST_GRAPH_VS_PARAMS \
     typename V, typename C, typename A
 
-template <BOOST_GRAPHS_VS_PARAMS>
+template <BOOST_GRAPH_VS_PARAMS>
 vertex_set_impl<V,C,A>::vertex_set_impl()
     : _verts()
 { }
 
-#undef BOOST_GRAPHS_VS_PARAMS
+/**
+ * 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(lg(V))
+ */
+template <BOOST_GRAPH_VS_PARAMS>
+typename vertex_set_impl<V,C,A>::vertex_descriptor
+vertex_set_impl<V,C,A>::add(vertex_properties const& vp)
+{
+    // Try to insert the vertex.
+    vertex_descriptor ret;
+    std::pair<iterator, bool> ins = _verts.insert(vertex_type(vp));
+    if(ins.second) {
+        vertex_type& v = const_cast<vertex_type&>(*(ins.first));
+        v.iter = ins.first;
+        ret = &v;
+    }
+    else {
+        ret = &const_cast<vertex_type&>(*ins.first);
+    }
+    return ret;
+}
+
+/**
+ * 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);
+}
+
+/**
+ * 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
 
@@ -176,19 +283,6 @@
 }
 
 /**
- * Remove a vertex from the store.
- *
- * @complexity O(log(V))
- */
-template <BOOST_GRAPH_VS_PARAMS>
-void
-vertex_set_impl<V,C,A>::remove_vertex(vertex_descriptor v)
-{
-    vertex_type* vp = static_cast<vertex_type*>(v.desc);
-    _verts.erase(vp->iter);
-}
-
-/**
  * Remove the vertex identified by the given properties from the store.
  *
  * @complexity O(log(V))
@@ -270,36 +364,6 @@
 }
 
 /**
- * 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.desc);
-}
-
-/**
- * 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.desc);
-}
-
-/**
- * Access 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);
-}
-
-/**
  * Access the properties of the given vertex.
  */
 template <BOOST_GRAPH_VS_PARAMS>
@@ -311,8 +375,4 @@
 
 #endif
 
-} /* namespace adj_list */
-} /* namesapce graphs */
-} /* namespace boost */
-
 #endif

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex_vector.hpp	2008-06-06 13:12:18 EDT (Fri, 06 Jun 2008)
@@ -4,15 +4,13 @@
 
 #include <vector>
 
-#include "indexed_vertex_iterator.hpp"
-
 // Forward declarations
 template <typename V, typename A> struct vertex_vector_impl;
 
 template <template <typename> class Allocator>
 struct basic_vertex_vector
 {
-    typedef void* key_type;
+    typedef none key_type;
     typedef std::size_t descriptor_type;
 
     template <typename Vertex>
@@ -46,8 +44,11 @@
     typedef Vertex vertex_type;
     typedef typename Vertex::vertex_properties vertex_properties;
     typedef typename vertex_store::size_type size_type;
-    typedef indexed_vertex_iterator<vertex_store> iterator;
-    typedef std::pair<iterator, iterator> range;
+    typedef typename vertex_store::iterator iterator;
+    typedef typename vertex_store::const_iterator const_iterator;
+
+    typedef indexed_vertex_iterator<vertex_store> vertex_iterator;
+    typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
 
     // Constructors
     vertex_vector_impl();
@@ -60,9 +61,9 @@
     size_type size() const;
 
     // Vertex iteration.
-    range vertices() const;
-    iterator begin() const;
-    iterator end() const;
+    vertex_range vertices() const;
+    vertex_iterator begin_vertices() const;
+    vertex_iterator end_vertices() const;
 
     // Vertex/vertex property accessors.
     vertex_type& vertex(vertex_descriptor v);
@@ -74,10 +75,10 @@
     vertex_store _verts;
 };
 
-#define BOOST_GRAPHS_VV_PARAMS \
+#define BOOST_GRAPH_VV_PARAMS \
     typename V, typename A
 
-template <BOOST_GRAPHS_VV_PARAMS>
+template <BOOST_GRAPH_VV_PARAMS>
 vertex_vector_impl<V,A>::vertex_vector_impl()
     : _verts()
 { }
@@ -89,7 +90,7 @@
  *
  * @complexity O(1) amortized
  */
-template <BOOST_GRAPHS_VV_PARAMS>
+template <BOOST_GRAPH_VV_PARAMS>
 typename vertex_vector_impl<V,A>::vertex_descriptor
 vertex_vector_impl<V,A>::add()
 {
@@ -102,7 +103,7 @@
  *
  * @complexity O(1) amortized
  */
-template <BOOST_GRAPHS_VV_PARAMS>
+template <BOOST_GRAPH_VV_PARAMS>
 typename vertex_vector_impl<V,A>::vertex_descriptor
 vertex_vector_impl<V,A>::add(vertex_properties const& vp)
 {
@@ -112,9 +113,39 @@
 }
 
 /**
+ * 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_GRAPHS_VV_PARAMS>
+template <BOOST_GRAPH_VV_PARAMS>
 typename vertex_vector_impl<V,A>::size_type
 vertex_vector_impl<V,A>::size() const
 {
@@ -124,7 +155,7 @@
 /**
  * Get access to the underlying vertex.
  */
-template <BOOST_GRAPHS_VV_PARAMS>
+template <BOOST_GRAPH_VV_PARAMS>
 typename vertex_vector_impl<V,A>::vertex_type&
 vertex_vector_impl<V,A>::vertex(vertex_descriptor v)
 {
@@ -134,14 +165,24 @@
 /**
  * Get access to the underlying vertex.
  */
-template <BOOST_GRAPHS_VV_PARAMS>
+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];
 }
 
-#undef BOOST_GRAPHS_VV_PARAMS
+/**
+ * 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
 
@@ -195,16 +236,6 @@
  * Get access to the properties of the given vertex.
  */
 template <typename V, template <typename> class A>
-typename vertex_vector_impl<V,A>::vertex_properties&
-vertex_vector_impl<V,A>::properties(vertex_descriptor v)
-{
-    return *vertex(v);
-}
-
-/**
- * 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
 {