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);