[Boost-commit] svn:boost r46559 - sandbox/SOC/2008/graphs/trunk/boost/graphs

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