[Boost-commit] svn:boost r46646 - in sandbox/SOC/2008/graphs/trunk: boost/graphs libs/graphs

From: asutton_at_[hidden]
Date: 2008-06-24 11:10:10

Author: asutton
Date: 2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
New Revision: 46646
URL: http://svn.boost.org/trac/boost/changeset/46646

Log:
Cleaned up more code. Got the impl of remove edges the way I wanted it to work
for both directed/undirected.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp     |    10 +                                       
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp    |    38 +++++--                                 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp   |    48 +++-----                                
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp       |     9                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp           |     4                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp    |   205 +++++++++++---------------------------- 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp     |   194 ++++++++++---------------------------   
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp  |    52 +++------                               
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp      |     7                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp  |    54 ++++------                              
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp |    44 +++-----                                
   sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp                 |     1                                         
   12 files changed, 230 insertions(+), 436 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -13,11 +13,12 @@
  * @param VertexDesc A vertex descriptor
  * @param OutDesc An out edge descriptor.
  */
-template <typename OutIter>
+template <typename OutIter, typename InIter>
 class directed_edge
 {
 public:
     typedef OutIter out_iterator;
+    typedef InIter in_iterator;
     typedef typename OutIter::value_type out_tuple;
     typedef typename boost::tuples::element<0, out_tuple>::type vertex_descriptor;
     typedef typename boost::tuples::element<1, out_tuple>::type edge_properties;
@@ -47,6 +48,9 @@
     inline OutIter out_edge() const
     { return _out; }
 
+    inline InIter in_edge() const
+    { return _out->template get<2>().template get<InIter>(); }
+
     /** @name Property Accessors
      * Return the properties associated with the edge.
      */
@@ -77,8 +81,8 @@
     OutIter             _out;
 };
 
-template <typename OI>
-std::ostream& operator<<(std::ostream& os, const directed_edge<OI>& e)
+template <typename O, typename I>
+std::ostream& operator<<(std::ostream& os, const directed_edge<O,I>& e)
 { return os << "(" << e.source() << " " << e.target() << ")"; }
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -75,10 +75,8 @@
     typedef typename EdgeStore::template out_store<vertex_descriptor, edge_properties>::type out_edge_store;
     typedef typename EdgeStore::template in_store<vertex_descriptor>::type in_edge_store;
 
-    // We can now generate the edge descriptor. The type of this can be entirely
-    // distilled from the iterator into the out edge set - it has it all. Note
-    // that this includes a placeholder for the in edge too.
-    typedef directed_edge<typename out_edge_store::iterator> edge_descriptor;
+    // We can now generate the edge descriptor.
+    typedef directed_edge<typename out_edge_store::iterator, typename in_edge_store::iterator> edge_descriptor;
 
     // Generate the vertex type over the vertex properties, and in/out stores.
     // We can also pull size
@@ -96,10 +94,12 @@
     typedef typename vertex_store::vertex_iterator vertex_iterator;
     typedef typename vertex_store::vertex_range vertex_range;
 
-    // Additional iterator types.
-    typedef basic_out_iterator<typename vertex_type::out_iterator> out_edge_iterator;
+    // Additional iterator types. I'm cheating here and using the edge
+    // descriptor to piggyback type information to these iterators. It kinda
+    // works.
+    typedef basic_out_iterator<edge_descriptor> out_edge_iterator;
     typedef std::pair<out_edge_iterator, out_edge_iterator> out_edge_range;
-    typedef basic_in_iterator<typename vertex_type::in_iterator, typename vertex_type::out_iterator> in_edge_iterator;
+    typedef basic_in_iterator<edge_descriptor> in_edge_iterator;
     typedef std::pair<in_edge_iterator, in_edge_iterator> in_edge_range;
 
     // This just makes sense.
@@ -641,9 +641,25 @@
 void
 directed_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor u, vertex_descriptor v)
 {
-    // Iterate over the out edges of u and, for each target v, remove the in
-    // edge (v, u) and the out edge (u, v).
-    _edges -= _verts.vertex(u).disconnect(_verts.vertex(v), v);
+    vertex_type& src = _verts.vertex(u);
+    vertex_type& tgt = _verts.vertex(v);
+
+    // Iterate over the out edges of the source, removing them.
+    out_edge_range rng = out_edges(u);
+    for(out_edge_iterator i = rng.first ; i != rng.second; ) {
+        // If the target vertex is one that we want to remove, remove it from
+        // the out list of this vertex. Also, brute-force remove it from the
+        // in list of other vertex.
+        edge_descriptor e = *i;
+        if(v == e.target()) {
+            tgt.disconnect_source(e.in_edge());
+            i = out_edge_iterator(u, src.disconnect_target(e.out_edge()));
+            --_edges;
+       }
+       else {
+            ++i;
+       }
+    }
 }
 
 template <BOOST_GRAPH_DG_PARAMS>
@@ -811,7 +827,7 @@
 }
 
 /**
- * Return awn iterator range over the in edges of the given vertex.
+ * Return an iterator range over the in edges of the given vertex.
  */
 template <BOOST_GRAPH_DG_PARAMS>
 typename directed_graph<VP,EP,VS,ES>::in_edge_range

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -28,7 +28,7 @@
 
     typedef out_size_type incident_size_type;
 
-    typedef directed_edge<out_iterator> edge_descriptor;
+    typedef directed_edge<out_iterator, in_iterator> edge_descriptor;
 
     /** @name Constructors */
     //@{
@@ -51,10 +51,12 @@
     in_iterator connect_source(vertex_descriptor);
     static edge_descriptor bind_connection(out_iterator, in_iterator);
 
-    out_size_type disconnect(directed_vertex&, vertex_descriptor);
     void disconnect_target(edge_descriptor);
     void disconnect_source(edge_descriptor);
 
+    out_iterator disconnect_target(out_iterator);
+    in_iterator disconnect_source(in_iterator);
+
     /** @name Property Accessors */
     //@{
     inline vertex_properties& properties()
@@ -180,34 +182,6 @@
 }
 
 /**
- * Disconnect all edges that connect this vertex to the target, returning the
- * number of edges actually removed.
- */
-template <typename V, typename O, typename I>
-typename directed_vertex<V,O,I>::out_size_type
-directed_vertex<V,O,I>::disconnect(directed_vertex& vert, vertex_descriptor d)
-{
-    out_size_type ret = 0;
-    out_iterator i = _out.begin(), end = _out.end();
-    for( ; i != end; ) {
-        vertex_descriptor t = i->template get<0>();
-
-        // If the target vertex is one that we want to remove, remove it from
-        // the out list of this vertex. Also, brute-force remove it from the
-        // in list of other vertex.
-        if(t == d) {
-            vert._in.remove(i->template get<2>().template get<in_iterator>());
-            i = _out.remove(i);
-            ++ret;
-       }
-       else {
-            ++i;
-       }
-    }
-    return ret;
-}
-
-/**
  * Disconnect this vertex from its target, removing the outgoing edge.
  */
 template <typename V, typename O, typename I>
@@ -230,4 +204,18 @@
     _in.remove(i);
 }
 
+template <typename V, typename O, typename I>
+typename directed_vertex<V,O,I>::out_iterator
+directed_vertex<V,O,I>::disconnect_target(out_iterator i)
+{
+    return _out.remove(i);
+}
+
+template <typename V, typename O, typename I>
+typename directed_vertex<V,O,I>::in_iterator
+directed_vertex<V,O,I>::disconnect_source(in_iterator i)
+{
+    return _in.remove(i);
+}
+
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -9,11 +9,11 @@
  * of the out edge iterator since in edges contain placeheld references to
  * out edges.
  */
-template <typename InIter, typename OutIter>
+template <typename Edge>
 class basic_in_iterator
 {
-    typedef InIter base_iterator;
-    typedef OutIter out_iterator;
+    typedef typename Edge::in_iterator base_iterator;
+    typedef typename Edge::out_iterator out_iterator;
     typedef typename out_iterator::value_type out_tuple;
 public:
     typedef typename boost::tuples::element<0, out_tuple>::type vertex_descriptor;
@@ -23,8 +23,9 @@
     // Clearly, we're going to be constraining members using some concept stuff
     // when it becomes available.
     typedef typename base_iterator::iterator_category iterator_category;
+    typedef typename base_iterator::difference_type difference_type;
 
-    typedef directed_edge<out_iterator> value_type;
+    typedef Edge value_type;
     typedef value_type reference;
     typedef value_type pointer;
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -44,10 +44,10 @@
      * Remove the edge referenced by the given iterator.
      * @complexity O(1)
      */
-    void remove(iterator i)
+    iterator remove(iterator i)
     {
         --_size;
-        _edges.erase(i);
+        return _edges.erase(i);
     }
 
     /**

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -23,167 +23,76 @@
     typedef typename IncEdge::second_type property_descriptor;
 
     typedef typename store_type::iterator iterator;
-    typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
     // Constructors
-    incidence_list();
-
-    inline void add(incidence_pair);
+    incidence_list()
+        : _edges()
+        , _size(0)
+    { }
+
+    /**
+     * Incidence lists always allow the addition of edges, assuming that no policy
+     * conflicts exist. The first element of the return is the end() of the list.
+     * @complexity O(1)
+     */
+    inline std::pair<iterator, bool> allow(vertex_descriptor) const
+    { return make_pair(_edges.end(), true); }
+
+    /**
+     * Add a vertex to the list.
+     * @complexity O(1)
+     */
+    inline void add(incidence_pair p)
+    {
+        ++_size;
+        _edges.push_back(p);
+    }
 
-    inline std::pair<const_iterator, bool> allow(vertex_descriptor) const;
-    inline iterator find(incidence_pair);
-    inline const_iterator find(incidence_pair) const;
+    /**
+     * Find the given incidence pair in the vertex.
+     * @todo Do we need this function?
+     * @complexity O(1)
+     */
+    inline iterator find(incidence_pair p) const
+    { return std::find(_edges.begin(), _edges.end(), p); }
+
+    /**
+     * Remove the given incidence pair in this vertex.
+     * @complexity O(deg(v))
+     */
+    inline void remove(incidence_pair p)
+    { remove(find(p)); }
+
+    /**
+     * Remove the iterator.
+     * @complexity O(1)
+     */
+    inline iterator remove(iterator i)
+    {
+        --_size;
+        return _edges.erase(i);
+    }
 
-    inline void clear();
-    inline void remove(incidence_pair);
-    template <typename Eraser> inline void remove(vertex_descriptor, Eraser);
+    /** Remove all edges from the vertex. */
+    inline void clear()
+    {
+        _size = 0;
+        _edges.clear();
+    }
 
     inline size_type size() const
-    { return _edges.size(); }
+    { return _size; }
 
-    inline const_iterator begin() const
+    inline iterator begin() const
     { return _edges.begin(); }
 
-    inline const_iterator end() const
+    inline iterator end() const
     { return _edges.end(); }
 
 private:
-    store_type _edges;
+    mutable store_type  _edges;
+    size_type           _size;
 };
 
-#define BOOST_GRAPH_IL_PARAMS \
-    typename E, typename A
-
-template <BOOST_GRAPH_IL_PARAMS>
-incidence_list<E,A>::incidence_list()
-    : _edges()
-{ }
-
-/**
- * Incidence lists always allow the addition of edges, assuming that no policy
- * conflicts exist. The first element of the return is the end() of the list.
- *
- * @complexity O(1)
- */
-template <BOOST_GRAPH_IL_PARAMS>
-std::pair<typename incidence_list<E,A>::const_iterator, bool>
-incidence_list<E,A>::allow(vertex_descriptor v) const
-{
-    // Since there's no policy, there we must be able to add the edge.
-    return make_pair(_edges.end(), true);
-}
-
-/**
- * Add the incident edge to the incidence set.
- *
- * @complexity O(1)
- */
-template <BOOST_GRAPH_IL_PARAMS>
-void
-incidence_list<E,A>::add(incidence_pair p)
-{
-    _edges.push_back(p);
-}
-
-/**
- * Remove all incident edges from this set.
- *
- * @complexity  O(d)
- */
-template <typename E, typename A>
-void
-incidence_list<E,A>::clear()
-{
-    _edges.clear();
-}
-
-/**
- * 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_GRAPH_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_GRAPH_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) {
-            erase(i->second);
-            i = _edges.erase(i);
-        }
-        else {
-            ++i;
-        }
-    }
-}
-
-#if 0
-
-// Functions
-
-template <typename E>
-vertex_edge_list<E>::vertex_edge_list()
-    : base_type()
-{ }
-
-template <typename E>
-void
-vertex_edge_list<E>::add(edge_descriptor e)
-{
-    this->_store.push_back(e);
-}
-
-template <typename E>
-typename vertex_edge_list<E>::iterator
-vertex_edge_list<E>::find(edge_descriptor e)
-{
-    return std::find(this->_store.begin(), this->_store.end(), e);
-}
-
-template <typename E>
-typename vertex_edge_list<E>::const_iterator
-vertex_edge_list<E>::find(edge_descriptor e) const
-{
-    return std::find(this->_store.begin(), this->_store.end(), e);
-}
-
-template <typename E>
-void
-vertex_edge_list<E>::clear()
-{
-    this->_store.clear();
-}
-
-template <typename E>
-typename vertex_edge_list<E>::size_type
-vertex_edge_list<E>::size() const
-{
-    return this->_store.size();
-}
-
-#endif
-
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -4,6 +4,8 @@
 
 #include <map>
 
+#include <boost/next_prior.hpp>
+
 /**
  * The incidence vector stores incident "edges" of a vertex. In actuality,
  * this stores pairs containing an adjacent vertex descriptor and a property
@@ -27,161 +29,71 @@
     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;
 
     // Constructors
-    incidence_set();
-
-    // Add an incident edge.
-    inline void add(incidence_pair);
-
-    // Allow a connection to the edge?
-    inline std::pair<const_iterator, bool> allow(vertex_descriptor) const;
-
-    // Find the edge record in question.
-    inline iterator find(incidence_pair);
-    inline const_iterator find(incidence_pair) const;
+    inline incidence_set()
+        : _edges()
+    { }
+
+    /**
+     * Deteremine whether or not the edge exists or is even allowed to be added.
+     * This returns a pair containing an iterator indicating the position of the
+     * edge if it already exists and a bool value indicating whether or not the
+     * addition would even be allowed by policy.
+     * @complexity O(lg(deg(v)))
+     */
+    inline std::pair<iterator, bool> allow(vertex_descriptor v) const
+    { return make_pair(_edges.find(v), true); }
+
+    /**
+     * Add the incidence pair to the vertex.
+     * @complexity O(lg(deg(v)))
+     */
+    inline void add(incidence_pair p)
+    { _edges.insert(p); }
+
+    /**
+     * Find the incidence pair.
+     * @complexity O(lg(deg(v)))
+     */
+    inline iterator find(incidence_pair p) const
+    { return _edges.find(p.first); }
+
+    /**
+     * Remove the incidence pair from the set.
+     * @complexity O(lg(deg(v)))
+     */
+    inline void remove(incidence_pair p)
+    { _edges.erase(find(p)); }
+
+    /**
+     * Remove the iterator to the given incidence pair, returning an iterator
+     * to the next object in the sequence.
+     * @complexity O(lg(deg(v)))
+     */
+    inline iterator remove(iterator x)
+    {
+        iterator ret = boost::next(x);
+        _edges.erase(x);
+        return ret;
+    }
 
     // Remove edges.
-    inline void clear();
-    inline void remove(incidence_pair);
-    template <typename Eraser> inline void remove(vertex_descriptor, Eraser);
-
+    inline void clear()
+    { _edges.clear(); }
 
     inline size_type size() const
     { return _edges.size(); }
 
-    inline const_iterator begin() const
+    inline iterator begin() const
     { return _edges.begin(); }
 
-    inline const_iterator end() const
+    inline iterator end() const
     { return _edges.end(); }
 
 private:
-    store_type _edges;
+    mutable store_type _edges;
 };
 
-// Functions
-
-#define BOOST_GRAPH_IS_PARAMS \
-    typename E, typename C, typename A
-
-template <BOOST_GRAPH_IS_PARAMS>
-incidence_set<E,C,A>::incidence_set()
-    : _edges()
-{ }
-
-/**
- * Deteremine whether or not the edge exists or is even allowed to be added.
- * This returns a pair containing an iterator indicating the position of the
- * edge if it already exists and a bool value indicating whether or not the
- * addition would even be allowed by policy.
- *
- * @complexity O(lg(d))
- */
-template <BOOST_GRAPH_IS_PARAMS>
-std::pair<typename incidence_set<E,C,A>::const_iterator, bool>
-incidence_set<E,C,A>::allow(vertex_descriptor v) const
-{
-    // For now, always assume that the edge is allowed by policy, and determine
-    // "addability" based on whehter or not the edge exists.
-    return make_pair(_edges.find(v), true);
-}
-
-
-/**
- * Add the incidence pair to the set.
- *
- * @complexity O(lg(d))
- */
-template <BOOST_GRAPH_IS_PARAMS>
-void
-incidence_set<E,C,A>::add(incidence_pair p)
-{
-    _edges.insert(p);
-}
-
-/**
- * Remove all incident edges from this edge set.
- */
-template <typename E, typename C, typename A>
-void
-incidence_set<E,C,A>::clear()
-{
-    _edges.clear();
-}
-
-/**
- * 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);
-}
-
-#undef BOOST_GRAPH_IS_PARAMS
-
-#if 0
-
-template <typename E>
-void
-incidence_set<E>::add(edge_descriptor e)
-{
-    this->_store.insert(e);
-}
-
-template <typename E>
-typename incidence_set<E>::iterator
-incidence_set<E>::find(edge_descriptor e)
-{
-    return this->_store.find(e);
-}
-
-template <typename E>
-typename incidence_set<E>::const_iterator
-incidence_set<E>::find(edge_descriptor e) const
-{
-    return this->_store.find(e);
-}
-
-template <typename E>
-void
-incidence_set<E>::clear()
-{
-    this->_store.clear();
-}
-
-template <typename E>
-typename incidence_set<E>::size_type
-incidence_set<E>::size() const
-{
-    return this->_store.size();
-}
-
-#endif
-
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -23,7 +23,6 @@
     typedef typename Edge::second_type property_descriptor;
 
     typedef typename store_type::iterator iterator;
-    typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
     // Constructors
@@ -31,48 +30,33 @@
         : _edges()
     { }
 
-    std::pair<const_iterator, bool> allow(vertex_descriptor) const;
-
-    void add(incidence_pair);
-    iterator find(incidence_pair);
-    const_iterator find(incidence_pair) const;
+    /**
+     * Incidence vectors always allow the addition of edges, assuming that no
+     * policy conflicts exist. The first element of the return is the end() of
+     * the vector.
+     * @complexity O(1)
+     */
+    std::pair<iterator, bool> allow(vertex_descriptor) const
+    { return make_pair(_edges.end(), true); }
+
+    /** Add the incidence pair to the vector. */
+    void add(incidence_pair p)
+    { _edges.push_back(p); }
 
     inline size_type size() const
     { return _edges.size(); }
 
-    inline const_iterator begin() const
+    /** @name Iterators */
+    //@{
+    inline iterator begin() const
     { return _edges.begin(); }
 
-    inline const_iterator end() const
+    inline iterator end() const
     { return _edges.end(); }
+    //@}
 
 private:
-    store_type _edges;
+    mutable store_type _edges;
 };
 
-/**
- * Incidence vectors always allow the addition of edges, assuming that no
- * policy conflicts exist. The first element of the return is the end() of the
- * vector.
- *
- * @complexity O(1)
- */
-template <typename E, typename A>
-std::pair<typename incidence_vector<E,A>::const_iterator, bool>
-incidence_vector<E,A>::allow(vertex_descriptor v) const
-{
-    // Since there's no policy, there we must be able to add the edge.
-    return make_pair(_edges.end(), true);
-}
-
-/**
- * Add the incidence pair to the vector.
- */
-template <typename E, typename A>
-void
-incidence_vector<E,A>::add(incidence_pair e)
-{
-    _edges.push_back(e);
-}
-
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -7,10 +7,10 @@
  * dereferenced will return an edge descriptor. The properties of the iterator
  * are taken from the underlying store.
  */
-template <typename Iter>
+template <typename Edge>
 class basic_out_iterator
 {
-    typedef Iter base_iterator;
+    typedef typename Edge::out_iterator base_iterator;
 public:
     typedef typename base_iterator::value_type out_tuple;
     typedef typename boost::tuples::element<0, out_tuple>::type vertex_descriptor;
@@ -20,8 +20,9 @@
     // Clearly, we're going to be constraining members using some concept stuff
     // when it becomes available.
     typedef typename base_iterator::iterator_category iterator_category;
+    typedef typename base_iterator::difference_type difference_type;
 
-    typedef directed_edge<base_iterator> value_type;
+    typedef Edge value_type;
     typedef value_type reference;
     typedef value_type pointer;
 

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-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -364,8 +364,6 @@
                                         vertex_descriptor v,
                                         edge_properties const& ep)
 {
-    typedef typename incidence_store::const_iterator inc_iterator;
-
     // To add the edge or not... We need to consult the virtual edge set
     // to determine whether or not this edge already exists. For multigraph
     // stores, this should always return false. The protocol is: ask the source
@@ -375,7 +373,7 @@
     vertex_type& src = _verts.vertex(u);
     vertex_type& tgt = _verts.vertex(v);
 
-    std::pair<inc_iterator, bool> ins = src.allow(v);
+    std::pair<typename vertex_type::iterator, bool> ins = src.allow(v);
     if(ins.second) {
         // If the returned iterator is past the end, then we need to add this
         // edge. Otherwise, we can simply return an edge over the existing
@@ -467,11 +465,10 @@
     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);
+    // Disconnect the incidence ends and then remove the property from the
+    // global property store.
     tgt.disconnect(u, p);
-
+    src.disconnect(v, p);
     _props.remove(p);
 }
 
@@ -536,34 +533,27 @@
 undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor u,
                                             vertex_descriptor v)
 {
-    std::vector<property_descriptor> del;
-
-    // First pass: Find all edges connecting u and v, remove the global property
-    // record and cache the descriptor for later.
-    incident_edge_range rng = incident_edges(v);
-    for(incident_edge_iterator i = rng.first; i != rng.second; ++i) {
-        edge_descriptor e = *i;
+    // Canonicalize the ordering of vertices first and the get the vertices.
+    reorder(u, v);
+    vertex_type& src = _verts.vertex(u);
+    vertex_type& tgt = _verts.vertex(v);
 
-        // If the edge connects these two vertices, remove the edge property.
-        if(e.connects(u, v)) {
-            property_descriptor p = e.properties();
-            del.push_back(p);
+    // Iterate over the incident edges of the source vertex.
+    typename vertex_type::iterator i = src.begin(), end = src.end();
+    for( ; i != end; ) {
+        vertex_descriptor o = i->first;
+        property_descriptor p = i->second;
+        // If this is the opposite end of the edge, then we need to remove this
+        // from a) the incidence store of the opposite vertex and b) the global
+        // edge property.
+        if(i->first == v) {
+            tgt.disconnect(u, p);
             _props.remove(p);
+            i = src.disconnect(i);
+        }
+        else {
+            ++i;
         }
-    }
-
-    // Second pass: Remove the local endpoints of each edge with the given
-    // properties. The propdescs might be invalid, but they aren't being used
-    // to reference actual properties here.
-    // TODO: This isn't particularly efficient since each disconnect() is a
-    // local search on the vertex of O(deg(x)).
-    vertex_type& src = _verts.vertex(u);
-    vertex_type& tgt = _verts.vertex(v);
-    typename std::vector<property_descriptor>::iterator i = del.begin(), end = del.end();
-    for( ; i != end; ++i) {
-        property_descriptor p = *i;
-        src.disconnect(v, p);
-        tgt.disconnect(u, p);
     }
 }
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -28,7 +28,7 @@
     typedef typename incidence_store::vertex_descriptor vertex_descriptor;
     typedef typename incidence_store::property_descriptor property_descriptor;
 
-    typedef typename incidence_store::const_iterator iterator;
+    typedef typename incidence_store::iterator iterator;
     typedef typename incidence_store::size_type size_type;
 
     inline undirected_vertex();
@@ -42,17 +42,26 @@
     inline std::pair<iterator, bool> allow(vertex_descriptor) const;
     inline void connect(vertex_descriptor, property_descriptor);
     inline void disconnect(vertex_descriptor, property_descriptor);
-    template <typename Eraser> inline void disconnect(vertex_descriptor, Eraser);
+    inline iterator disconnect(iterator);
 
-    inline vertex_properties& properties();
-    inline vertex_properties const& properties() const;
 
+    /** @name Property Accessors */
+    //@{
+    inline vertex_properties& properties()
+    { return _props; }
 
+    inline vertex_properties const& properties() const
+    { return _props; }
+    //@}
+
+    /** @name Iterators */
+    //@{
     inline iterator begin() const
     { return _edges.begin(); }
 
     inline iterator end() const
     { return _edges.end(); }
+    //@}
 
     inline void clear()
     { _edges.clear(); }
@@ -122,31 +131,10 @@
 }
 
 template <typename VP, typename IS>
-template <typename Eraser>
-void
-undirected_vertex<VP,IS>::disconnect(vertex_descriptor v, Eraser erase)
-{
-    _edges.remove(v, erase);
-}
-
-/**
- * Return the properties associated with this vertex (if any).
- */
-template <typename VP, typename IS>
-typename undirected_vertex<VP,IS>::vertex_properties&
-undirected_vertex<VP,IS>::properties()
-{
-    return _props;
-}
-
-/**
- * Return the properties associated with this vertex (if any).
- */
-template <typename VP, typename IS>
-typename undirected_vertex<VP,IS>::vertex_properties const&
-undirected_vertex<VP,IS>::properties() const
+typename undirected_vertex<VP,IS>::iterator
+undirected_vertex<VP,IS>::disconnect(iterator i)
 {
-    return _props;
+    return _edges.remove(i);
 }
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp	2008-06-24 11:10:08 EDT (Tue, 24 Jun 2008)
@@ -87,6 +87,7 @@
     BOOST_ASSERT(g.num_edges() == 3);
 
     g.remove_edge(E.front());
+    BOOST_ASSERT(g.num_edges() == 2);
     BOOST_ASSERT(g.degree(V[1]) == 1);
     E.pop_front();