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