Boost logo

Boost-Commit :

From: asutton_at_[hidden]
Date: 2008-06-24 09:41:03


Author: asutton
Date: 2008-06-24 09:41:02 EDT (Tue, 24 Jun 2008)
New Revision: 46641
URL: http://svn.boost.org/trac/boost/changeset/46641

Log:
Added some missing files for in/out edge iteration.
Renamed all the disconnect methods to remove_edges(). Tried to optimize
some of them - may have worked, but undirected graphs is still pretty
bad.

Added:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp (contents, props changed)
Text files modified:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 47 ++++----
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp | 31 +++++
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp | 5
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp | 8
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp | 13 ++
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 219 +++++++++++++++++++++++----------------
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp | 15 --
   sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp | 12 ++
   sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp | 6 +
   sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp | 2
   10 files changed, 225 insertions(+), 133 deletions(-)

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 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -139,21 +139,14 @@
     //@{
     vertex_descriptor find_vertex(vertex_properties const&) const;
     vertex_descriptor find_vertex(vertex_key const&) const;
- //@{
+ //@}
 
- /** @name Disconnect Vertex
- * Disconnect a vertex from the graph by removing all of its incident edges.
- * These functions only exist for graphs with ReducibleEdgeSets. Functions
- * that take properties or keys are provided for convenience, but have
- * additional dependencies and cost. These additonal functions are
- * equivalent to disconnect_vertex(find_vertex(x)) where x is either a
- * vertex_properties or vertex_key.
- *
- * ReducibleEdgeSet disconnect_vertex(vertex_descriptor)
- * LabeledUniqueVertices disconnect_vertex(vertex_properties)
- * MappedUniqueVertices disconnect_vertex(vertex_key)
+ /** @name Vertex Key
+ * Return the key for the given vertex. This is only provided for graphs
+ * with MappedVertices (can be multimapped).
      */
     //@{
+ vertex_key const& key(vertex_descriptor) const;
     //@}
 
     /** @name Remove Vertex
@@ -173,14 +166,6 @@
     void remove_vertex(vertex_key const&);
     //@}
 
- /** @name Vertex Key
- * Return the key for the given vertex. This is only provided for graphs
- * with MappedVertices (can be multimapped).
- */
- //@{
- vertex_key const& key(vertex_descriptor) const;
- //@}
-
     /** @name Add Edge
      * Add an edge, connecting two vertices, to the graph. There are a number of
      * variations of this function, depending on the type of vertex store and
@@ -245,7 +230,6 @@
     void remove_edges(vertex_descriptor, vertex_descriptor);
     void remove_edges(vertex_properties const&, vertex_properties const&);
     void remove_edges(vertex_key const&, vertex_key const&);
-
     //@}
 
     /** @name Size and Degree
@@ -258,7 +242,6 @@
     in_edges_size_type in_degree(vertex_descriptor v) const;
     incident_edges_size_type degree(vertex_descriptor v) const;
     //@}
- //
 
     /** @name Out Edge Iterator */
     //@{
@@ -658,8 +641,28 @@
 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);
+}
+
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_edges(vertex_properties const& u,
+ vertex_properties const& v)
+{
+ remove_vertices(find_vertex(u), find_vertex(v));
 }
 
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_edges(vertex_key const& u,
+ vertex_key const& v)
+{
+ remove_vertices(find_vertex(u), find_vertex(v));
+}
+
+
 /**
  * Test to see if the given edge exists. Return a pair containing the edge
  * descriptor (if it exists), and a boolean value indicating whether it actually

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 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -51,6 +51,7 @@
     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);
 
@@ -173,12 +174,40 @@
 typename directed_vertex<V,O,I>::edge_descriptor
 directed_vertex<V,O,I>::bind_connection(out_iterator i, in_iterator j)
 {
- boost::get<2>(*i).put(j);
+ i->template get<2>().put(j);
     j->second.put(i);
     return edge_descriptor(j->first, i);
 }
 
 /**
+ * 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>

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp 2008-06-24 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -0,0 +1,82 @@
+
+#ifndef IN_ITERATOR_HPP
+#define IN_ITERATOR_HPP
+
+/**
+ * The in edge iterator is a wrapper around out store iterators that, when
+ * dereferenced will return an edge descriptor. The iterator category is taken
+ * from the base iterator. The in edge iterator also needs to know the type
+ * of the out edge iterator since in edges contain placeheld references to
+ * out edges.
+ */
+template <typename InIter, typename OutIter>
+class basic_in_iterator
+{
+ typedef InIter base_iterator;
+ typedef OutIter out_iterator;
+ typedef typename out_iterator::value_type out_tuple;
+public:
+ typedef typename boost::tuples::element<0, out_tuple>::type vertex_descriptor;
+ typedef typename boost::tuples::element<1, out_tuple>::type edge_properties;
+
+ // This is a little misleading. This iterator can be either bidi or random.
+ // 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 directed_edge<out_iterator> value_type;
+ typedef value_type reference;
+ typedef value_type pointer;
+
+ inline basic_in_iterator()
+ : _base(), _iter()
+ { }
+
+ inline basic_in_iterator(basic_in_iterator const& x)
+ : _base(x._base), _iter(x._iter)
+ { }
+
+ inline basic_in_iterator(vertex_descriptor v, base_iterator const& x)
+ : _base(v), _iter(x)
+ { }
+
+ /**
+ * Extended iterator functionality. Return the source vertex of the
+ * iterator. This is the vertex for which the iterator was originally
+ * created.
+ */
+ vertex_descriptor source() const
+ { return _base; }
+
+ /**
+ * Extended iterator functionality. Return the opposite vertex of the
+ * edge indicated by the iterator. This is mostly provided for use by
+ * the adjacency iterator.
+ */
+ vertex_descriptor opposite() const
+ { return _iter->first; }
+
+ inline basic_in_iterator& operator++()
+ { ++_iter; return *this; }
+
+ inline basic_in_iterator& operator--()
+ { --_iter; return *this; }
+
+ // Iterators are equivalent if they reference the same edge.
+ inline bool operator==(basic_in_iterator const& x) const
+ { return **this == *x; }
+
+ inline bool operator!=(basic_in_iterator const& x) const
+ { return !this->operator==(x); }
+
+ inline reference operator*() const
+ {
+ return reference(_iter->first, _iter->second.template get<out_iterator>());
+ }
+
+private:
+ vertex_descriptor _base;
+ base_iterator _iter;
+};
+
+#endif

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 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -40,7 +40,10 @@
         return boost::prior(_edges.end());
     }
 
- /** Remove the edge referenced by the given iterator. */
+ /**
+ * Remove the edge referenced by the given iterator.
+ * @complexity O(1)
+ */
     void remove(iterator i)
     {
         --_size;

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp 2008-06-24 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -0,0 +1,77 @@
+
+#ifndef OUT_ITERATOR_HPP
+#define OUT_ITERATOR_HPP
+
+/**
+ * The out edge iterator is a wrapper around out store iterators that, when
+ * dereferenced will return an edge descriptor. The properties of the iterator
+ * are taken from the underlying store.
+ */
+template <typename Iter>
+class basic_out_iterator
+{
+ typedef Iter base_iterator;
+public:
+ typedef typename base_iterator::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;
+
+ // This is a little misleading. This iterator can be either bidi or random.
+ // 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 directed_edge<base_iterator> value_type;
+ typedef value_type reference;
+ typedef value_type pointer;
+
+ inline basic_out_iterator()
+ : _base(), _iter()
+ { }
+
+ inline basic_out_iterator(basic_out_iterator const& x)
+ : _base(x._base), _iter(x._iter)
+ { }
+
+ inline basic_out_iterator(vertex_descriptor v, base_iterator const& x)
+ : _base(v), _iter(x)
+ { }
+
+ /**
+ * Extended iterator functionality. Return the source vertex of the
+ * iterator. This is the vertex for which the iterator was originally
+ * created.
+ */
+ vertex_descriptor source() const
+ { return _base; }
+
+ /**
+ * Extended iterator functionality. Return the opposite vertex of the
+ * edge indicated by the iterator. This is mostly provided for use by
+ * the adjacency iterator.
+ */
+ vertex_descriptor opposite() const
+ { return _iter->first; }
+
+ inline basic_out_iterator& operator++()
+ { ++_iter; return *this; }
+
+ inline basic_out_iterator& operator--()
+ { --_iter; return *this; }
+
+ // Iterators are equivalent if they reference the same edge.
+ inline bool operator==(basic_out_iterator const& x) const
+ { return **this == *x; }
+
+ inline bool operator!=(basic_out_iterator const& x) const
+ { return !this->operator==(x); }
+
+ inline reference operator*() const
+ { return reference(_base, _iter); }
+
+private:
+ vertex_descriptor _base;
+ base_iterator _iter;
+};
+
+#endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp 2008-06-24 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -49,15 +49,17 @@
     }
 
     /**
- * Remove the edge with the given vertex.
+ * Remove the edge with the given vertex. Return the next iterator in
+ * the sequence.
      * @complexity O(1)
      */
- void remove(iterator i)
+ iterator remove(iterator i)
     {
         --_size;
- _edges.erase(i);
+ return _edges.erase(i);
     }
 
+
     /** Find the edge with the given vertex. */
     iterator find(vertex_descriptor v) const
     {

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp 2008-06-24 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -2,6 +2,8 @@
 #ifndef UNDIRECTED_EDGE_HPP
 #define UNDIRECTED_EDGE_HPP
 
+#include <iosfwd>
+
 #include "unordered_pair.hpp"
 
 /**
@@ -33,6 +35,13 @@
     inline vertex_descriptor second() const
     { return _edge.second(); }
 
+ /** Return true if the edge connects the two vertices. */
+ inline bool connects(vertex_descriptor u, vertex_descriptor v) const
+ {
+ reorder(u, v);
+ return first() == u && second() == v;
+ }
+
     inline vertex_descriptor opposite(vertex_descriptor v)
     { return v == first() ? second() : first(); }
 
@@ -81,5 +90,9 @@
     return _edge < x._edge || (!(x._edge < _edge) && _prop < x._prop);
 }
 
+template <typename VD, typename PD>
+std::ostream& operator<<(std::ostream& os, undirected_edge<VD,PD> const& e)
+{ return os << "{" << e.first() << " " << e.second() << "}"; }
+
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp 2008-06-24 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -99,24 +99,14 @@
     //@{
     vertex_descriptor find_vertex(vertex_properties const&) const;
     vertex_descriptor find_vertex(vertex_key const&) const;
- //@{
+ //@}
 
- /** @name Disconnect Vertex
- * Disconnect a vertex from the graph by removing all of its incident edges.
- * These functions only exist for graphs with ReducibleEdgeSets. Functions
- * that take properties or keys are provided for convenience, but have
- * additional dependencies and cost. These additonal functions are
- * equivalent to disconnect_vertex(find_vertex(x)) where x is either a
- * vertex_properties or vertex_key.
- *
- * ReducibleEdgeSet disconnect_vertex(vertex_descriptor)
- * LabeledUniqueVertices disconnect_vertex(vertex_properties)
- * MappedUniqueVertices disconnect_vertex(vertex_key)
+ /** @name Vertex Key
+ * Return the key for the given vertex. This is only provided for graphs
+ * with MappedVertices (can be multimapped).
      */
     //@{
- void disconnect_vertex(vertex_descriptor);
- void disconnect_vertex(vertex_properties const&);
- void disconnect_vertex(vertex_key const&);
+ vertex_key const& key(vertex_descriptor) const;
     //@}
 
     /** @name Remove Vertex
@@ -136,14 +126,6 @@
     void remove_vertex(vertex_key const&);
     //@}
 
- /** @name Vertex Key
- * Return the key for the given vertex. This is only provided for graphs
- * with MappedVertices (can be multimapped).
- */
- //@{
- vertex_key const& key(vertex_descriptor) const;
- //@{
-
     /** @name Add Edge
      * Add an edge, connecting two vertices, to the graph. There are a number of
      * variations of this function, depending on the type of vertex store and
@@ -175,12 +157,22 @@
     //@}
 
     /** @name Remove Edge(s)
- * These functions operate on the edges of the graph. This functions
- * include the ability to add and remove edges.
+ * Remove one or more edges from the graph. The function taking a single
+ * edge descriptor removes exactly that edge. The fucntion(s) taking
+ * a single vertex descriptor remove all edges incident to that vertex. The
+ * function(s) taking two vertices remove all edges connecting the two
+ * vertices.
      */
     //@{
     void remove_edge(edge_descriptor);
+
+ void remove_edges(vertex_descriptor);
+ void remove_edges(vertex_properties const&);
+ void remove_edges(vertex_key const&);
+
     void remove_edges(vertex_descriptor, vertex_descriptor);
+ void remove_edges(vertex_properties const&, vertex_properties const&);
+ void remove_edges(vertex_key const&, vertex_key const&);
     //@}
 
     /** @name Vertex Iteration
@@ -216,7 +208,7 @@
     adjacent_vertex_range adjacent_vertices(vertex_descriptor) const;
 
     incident_edges_size_type degree(vertex_descriptor) const;
- //@{
+ //@}
 
     /** @name Property Accessors
      * Access the properties of the given vertex or edge.
@@ -224,7 +216,7 @@
     //@{
     vertex_properties& operator[](vertex_descriptor);
     edge_properties& operator[](edge_descriptor);
- //@{
+ //@}
 
 private:
     property_store _props;
@@ -306,57 +298,6 @@
 }
 
 /**
- * Disconnect the vertex from the graph. This removes all edges incident to
- * the vertex, but will not remove the vertex itself.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_descriptor v)
-{
- // Disconnecting a vertex is not quite so simple as clearing the incidence
- // set since we have to remove all the edge properties and remove the
- // opposite edges from other vertices.
- // TODO: Can we specialize this at all?
-
- // Start by disconnecting all of the incident edges from adjacent vertices.
- incident_edge_range rng = incident_edges(v);
- for( ; rng.first != rng.second; ++rng.first) {
- edge_descriptor e = *rng.first;
- vertex_type& opp = _verts.vertex(e.opposite(v));
- opp.disconnect(v, e.properties());
-
- // Remove all the properties too. Does this make sense here?
- _props.remove(e.properties());
- }
-
- // Clear the incident edge set of the vertex. We don't do this in the
- // previous loop because we'll probably end up invalidating our own
- // iterators.
- _verts.vertex(v).disconnect();
-}
-
-/**
- * Disconnect the vertex having the given properties from the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_properties const& vp)
-{
- BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
- disconnect_vertex(find_vertex(vp));
-}
-
-/**
- * Disconnect the vertex having the given key from the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_key const& k)
-{
- disconnect_vertex(find_vertex(k));
-}
-
-/**
  * Remove the vertex from the graph. This will disconnect the vertex from the
  * graph prior to remove.
  */
@@ -364,7 +305,7 @@
 void
 undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_descriptor v)
 {
- disconnect_vertex(v);
+ remove_edges(v);
     _verts.remove(v);
 }
 
@@ -376,7 +317,7 @@
 undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_properties const& vp)
 {
     BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
- disconnect_vertex(vp);
+ remove_edges(vp);
     _verts.remove(vp);
 }
 
@@ -387,7 +328,7 @@
 void
 undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_key const& k)
 {
- disconnect_vertex(k);
+ remove_edges(k);
     _verts.remove(k);
 }
 
@@ -535,27 +476,119 @@
 }
 
 /**
- * This removes all distinct edges connecting the vertices u and v.
+ * Remove all edges incident to the given vertex, effectively disconnecting
+ * it from the graph.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor v)
+{
+ // Disconnecting a vertex is not quite so simple as clearing the incidence
+ // set since we have to remove all the edge properties and remove the
+ // opposite edges from other vertices.
+ // TODO: Can we specialize this at all?
+
+ vertex_type& src = _verts.vertex(v);
+
+ // Start by disconnecting all of the incident edges from adjacent vertices.
+ incident_edge_range rng = incident_edges(v);
+ for( ; rng.first != rng.second; ++rng.first) {
+ edge_descriptor e = *rng.first;
+ vertex_type& opp = _verts.vertex(e.opposite(v));
+ opp.disconnect(v, e.properties());
+
+ // Remove all the properties too. Does this make sense here?
+ _props.remove(e.properties());
+ }
+
+ // Clear the incident edge set of the vertex. We don't do this in the
+ // previous loop because we'll probably end up invalidating our own
+ // iterators.
+ src.clear();
+}
+
+/**
+ * Disconnect the vertex having the given properties from the graph.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_properties const& vp)
+{
+ BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+ remove_edges(find_vertex(vp));
+}
+
+/**
+ * Disconnect the vertex having the given key from the graph.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_key const& k)
+{
+ remove_edges(find_vertex(k));
+}
+
+/**
+ * Remove all 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)
 {
+ 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;
+
+ // 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);
+ _props.remove(p);
+ }
+ }
+
+ // 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);
+ }
+}
+
+/**
+ * Remove all edges connecting the vertices identified by the given properties.
+ * This is equivalent to remove_edges(find_vertex(u), find_vertex(v)).
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_properties const& u,
+ vertex_properties const& v)
+{
+ return remove_edges(find_vertex(u), find_vertex(v));
+}
 
- // 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.
- //
- // 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, property_eraser<property_store>(_props));
- tgt.disconnect(u, noop_eraser());
+/**
+ * Remove all edges connecting the vertices identified by the given keys. This
+ * is equivalent to remove_edges(find_vertex(u), find_vertex(v)).
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_key const& u,
+ vertex_key const& v)
+{
+ return remove_edges(find_vertex(u), find_vertex(v));
 }
 
 /**

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 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -41,7 +41,6 @@
      */
     inline std::pair<iterator, bool> allow(vertex_descriptor) const;
     inline void connect(vertex_descriptor, property_descriptor);
- inline void disconnect();
     inline void disconnect(vertex_descriptor, property_descriptor);
     template <typename Eraser> inline void disconnect(vertex_descriptor, Eraser);
 
@@ -55,6 +54,9 @@
     inline iterator end() const
     { return _edges.end(); }
 
+ inline void clear()
+ { _edges.clear(); }
+
     inline size_type degree() const
     { return _edges.size(); }
 
@@ -110,17 +112,6 @@
 }
 
 /**
- * Disconect all edges from this vertex. This does not remove the connection
- * from adjacent vertices to this vertex.
- */
-template <typename VP, typename IS>
-void
-undirected_vertex<VP,IS>::disconnect()
-{
- _edges.clear();
-}
-
-/**
  * Disconnect the incidedent edge given by the vertex v with edge properties p.
  */
 template <typename VP, typename IS>

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp 2008-06-24 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -134,4 +134,16 @@
     return x;
 }
 
+/**
+ * A swap-like sort function that will "unorder" two objects.
+ */
+template <typename T>
+void
+reorder(T& a, T& b)
+{
+ unordered_pair<T> p(a, b);
+ a = p.first();
+ b = p.second();
+}
+
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp 2008-06-24 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -141,6 +141,12 @@
     BOOST_ASSERT(g.in_degree(V[0]) == 0);
     BOOST_ASSERT(g.in_degree(V[1]) == 0);
     BOOST_ASSERT(g.in_degree(V[2]) == 1);
+
+ // This isn't really part of this test. See the multi-edge removals.
+ g.remove_edges(V[1], V[2]);
+ BOOST_ASSERT(g.num_edges() == 0);
+ BOOST_ASSERT(g.out_degree(V[1]) == 0);
+ BOOST_ASSERT(g.in_degree(V[2]) == 0);
 }
 
 // This is a little different than above. We remove a vertex from the triangle,

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 09:41:02 EDT (Tue, 24 Jun 2008)
@@ -110,7 +110,7 @@
     BOOST_ASSERT(g.num_vertices() == 3);
     BOOST_ASSERT(g.num_edges() == 3);
 
- g.disconnect_vertex(V[1]);
+ g.remove_edges(V[1]);
     BOOST_ASSERT(g.num_vertices() == 3);
     BOOST_ASSERT(g.degree(V[1]) == 0);
     BOOST_ASSERT(g.degree(V[0]) == 1);


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk