From: asutton_at_[hidden]
Date: 2008-06-20 10:49:59
Author: asutton
Date: 2008-06-20 10:49:58 EDT (Fri, 20 Jun 2008)
New Revision: 46559
URL: http://svn.boost.org/trac/boost/changeset/46559
Log:
Finished implementing edge sets for directed graphs. Kind of in the process of
trying to clean up some of the store interfaces. They're a little gross.
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 38 ++++++++++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp | 31 +++++++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp | 54 +++++++++++++++---
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp | 14 +---
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp | 114 +++++++++++++++------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp | 59 +++++--------------
7 files changed, 165 insertions(+), 147 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-20 10:49:58 EDT (Fri, 20 Jun 2008)
@@ -190,6 +190,13 @@
edge_descriptor add_edge(vertex_key const&, vertex_key const&, edge_properties const&);
//@}
+ /** @name Remove Edge
+ * Remove the edge from the graph.
+ */
+ //@{
+ void remove_edge(edge_descriptor e);
+ //@}
+
/** @name Size and Degree
* Return the in/out or cumulative degree of the given vertex.
*/
@@ -396,8 +403,8 @@
// just return the existing edge.
edge_descriptor e;
if(ins.first == src.end_out()) {
- out_descriptor o = src.connect_to(v, ep);
- tgt.connect_from(u, o);
+ out_descriptor o = src.connect_target(v, ep);
+ tgt.connect_source(u, o);
e = edge_descriptor(u, o);
}
else {
@@ -434,8 +441,8 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::edge_descriptor
directed_graph<VP,EP,VS,ES>::add_edge(vertex_properties const& u,
- vertex_properties const& v,
- edge_properties const& ep)
+ vertex_properties const& v,
+ edge_properties const& ep)
{
return add_edge(find_vertex(u), find_vertex(v), ep);
}
@@ -447,7 +454,7 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::edge_descriptor
directed_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
- vertex_key const& v)
+ vertex_key const& v)
{
return add_edge(u, v, edge_properties());
}
@@ -459,13 +466,30 @@
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::edge_descriptor
directed_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
- vertex_key const& v,
- edge_properties const& ep)
+ vertex_key const& v,
+ edge_properties const& ep)
{
return add_edge(find_vertex(u), find_vertex(v), ep);
}
/**
+ * Remove the edge connecting the two vertices. This removes only the given
+ * edge. Other edges connecting the two vertices remain.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
+{
+ vertex_type& src = _verts.vertex(e.source());
+ vertex_type& tgt = _verts.vertex(e.target());
+
+ // Remove the connections... That's it.
+ src.disconnect_target(e.target());
+ tgt.disconnect_source(e.source());
+}
+
+
+/**
* Return the number of vertices in the graph.
*/
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-20 10:49:58 EDT (Fri, 20 Jun 2008)
@@ -46,8 +46,11 @@
std::pair<out_iterator, bool> allow(vertex_descriptor) const;
- out_descriptor connect_to(vertex_descriptor, edge_properties const&);
- void connect_from(vertex_descriptor, out_descriptor);
+ out_descriptor connect_target(vertex_descriptor, edge_properties const&);
+ void connect_source(vertex_descriptor, out_descriptor);
+
+ void disconnect_target(vertex_descriptor);
+ void disconnect_source(vertex_descriptor);
/** @name Property Accessors */
//@{
@@ -129,7 +132,7 @@
*/
template <typename V, typename O, typename I>
typename directed_vertex<V,O,I>::out_descriptor
-directed_vertex<V,O,I>::connect_to(vertex_descriptor v, edge_properties const& ep)
+directed_vertex<V,O,I>::connect_target(vertex_descriptor v, edge_properties const& ep)
{
return _out.add(std::make_pair(v, ep));
}
@@ -142,9 +145,29 @@
*/
template <typename V, typename O, typename I>
void
-directed_vertex<V,O,I>::connect_from(vertex_descriptor v, out_descriptor o)
+directed_vertex<V,O,I>::connect_source(vertex_descriptor v, out_descriptor o)
{
return _in.add(std::make_pair(v, o));
}
+/**
+ * Disconnect this vertex from its target, removing the outgoing edge.
+ */
+template <typename V, typename O, typename I>
+void
+directed_vertex<V,O,I>::disconnect_target(vertex_descriptor v)
+{
+ _out.remove(v);
+}
+
+/**
+ * Disconnect this vertex from its source, removing the incoming edge.
+ */
+template <typename V, typename O, typename I>
+void
+directed_vertex<V,O,I>::disconnect_source(vertex_descriptor v)
+{
+ _in.remove(v);
+}
+
#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-20 10:49:58 EDT (Fri, 20 Jun 2008)
@@ -20,6 +20,7 @@
typedef typename Edge::first_type vertex_descriptor;
typedef typename Edge::second_type edge_descriptor;
+ typedef typename store_type::iterator iterator;
typedef typename store_type::const_iterator const_iterator;
typedef typename store_type::size_type size_type;
@@ -27,7 +28,48 @@
: _edges()
{ }
- void add(in_pair);
+ /**
+ * Add the edge to list.
+ * @complexity O(1)
+ */
+ void add(in_pair e)
+ { _edges.push_back(e); }
+
+ /**
+ * Find the edge with the given iterator.
+ * @complexity O(deg(u))
+ */
+ iterator find(vertex_descriptor v)
+ {
+ iterator i = _edges.begin(), end = _edges.end();
+ for( ; i != end; ++i) {
+ if(i->first == v) return i;
+ }
+ return end;
+ }
+
+ /**
+ * Find the edge with the given iterator.
+ * @complexity O(deg(u))
+ */
+ const_iterator find(vertex_descriptor v) const
+ {
+ const_iterator i = _edges.begin(), end = _edges.end();
+ for( ; i != end; ++i) {
+ if(i->first == v) return i;
+ }
+ return end;
+ }
+
+ /**
+ * Remove the edge with the given vertex.
+ * @complexity O(deg(u))
+ */
+ void remove(vertex_descriptor v)
+ { _edges.erase(find(v)); }
+
+ void clear()
+ { _edges.clear(); }
/** Get the number of incoming edges (in degree). */
size_type size() const
@@ -37,14 +79,4 @@
store_type _edges;
};
-/**
- * Add the given pair to the edge set.
- */
-template <typename E, typename A>
-void
-in_list<E,A>::add(in_pair e)
-{
- _edges.push_back(e);
-}
-
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp 2008-06-20 10:49:58 EDT (Fri, 20 Jun 2008)
@@ -27,7 +27,9 @@
: _edges()
{ }
- void add(in_pair);
+ /** Add the edge to the vector. */
+ void add(in_pair e)
+ { _edges.push_back(e); }
/** Get the number of incoming edges (in degree). */
size_type size() const
@@ -37,14 +39,4 @@
store_type _edges;
};
-/**
- * Add the given pair to the edge set.
- */
-template <typename E, typename A>
-void
-in_vector<E,A>::add(in_pair e)
-{
- _edges.push_back(e);
-}
-
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp 2008-06-20 10:49:58 EDT (Fri, 20 Jun 2008)
@@ -37,7 +37,7 @@
//@{
OutPair& pair() const
- { return reinterpret_cast<OutPair*>(_d); }
+ { return *reinterpret_cast<OutPair*>(_d); }
vertex_descriptor target() const
{ return pair().first; }
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-20 10:49:58 EDT (Fri, 20 Jun 2008)
@@ -5,6 +5,7 @@
#include <list>
#include "out_descriptor.hpp"
+#include "select.hpp"
/**
* The out list implements list-based, out-edge storage for directed graphs.
@@ -39,12 +40,48 @@
, _size(0)
{ }
- std::pair<const_iterator, bool> allow(vertex_descriptor v) const;
- out_descriptor add(out_pair);
- iterator find(out_pair);
- const_iterator find(out_pair) const;
- void remove(out_pair);
- void clear();
+ /** Allow an edge insertion? */
+ std::pair<const_iterator, bool> allow(vertex_descriptor v) const
+ { return std::make_pair(_edges.end(), true); }
+
+ /** Add the edge to the list. */
+ out_descriptor add(out_pair e)
+ {
+ ++_size;
+ _edges.push_back(e);
+ return _edges.back();
+ }
+
+ /** Find the edge with the given vertex. */
+ iterator find(vertex_descriptor v)
+ {
+ iterator i = _edges.begin(), end = _edges.end();
+ for( ; i != end; ++i) {
+ if(i->first == v) return i;
+ }
+ return end;
+ }
+
+ /** Find the edge with the given vertex. */
+ const_iterator find(vertex_descriptor v) const
+ {
+ const_iterator i = _edges.begin(), end = _edges.end();
+ for( ; i != end; ++i) {
+ if(i->first == v) return i;
+ }
+ return end;
+ }
+
+ /** Remove the edge with the given vertex. */
+ void remove(vertex_descriptor v)
+ {
+ --_size;
+ _edges.erase(find(v));
+ }
+
+ /** Remove all edges. */
+ void clear()
+ { _edges.clear(); }
/** @name Iterators and Size */
//@{
@@ -64,69 +101,4 @@
size_type _size;
};
-/**
- * Out lists always allow the insertion of new edges, unless configured by
- * policy to do otherwise.
- */
-template <typename E, typename A>
-std::pair<typename out_list<E,A>::const_iterator, bool>
-out_list<E,A>::allow(vertex_descriptor v) const
-{
- return std::make_pair(_edges.end(), true);
-}
-
-/**
- * Add the incident edge, returning the property descriptor of the added
- * incidence pair.
- */
-template <typename E, typename A>
-typename out_list<E,A>::out_descriptor
-out_list<E,A>::add(out_pair e)
-{
- ++_size;
- _edges.push_back(e);
- return _edges.back();
-}
-
-/**
- * Find the requested incidence pair in the list, returning an iterator to it.
- */
-template <typename E, typename A>
-typename out_list<E,A>::iterator
-out_list<E,A>::find(out_pair e)
-{
- return std::find(_edges.begin(), _edges.end(), e);
-}
-
-/**
- * Find the requested incidence pair in the list, returning an iterator to it.
- */
-template <typename E, typename A>
-typename out_list<E,A>::const_iterator
-out_list<E,A>::find(out_pair e) const
-{
- return std::find(_edges.begin(), _edges.end(), e);
-}
-
-/**
- * Remove the given incidence pair from the out list.
- */
-template <typename E, typename A>
-void
-out_list<E,A>::remove(out_pair e)
-{
- --_size;
- _edges.erase(find(e));
-}
-
-/**
- * Remove all edges from the out list.
- */
-template <typename E, typename A>
-void
-out_list<E,A>::clear()
-{
- _edges.clear();
-}
-
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp 2008-06-20 10:49:58 EDT (Fri, 20 Jun 2008)
@@ -38,12 +38,25 @@
: _edges()
{ }
- std::pair<const_iterator, bool> allow(vertex_descriptor v) const;
- out_descriptor add(out_pair);
+ /** Allow the addition? */
+ std::pair<const_iterator, bool> allow(vertex_descriptor v) const
+ { return std::make_pair(_edges.end(), true); }
+
+ /**
+ * Add the edge to the vector.
+ * @complexity O(1)
+ */
+ out_descriptor add(out_pair e)
+ {
+ _edges.push_back(e);
+ return _edges.back();
+ }
- vertex_descriptor vertex(out_descriptor) const;
+ /** Get the number of outgoing edges. */
+ inline size_type size() const
+ { return _edges.size(); }
- /** @name Iterators and Size */
+ /** @name Iterators */
//@{
inline const_iterator begin() const
{ return _edges.begin(); }
@@ -51,48 +64,10 @@
inline const_iterator end() const
{ return _edges.end(); }
- /** Get the number of outgoing edges. */
- inline size_type size() const
- { return _edges.size(); }
//@{
private:
store_type _edges;
};
-/**
- * Out vectors always allow the insertion of new edges, unless configured by
- * policy to do otherwise.
- */
-template <typename E, typename A>
-std::pair<typename out_vector<E,A>::const_iterator, bool>
-out_vector<E,A>::allow(vertex_descriptor v) const
-{
- return std::make_pair(_edges.end(), true);
-}
-
-/**
- * Add the incident edge, returning the property descriptor of the added
- * incidence pair.
- */
-template <typename E, typename A>
-typename out_vector<E,A>::out_descriptor
-out_vector<E,A>::add(out_pair e)
-{
- _edges.push_back(e);
- return _edges.back();
-}
-
-/**
- * Return the target vertex of the given edge property descriptor. Because each
- * property descriptor references a unique edge, we can easily access the
- * corresponding target vertex.
- */
-template <typename E, typename A>
-typename out_vector<E,A>::vertex_descriptor
-out_vector<E,A>::vertex(out_descriptor p) const
-{
- return p.target();
-}
-
#endif