|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-06-24 08:24:40
Author: asutton
Date: 2008-06-24 08:24:39 EDT (Tue, 24 Jun 2008)
New Revision: 46640
URL: http://svn.boost.org/trac/boost/changeset/46640
Log:
Fixed some bugs with the removal of edges in directed graphs. Started
renaming the "disconnect_vertex" interface to remove_edges(). Implemented
edge() tests for directed graphs.
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp | 17 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 348 +++++++++++++++++++++++++++++++++++----
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp | 26 ++
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp | 33 ++
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp | 49 ++---
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp | 6
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp | 1
sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp | 29 ++
8 files changed, 413 insertions(+), 96 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 08:24:39 EDT (Tue, 24 Jun 2008)
@@ -2,6 +2,8 @@
#ifndef DIRECTED_EDGE_HPP
#define DIRECTED_EDGE_HPP
+#include <iosfwd>
+
#include <boost/tuple/tuple.hpp>
/**
@@ -39,7 +41,7 @@
/** Return the target of the edge. */
inline vertex_descriptor target() const
- { return boost::get<0>(*_out); }
+ { return _out->template get<0>(); }
/** Return the iterator to the out edge. */
inline OutIter out_edge() const
@@ -50,16 +52,18 @@
*/
//@{
inline edge_properties& properties()
- { return boost::get<1>(*_out); }
+ { return _out->template get<1>(); }
inline edge_properties const& properties() const
- { return boost::get<1>(*_out); }
+ { return _out->template get<1>(); }
//@}
- /** @name Operators */
+ /** @name Operators
+ * @todo Consider externalizing these.
+ */
//@{
inline bool operator==(directed_edge const& x)
- { return _src == x._src && _out = x._out; }
+ { return _src == x._src && _out == x._out; }
inline bool operator!=(directed_edge const& x)
{ return !operator==(x); }
@@ -73,5 +77,8 @@
OutIter _out;
};
+template <typename OI>
+std::ostream& operator<<(std::ostream& os, const directed_edge<OI>& 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 08:24:39 EDT (Tue, 24 Jun 2008)
@@ -43,6 +43,9 @@
#include "edge_list.hpp"
#include "edge_set.hpp"
+#include "out_iterator.hpp"
+#include "in_iterator.hpp"
+
#include "adjacency_iterator.hpp"
template <
@@ -93,6 +96,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;
+ 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 std::pair<in_edge_iterator, in_edge_iterator> in_edge_range;
+
// This just makes sense.
typedef std::size_t edges_size_type;
@@ -145,9 +154,6 @@
* MappedUniqueVertices disconnect_vertex(vertex_key)
*/
//@{
- void disconnect_vertex(vertex_descriptor);
- void disconnect_vertex(vertex_properties const&);
- void disconnect_vertex(vertex_key const&);
//@}
/** @name Remove Vertex
@@ -203,11 +209,43 @@
edge_descriptor add_edge(vertex_key const&, vertex_key const&, edge_properties const&);
//@}
- /** @name Remove Edge
- * Remove the edge from the graph.
+ /** @name Test Edge
+ * Determine if the edge, given by two vertices exists. This function a few
+ * convenience overloads that depend on the type of vertex store.
+ */
+ //@{
+ std::pair<edge_descriptor, bool> edge(vertex_descriptor, vertex_descriptor);
+ std::pair<edge_descriptor, bool> edge(vertex_properties const&, vertex_properties const&);
+ std::pair<edge_descriptor, bool> edge(vertex_key const&, vertex_key const&);
+ //@}
+
+ /** @name Remove Edge(s)
+ * 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 (both in and
+ * out edges) that vertex. The function(s) taking two vertices remove all
+ * edges connecting the two vertices. The so-called half-remove functions
+ * remove only the outgoing and incoming edges from the given vertex.
*/
//@{
void remove_edge(edge_descriptor e);
+
+ void remove_edges(vertex_descriptor);
+ void remove_edges(vertex_properties const&);
+ void remove_edges(vertex_key const&);
+
+ void remove_out_edges(vertex_descriptor);
+ void remove_out_edges(vertex_properties const&);
+ void remove_out_edges(vertex_key const&);
+
+ void remove_in_edges(vertex_descriptor);
+ void remove_in_edges(vertex_properties const&);
+ void remove_in_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 Size and Degree
@@ -220,7 +258,21 @@
in_edges_size_type in_degree(vertex_descriptor v) const;
incident_edges_size_type degree(vertex_descriptor v) const;
//@}
+ //
+ /** @name Out Edge Iterator */
+ //@{
+ out_edge_iterator begin_out_edges(vertex_descriptor) const;
+ out_edge_iterator end_out_edges(vertex_descriptor) const;
+ out_edge_range out_edges(vertex_descriptor) const;
+ //@}
+
+ /** @name In Edge Iterator */
+ //@{
+ in_edge_iterator begin_in_edges(vertex_descriptor) const;
+ in_edge_iterator end_in_edges(vertex_descriptor) const;
+ in_edge_range in_edges(vertex_descriptor) const;
+ //@}
/** @name Property Accessors
* Access the properties of the given vertex or edge.
@@ -305,38 +357,6 @@
}
/**
- * Disconnect the vertex from the graph. This removes all edges incident (both
- * incoming and outgoing) to the vertex, but will not remove the vertex itself.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_descriptor v)
-{
- // TODO: Implement me!
-}
-
-/**
- * Disconnect the vertex having the given properties from the graph.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_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_DG_PARAMS>
-void
-directed_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.
*/
@@ -344,7 +364,7 @@
void
directed_graph<VP,EP,VS,ES>::remove_vertex(vertex_descriptor v)
{
- disconnect_vertex(v);
+ remove_edges(v);
_verts.remove(v);
}
@@ -356,7 +376,7 @@
directed_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);
}
@@ -367,7 +387,7 @@
void
directed_graph<VP,EP,VS,ES>::remove_vertex(vertex_key const& k)
{
- disconnect_vertex(k);
+ remove_edges(k);
_verts.remove(k);
}
@@ -405,8 +425,6 @@
vertex_descriptor v,
edge_properties const& ep)
{
- typedef typename out_edge_store::out_tuple out_tuple;
- typedef typename in_edge_store::in_pair in_pair;
typedef typename vertex_type::out_iterator out_iterator;
typedef typename vertex_type::in_iterator in_iterator;
@@ -424,7 +442,8 @@
// Insert the edge stubs, getting iterators to each stub.
out_iterator i = src.connect_target(v, ep);
in_iterator j = tgt.connect_source(u);
- return vertex_type::bind_connection(i, j);
+ edge_descriptor e = vertex_type::bind_connection(i, j);
+ return e;
}
else {
return edge_descriptor(u, ins.first);
@@ -504,6 +523,189 @@
}
/**
+ * Remove all edges incident to this vertex. This will remove all edges in
+ * which the given vertex appears as either a source or target, effectively
+ * disconnecting the vertex from the graph. This is equivalent to calling
+ * remove_out_edges(v) and removing_in_edges(v).
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor v)
+{
+ remove_out_edges(v);
+ remove_in_edges(v);
+}
+
+/**
+ * Remove all edges incident to the vertex identified by the given properties.
+ * This is equivalent to remove_edges(find_vertex(vp));
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_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));
+}
+
+/**
+ * Remove all edges incident to the vertex identified by the given key. This is
+ * equivalent to remove_edges(find_vertex(k)).
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_edges(vertex_key const& k)
+{
+ remove_edges(find_vertex(k));
+}
+
+/**
+ * Remove all out edges of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_out_edges(vertex_descriptor v)
+{
+ // Basically, just iterate over the out edges of v and remove all of the
+ // incoming parts of each out edge. Don't forget to drop the edge count.
+ out_edge_range out = out_edges(v);
+ for( ; out.first != out.second; ++out.first) {
+ edge_descriptor e = *out.first;
+ vertex_type& tgt = _verts.vertex(e.target());
+ tgt.disconnect_source(e);
+ --_edges;
+ }
+
+ // Clear the out edges.
+ _verts.vertex(v).clear_out();
+}
+
+/**
+ * Remove all out edges of the vertex identified by the given properties. This
+ * is equivalent to remove_out_edges(find_vertex(vp));
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_out_edges(vertex_properties const& vp)
+{
+ BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+ remove_out_edges(find_vertex(vp));
+}
+
+/**
+ * Remove all out edges incident to the vertex identified by the given key. This
+ * is equivalent to remove_out_edges(find_vertex(k)).
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_out_edges(vertex_key const& k)
+{
+ remove_out_edges(find_vertex(k));
+}
+
+/**
+ * Remove all in edges of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_in_edges(vertex_descriptor v)
+{
+ // we have to disconnect the source of the opposite edge. Don't forget to
+ // drop the edge count.
+ in_edge_range in = in_edges(v);
+ for( ; in.first != in.second; ++in.first) {
+ edge_descriptor e = *in.first;
+ vertex_type& src = _verts.vertex(e.source());
+ src.disconnect_target(e);
+ --_edges;
+ }
+
+ // Clear out the vertices lists.
+ _verts.vertex(v).clear_in();
+}
+
+/**
+ * Remove all in edges of the vertex identified by the given properties. This
+ * is equivalent to remove_in_edges(find_vertex(vp));
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_in_edges(vertex_properties const& vp)
+{
+ BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+ remove_in_edges(find_vertex(vp));
+}
+
+/**
+ * Remove all out edges incident to the vertex identified by the given key. This
+ * is equivalent to remove_in_edges(find_vertex(k)).
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_in_edges(vertex_key const& k)
+{
+ remove_in_edges(find_vertex(k));
+}
+
+/**
+ * Remove all edges connecting the vertex u to v. This function only removes
+ * the edges with u as a source and v as a target.
+ *
+ * To remove all edges interconnecting u and v, first call remove_edges(u, v)
+ * followed by remove_edges(v, u).
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor u, vertex_descriptor 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
+ * exists or not.
+ *
+ * @todo Consider making descriptors "self-invalidating".
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+std::pair<typename directed_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+directed_graph<VP,EP,VS,ES>::edge(vertex_descriptor u, vertex_descriptor v)
+{
+ vertex_type& src = _verts.vertex(u);
+ typename vertex_type::out_iterator i = src.find_out(v);
+ return i != src.end_out() ?
+ std::make_pair(edge_descriptor(u, i), true) :
+ std::make_pair(edge_descriptor(), false);
+}
+
+/**
+ * Test to see if at least one edge connects the two vertices identified by
+ * the given properties. Return a pair containing a descriptor to the first such
+ * edge (if it exists), and a boolean value indicating whether it actually
+ * exists or not. This is equivalent to edge(find_vertex(u), find_vertex(v)).
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+std::pair<typename directed_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+directed_graph<VP,EP,VS,ES>::edge(vertex_properties const& u,
+ vertex_properties const& v)
+{
+ return edge(find_vertex(u), find_vertex(v));
+}
+/**
+ * Test to see if at least one edge connects the two vertices identified by
+ * the given key. Return a pair containing a descriptor to the first such
+ * edge (if it exists), and a boolean value indicating whether it actually
+ * exists or not. This is equivalent to edge(find_vertex(u), find_vertex(v)).
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+std::pair<typename directed_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+directed_graph<VP,EP,VS,ES>::edge(vertex_key const& u,
+ vertex_key const& v)
+{
+ return edge(find_vertex(u), find_vertex(v));
+}
+
+/**
* Return the number of vertices in the graph.
*/
template <BOOST_GRAPH_DG_PARAMS>
@@ -556,6 +758,66 @@
}
/**
+ * Return an iterator to the first out edge of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::out_edge_iterator
+directed_graph<VP,EP,VS,ES>::begin_out_edges(vertex_descriptor v) const
+{
+ return out_edge_iterator(v, _verts.vertex(v).begin_out());
+}
+
+/**
+ * Return an iterator past the end of then out edges of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::out_edge_iterator
+directed_graph<VP,EP,VS,ES>::end_out_edges(vertex_descriptor v) const
+{
+ return out_edge_iterator(v, _verts.vertex(v).end_out());
+}
+
+/**
+ * Return awn iterator range over the out edges of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::out_edge_range
+directed_graph<VP,EP,VS,ES>::out_edges(vertex_descriptor v) const
+{
+ return std::make_pair(begin_out_edges(v), end_out_edges(v));
+}
+
+/**
+ * Return an iterator to the first in edge of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::in_edge_iterator
+directed_graph<VP,EP,VS,ES>::begin_in_edges(vertex_descriptor v) const
+{
+ return in_edge_iterator(v, _verts.vertex(v).begin_in());
+}
+
+/**
+ * Return an iterator past the end of then in edges of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::in_edge_iterator
+directed_graph<VP,EP,VS,ES>::end_in_edges(vertex_descriptor v) const
+{
+ return in_edge_iterator(v, _verts.vertex(v).end_in());
+}
+
+/**
+ * Return awn 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
+directed_graph<VP,EP,VS,ES>::in_edges(vertex_descriptor v) const
+{
+ return std::make_pair(begin_in_edges(v), end_in_edges(v));
+}
+
+/**
* Return the properties for the given vertex.
*/
template <BOOST_GRAPH_DG_PARAMS>
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 08:24:39 EDT (Tue, 24 Jun 2008)
@@ -2,8 +2,6 @@
#ifndef DIRECTED_VERTEX_HPP
#define DIRECTED_VERTEX_HPP
-#include <list>
-#include "placeholder.hpp"
#include "directed_edge.hpp"
/**
@@ -32,7 +30,6 @@
typedef directed_edge<out_iterator> edge_descriptor;
-
/** @name Constructors */
//@{
inline directed_vertex()
@@ -74,6 +71,12 @@
inline out_iterator end_out() const
{ return _out.end(); }
+
+ inline out_iterator find_out(vertex_descriptor v) const
+ { return _out.find(v); }
+
+ inline void clear_out()
+ { _out.clear(); }
//@}
/** @name In Edges */
@@ -83,6 +86,12 @@
inline in_iterator end_in() const
{ return _in.end(); }
+
+ inline in_iterator find_in(vertex_descriptor v) const
+ { return _in.find(v); }
+
+ inline void clear_in()
+ { return _in.clear(); }
//@}
@@ -155,6 +164,11 @@
return _in.add(v);
}
+/**
+ * Having added the edge stubs, bind them together and return a descriptor over
+ * the edge. This is a static method because it doesn't pertain to single
+ * object.
+ */
template <typename V, typename O, typename I>
typename directed_vertex<V,O,I>::edge_descriptor
directed_vertex<V,O,I>::bind_connection(out_iterator i, in_iterator j)
@@ -181,8 +195,10 @@
void
directed_vertex<V,O,I>::disconnect_source(edge_descriptor e)
{
- // placeholder<sizeof(std::list<int>::iterator)> x = boost::get<2>(*e.out_edge());
- _in.remove(boost::get<2>(*e.out_edge()).template get<in_iterator>());
+ // Get the input iterator from the edge.
+ out_iterator o = e.out_edge();
+ in_iterator i = o->template get<2>().template get<in_iterator>();
+ _in.remove(i);
}
#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 08:24:39 EDT (Tue, 24 Jun 2008)
@@ -26,6 +26,7 @@
in_list()
: _edges()
+ , _size(0)
{ }
/**
@@ -34,10 +35,18 @@
*/
iterator add(vertex_descriptor v)
{
+ ++_size;
_edges.push_back(make_pair(v, out_edge_place()));
return boost::prior(_edges.end());
}
+ /** Remove the edge referenced by the given iterator. */
+ void remove(iterator i)
+ {
+ --_size;
+ _edges.erase(i);
+ }
+
/**
* Find the edge with the given iterator.
* @complexity O(deg(u))
@@ -51,19 +60,29 @@
return end;
}
- /** Remove the edge referenced by the given iterator. */
- void remove(iterator i)
- { _edges.erase(i); }
-
+ /** Remove all incoming edges from the list, resetting the size to 0. */
void clear()
- { _edges.clear(); }
+ {
+ _size = 0;
+ _edges.clear();
+ }
/** Get the number of incoming edges (in degree). */
size_type size() const
- { return _edges.size(); }
+ { return _size; }
+
+ /** @name Iterators */
+ //@{
+ iterator begin() const
+ { return _edges.begin(); }
+
+ iterator end() const
+ { return _edges.end(); }
+ //@}
private:
- mutable store_type _edges;
+ mutable store_type _edges;
+ size_type _size;
};
#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 08:24:39 EDT (Tue, 24 Jun 2008)
@@ -29,7 +29,6 @@
typedef typename boost::tuples::element<1, Edge>::type in_edge_place;
public:
typedef typename store_type::iterator iterator;
- typedef typename store_type::iterator const_iterator;
typedef typename store_type::size_type size_type;
inline out_list()
@@ -38,69 +37,61 @@
{ }
/** Allow an edge insertion? */
- std::pair<const_iterator, bool> allow(vertex_descriptor v) const
+ std::pair<iterator, bool> allow(vertex_descriptor v) const
{ return std::make_pair(_edges.end(), true); }
/** Add the edge to the list. */
- const_iterator add(vertex_descriptor v, edge_properties const& ep)
+ iterator add(vertex_descriptor v, edge_properties const& ep)
{
++_size;
_edges.push_back(out_tuple(v, ep, in_edge_place()));
return boost::prior(_edges.end());
}
- /** Find the edge with the given vertex. */
- iterator find(vertex_descriptor v)
+ /**
+ * Remove the edge with the given vertex.
+ * @complexity O(1)
+ */
+ void remove(iterator i)
{
- // TODO How do I write this with std::find?
- iterator i = _edges.begin(), end = _edges.end();
- for( ; i != end; ++i) {
- if(i->first == v) return i;
- }
- return end;
+ --_size;
+ _edges.erase(i);
}
/** Find the edge with the given vertex. */
- const_iterator find(vertex_descriptor v) const
+ iterator find(vertex_descriptor v) const
{
// TODO How do I write this with std::find?
- const_iterator i = _edges.begin(), end = _edges.end();
+ iterator i = _edges.begin(), end = _edges.end();
for( ; i != end; ++i) {
- if(i->first == v) return i;
+ if(i->template get<0>() == v) return i;
}
return end;
}
- /**
- * Remove the edge with the given vertex.
- * @complexity O(1)
- */
- void remove(iterator i)
+ /** Remove all incoming edges from the list, resetting the size to 0. */
+ void clear()
{
- --_size;
- _edges.erase(i);
+ _size = 0;
+ _edges.clear();
}
- /** Remove all edges. */
- void clear()
- { _edges.clear(); }
-
/** @name Iterators and 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(); }
+ //@}
/** Get the number of outgoing edges. */
inline size_type size() const
{ return _size; }
- //@{
private:
mutable store_type _edges;
- size_type _size;
+ size_type _size;
};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp 2008-06-24 08:24:39 EDT (Tue, 24 Jun 2008)
@@ -2,6 +2,8 @@
#ifndef VERTEX_DESCRIPTOR_HPP
#define VERTEX_DESCRIPTOR_HPP
+#include <iosfwd>
+
// Important notes about descriptors
//
// A descriptor is basically an opaque reference to an object. It's kind of
@@ -102,7 +104,9 @@
operator!=(basic_vertex_descriptor<D> const& a, basic_vertex_descriptor<D> const& b)
{ return a.get() != b.get(); }
-
+template <typename D>
+std::ostream& operator<<(std::ostream& os, const basic_vertex_descriptor<D>& v)
+{ return os << v.get(); }
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp 2008-06-24 08:24:39 EDT (Tue, 24 Jun 2008)
@@ -365,5 +365,4 @@
return iter != x.iter;
}
-
#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 08:24:39 EDT (Tue, 24 Jun 2008)
@@ -114,14 +114,33 @@
g.add_edge(V[0], V[1]);
g.add_edge(V[1], V[2]);
g.add_edge(V[2], V[0]);
+
+ // Ensure that the graph is set up correctly.
BOOST_ASSERT(g.num_vertices() == 3);
BOOST_ASSERT(g.num_edges() == 3);
+ BOOST_ASSERT(g.out_degree(V[0]) == 1);
+ BOOST_ASSERT(g.out_degree(V[1]) == 1);
+ BOOST_ASSERT(g.out_degree(V[2]) == 1);
+ BOOST_ASSERT(g.in_degree(V[0]) == 1);
+ BOOST_ASSERT(g.in_degree(V[1]) == 1);
+ BOOST_ASSERT(g.in_degree(V[2]) == 1);
+ BOOST_ASSERT(g.edge(V[0], V[1]).second);
+ BOOST_ASSERT(g.edge(V[2], V[0]).second);
+
+ // Disconnect the vertex
+ g.remove_edges(V[0]);
- g.disconnect_vertex(V[1]);
+ // Assert that the graph structure is correct after cutting v0 out of the
+ // graph. The only remaining edge should be (v1, v2)
BOOST_ASSERT(g.num_vertices() == 3);
- BOOST_ASSERT(g.degree(V[1]) == 0);
- BOOST_ASSERT(g.degree(V[0]) == 1);
- BOOST_ASSERT(g.degree(V[2]) == 1);
+ BOOST_ASSERT(g.num_edges() == 1);
+ BOOST_ASSERT(g.out_degree(V[0]) == 0);
+ BOOST_ASSERT(g.out_degree(V[1]) == 1);
+ BOOST_ASSERT(g.out_degree(V[2]) == 0);
+
+ 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 is a little different than above. We remove a vertex from the triangle,
@@ -242,8 +261,8 @@
typedef directed_graph<City, Road, vertex_list, edge_list> Graph;
test_add_remove_vertices<Graph>();
test_add_remove_edges<Graph>();
+ test_disconnect_vertex<Graph>();
/*
- // test_disconnect_vertex<Graph>();
// test_implicit_disconnect_vertex<Graph>();
// test_add_multi_edges<Graph>();
// test_remove_multi_edges<Graph>();
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