[Boost-commit] svn:boost r46626 - in sandbox/SOC/2008/graphs/trunk: boost/graphs libs/graphs

From: asutton_at_[hidden]
Date: 2008-06-23 10:57:55

Author: asutton
Date: 2008-06-23 10:57:54 EDT (Mon, 23 Jun 2008)
New Revision: 46626
URL: http://svn.boost.org/trac/boost/changeset/46626

Log:
Changed all directed iterators from const to non-const to support removals.
Implemented removals in edge_list.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp   |    17 ++++++++++-----                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp  |    37 +++++++++++-----------------------      
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp |    38 ++++++++++++++++++++++++-----------     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp       |    23 +++++++++++++++------                   
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp         |    37 +++++++++++-----------------------      
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp       |     3 -                                       
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp        |    42 +++++++++++++++++++-------------------- 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp      |    16 +++++---------                          
   sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp     |     4 +++                                     
   sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp               |     6 ++--                                    
   10 files changed, 111 insertions(+), 112 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-23 10:57:54 EDT (Mon, 23 Jun 2008)
@@ -11,13 +11,14 @@
  * @param VertexDesc A vertex descriptor
  * @param OutDesc An out edge descriptor.
  */
-template <typename OutTuple>
+template <typename OutIter>
 class directed_edge
 {
 public:
-    typedef OutTuple out_tuple;
-    typedef typename boost::tuples::element<0, OutTuple>::type vertex_descriptor;
-    typedef typename boost::tuples::element<1, OutTuple>::type edge_properties;
+    typedef OutIter out_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;
 
     /** @name Constructors */
     //@{
@@ -26,7 +27,7 @@
         , _out(0)
     { }
 
-    inline directed_edge(vertex_descriptor v, OutTuple const* o)
+    inline directed_edge(vertex_descriptor v, OutIter o)
         : _src(v)
         , _out(o)
     { }
@@ -40,6 +41,10 @@
     inline vertex_descriptor target() const
     { return boost::get<0>(*_out); }
 
+    /** Return the iterator to the out edge. */
+    inline OutIter out_edge() const
+    { return _out; }
+
     /** @name Property Accessors
      * Return the properties associated with the edge.
      */
@@ -65,7 +70,7 @@
 
 private:
     vertex_descriptor   _src;
-    OutTuple const*     _out;
+    OutIter             _out;
 };
 
 

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-23 10:57:54 EDT (Mon, 23 Jun 2008)
@@ -72,8 +72,10 @@
     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.
-    typedef directed_edge<typename out_edge_store::out_tuple> edge_descriptor;
+    // 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;
 
     // Generate the vertex type over the vertex properties, and in/out stores.
     // We can also pull size
@@ -414,33 +416,19 @@
     // Do we add the edge or not?
     std::pair<out_iterator, bool> ins = src.allow(v);
     if(ins.second) {
-        // The addition is allowed... Was there already an edge there? If not,
-        // connect u to v (and vice-versa) with the given properties. Otherwise,
-        // just return the existing edge.
-        edge_descriptor e;
-
         // If the returned iterator is past the end, then we have to create and
         // connect the edge.
         if(ins.first == src.end_out()) {
+            ++_edges;
+
             // Insert the edge stubs, getting iterators to each stub.
             out_iterator i = src.connect_target(v, ep);
             in_iterator j = tgt.connect_source(u);
-
-            // Biconnect the stubs. This relies heavily on the fact that these
-            // placeholders aren't squashing the underlying memory.
-            out_tuple& x = const_cast<out_tuple&>(*i);
-            in_pair& y = const_cast<in_pair&>(*j);
-            boost::get<2>(x).put(i);
-            y.second.put(j);
-            e = edge_descriptor(u, &*i);
+            return vertex_type::bind_connection(i, j);
         }
         else {
-            e = edge_descriptor(u, &*ins.first);
+            return edge_descriptor(u, ins.first);
         }
-
-        // Increment the edge count.
-        ++_edges;
-        return e;
     }
     else {
         // Can't add the edge? This is a flat refusal (as in a loop).
@@ -507,15 +495,14 @@
 void
 directed_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
 {
+    // Removing the edge involves the removal of both parts from the two
+    // connected vertices.
     vertex_type& src = _verts.vertex(e.source());
     vertex_type& tgt = _verts.vertex(e.target());
-
-    // Remove the connections... That's it.
-    src.disconnect_target(e.out_edge());
-    tgt.disconnect_source(e.source());
+    src.disconnect_target(e);
+    tgt.disconnect_source(e);
 }
 
-
 /**
  * Return the number of vertices in the graph.
  */

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-23 10:57:54 EDT (Mon, 23 Jun 2008)
@@ -2,6 +2,10 @@
 #ifndef DIRECTED_VERTEX_HPP
 #define DIRECTED_VERTEX_HPP
 
+#include <list>
+#include "placeholder.hpp"
+#include "directed_edge.hpp"
+
 /**
  * A directed vertex provides storage for both outgoing edges and in edges.
  * Each of these stores are parameterizable, although they should generally
@@ -18,14 +22,16 @@
 
     typedef typename OutStore::edge_properties edge_properties;
 
-    typedef typename out_store::const_iterator out_iterator;
+    typedef typename out_store::iterator out_iterator;
     typedef typename out_store::size_type out_size_type;
 
-    typedef typename in_store::const_iterator in_iterator;
+    typedef typename in_store::iterator in_iterator;
     typedef typename in_store::size_type in_size_type;
 
     typedef out_size_type incident_size_type;
 
+    typedef directed_edge<out_iterator> edge_descriptor;
+
 
     /** @name Constructors */
     //@{
@@ -42,14 +48,14 @@
     { }
     //@}
 
-
     std::pair<out_iterator, bool> allow(vertex_descriptor) const;
 
     out_iterator connect_target(vertex_descriptor, edge_properties const&);
     in_iterator connect_source(vertex_descriptor);
+    static edge_descriptor bind_connection(out_iterator, in_iterator);
 
-    // void disconnect_target(out_descriptor);
-    // void disconnect_source(vertex_descriptor);
+    void disconnect_target(edge_descriptor);
+    void disconnect_source(edge_descriptor);
 
     /** @name Property Accessors */
     //@{
@@ -133,7 +139,7 @@
 typename directed_vertex<V,O,I>::out_iterator
 directed_vertex<V,O,I>::connect_target(vertex_descriptor v, edge_properties const& ep)
 {
-    return _out.add(std::make_pair(v, ep));
+    return _out.add(v, ep);
 }
 
 /**
@@ -149,15 +155,23 @@
     return _in.add(v);
 }
 
-#if 0
+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)
+{
+    boost::get<2>(*i).put(j);
+    j->second.put(i);
+    return edge_descriptor(j->first, i);
+}
+
 /**
  * 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(out_descriptor d)
+directed_vertex<V,O,I>::disconnect_target(edge_descriptor e)
 {
-    _out.remove(d);
+    _out.remove(e.out_edge());
 }
 
 /**
@@ -165,10 +179,10 @@
  */
 template <typename V, typename O, typename I>
 void
-directed_vertex<V,O,I>::disconnect_source(vertex_descriptor v)
+directed_vertex<V,O,I>::disconnect_source(edge_descriptor e)
 {
-    _in.remove(v);
+    // 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>());
 }
-#endif
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp	2008-06-23 10:57:54 EDT (Mon, 23 Jun 2008)
@@ -45,20 +45,29 @@
     template <typename VertexDesc, typename Props>
     struct out_store
     {
-        typedef std::pair<VertexDesc, Props> out_pair;
-        typedef FirstAlloc<out_pair> out_allocator;
-        typedef out_list<out_pair, out_allocator> type;
+        // Define a dummy type that eventually be used to store iterators to
+        // in edge iterators. The actual out edge type is a tuple of target
+        // vertex, edge properties, and in edge iterator (placeheld). The in
+        // edge type is the source vertex and the out edge iterator (placeheld).
+        typedef placeholder<sizeof(typename std::list<int>::iterator)> dummy_type;
+        typedef boost::tuple<VertexDesc, Props, dummy_type> edge;
+        typedef FirstAlloc<edge> allocator;
+        typedef out_list<edge, allocator> type;
     };
 
     // The in store metafunction generates the type of list used to store
     // incoming edges of directed graph. In edges are represented by the
     // referencing vertex and an out edge descriptor.
-    template <typename VertexDesc, typename OutDesc>
+    template <typename VertexDesc>
     struct in_store
     {
-        typedef std::pair<VertexDesc, OutDesc> in_pair;
-        typedef SecondAlloc<in_pair> in_allocator;
-        typedef in_list<in_pair, in_allocator> type;
+        // Define a dummy type that will ultimately act as a placeholder for
+        // an iterator into the out edge vector. Use that to define the in edge
+        // pair.
+        typedef placeholder<sizeof(typename std::list<int>::iterator)> dummy_type;
+        typedef std::pair<VertexDesc, dummy_type> edge;
+        typedef SecondAlloc<edge> allocator;
+        typedef in_list<edge, allocator> type;
     };
 };
 

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-23 10:57:54 EDT (Mon, 23 Jun 2008)
@@ -18,10 +18,10 @@
 public:
     typedef Edge in_pair;
     typedef typename Edge::first_type vertex_descriptor;
-    typedef typename Edge::second_type edge_descriptor;
-
+private:
+    typedef typename Edge::second_type out_edge_place;
+public:
     typedef typename store_type::iterator iterator;
-    typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
     in_list()
@@ -32,41 +32,28 @@
      * 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 add(vertex_descriptor v)
     {
-        iterator i = _edges.begin(), end = _edges.end();
-        for( ; i != end; ++i) {
-            if(i->first == v) return i;
-        }
-        return end;
+        _edges.push_back(make_pair(v, out_edge_place()));
+        return boost::prior(_edges.end());
     }
 
     /**
      * Find the edge with the given iterator.
      * @complexity O(deg(u))
      */
-    const_iterator find(vertex_descriptor v) const
+    iterator find(vertex_descriptor v) const
     {
-        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;
         }
         return end;
     }
 
-    /**
-     * Remove the edge with the given vertex.
-     * @complexity O(deg(u))
-     */
-    void remove(vertex_descriptor v)
-    { _edges.erase(find(v)); }
+    /** Remove the edge referenced by the given iterator. */
+    void remove(iterator i)
+    { _edges.erase(i); }
 
     void clear()
     { _edges.clear(); }
@@ -76,7 +63,7 @@
     { return _edges.size(); }
 
 private:
-    store_type _edges;
+    mutable store_type _edges;
 };
 
 #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-23 10:57:54 EDT (Mon, 23 Jun 2008)
@@ -22,7 +22,6 @@
     typedef typename Edge::second_type out_edge_place;
 public:
     typedef typename store_type::iterator iterator;
-    typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
     in_vector()
@@ -33,7 +32,7 @@
      * Add the edge to the vector, returning an iterator to the added element.
      * @complexity O(1)
      */
-    const_iterator add(vertex_descriptor e)
+    iterator add(vertex_descriptor e)
     {
         _edges.push_back(std::make_pair(e, out_edge_place()));
         return boost::prior(_edges.end());

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-23 10:57:54 EDT (Mon, 23 Jun 2008)
@@ -5,8 +5,7 @@
 #include <list>
 
 #include <boost/next_prior.hpp>
-
-#include "out_descriptor.hpp"
+#include <boost/tuple/tuple.hpp>
 
 /**
  * The out list implements list-based, out-edge storage for directed graphs.
@@ -14,11 +13,8 @@
  * descriptor. List-based stores support fast inserts, slow finds, but do allow
  * removals.
  *
- * The edge is required to be a pair containing a vertex descriptor and a edge
- * property (not descriptor). This type defines the out_descriptor - an opaque
- * reference to a target/property pair.
- *
- * @param Edge A pair describing a vertex descriptor and the edge properties.
+
+ * @param Edge A tuple describing a vertex descriptor and the edge properties.
  * @param Alloc The allocator for edge pairs.
  */
 template <typename Edge, typename Alloc>
@@ -26,36 +22,37 @@
 {
     typedef std::list<Edge, Alloc> store_type;
 public:
-    typedef Edge out_pair;
-    typedef typename Edge::first_type vertex_descriptor;
-    typedef typename Edge::second_type edge_properties;
-
+    typedef Edge out_tuple;
+    typedef typename boost::tuples::element<0, Edge>::type vertex_descriptor;
+    typedef typename boost::tuples::element<1, Edge>::type edge_properties;
+private:
+    typedef typename boost::tuples::element<1, Edge>::type in_edge_place;
+public:
     typedef typename store_type::iterator iterator;
-    typedef typename store_type::const_iterator const_iterator;
+    typedef typename store_type::iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
-    typedef basic_out_descriptor<iterator> out_descriptor;
-
     inline out_list()
         : _edges()
         , _size(0)
     { }
 
     /** Allow an edge insertion? */
-    std::pair<out_descriptor, bool> allow(vertex_descriptor v)
-    { return std::make_pair(out_descriptor(_edges.end()), true); }
+    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)
+    const_iterator add(vertex_descriptor v, edge_properties const& ep)
     {
         ++_size;
-        _edges.push_back(e);
-        return out_descriptor(boost::prior(_edges.end()));
+        _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)
     {
+        // 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;
@@ -66,6 +63,7 @@
     /** Find the edge with the given vertex. */
     const_iterator find(vertex_descriptor v) const
     {
+        // TODO How do I write this with std::find?
         const_iterator i = _edges.begin(), end = _edges.end();
         for( ; i != end; ++i) {
             if(i->first == v) return i;
@@ -77,10 +75,10 @@
      * Remove the edge with the given vertex.
      * @complexity O(1)
      */
-    void remove(out_descriptor d)
+    void remove(iterator i)
     {
         --_size;
-        _edges.erase(d.iter);
+        _edges.erase(i);
     }
 
     /** Remove all edges. */
@@ -101,7 +99,7 @@
     //@{
 
 private:
-    store_type  _edges;
+    mutable store_type  _edges;
     size_type   _size;
 };
 

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-23 10:57:54 EDT (Mon, 23 Jun 2008)
@@ -6,9 +6,6 @@
 
 #include <boost/tuple/tuple.hpp>
 
-#include "placeholder.hpp"
-#include "out_descriptor.hpp"
-
 /**
  * The in/out vector implements vector-based, edge storage for directed graphs.
  * Each out edge is capable of referencing its corresponding in edge in another
@@ -30,7 +27,6 @@
 public:
     typedef std::pair<vertex_descriptor, edge_properties> out_pair;
     typedef typename store_type::iterator iterator;
-    typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
     inline out_vector()
@@ -41,16 +37,16 @@
      * Allow the edge addition? Unless policy dictates otherwise, always allow
      * the addition of the edge.
      */
-    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 vector.
      * @complexity O(1)
      */
-    const_iterator add(out_pair e)
+    iterator add(vertex_descriptor v, edge_properties const& ep)
     {
-        _edges.push_back(out_tuple(e.first, e.second, in_edge_place()));
+        _edges.push_back(out_tuple(v, ep, in_edge_place()));
         return boost::prior(_edges.end());
     }
 
@@ -60,15 +56,15 @@
 
     /** @name Iterators */
     //@{
-    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;
 };
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp	2008-06-23 10:57:54 EDT (Mon, 23 Jun 2008)
@@ -22,6 +22,10 @@
         : mem()
     { std::fill(mem, mem + N, 0); }
 
+    inline placeholder(placeholder const& x)
+        : mem()
+    { copy(x.mem, x.mem + N, mem); }
+
     template <typename T>
     inline placeholder(const T& x)
         : mem()

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-23 10:57:54 EDT (Mon, 23 Jun 2008)
@@ -231,21 +231,21 @@
     typedef directed_graph<City, Road, vertex_vector, edge_vector> Graph;
     test_add_vertices<Graph>();
     test_add_edges<Graph>();
-    // test_add_multi_edges<Graph>();
+    test_add_multi_edges<Graph>();
     // test_incidence_iterator<Graph>();
     // test_adjacency_iterator<Graph>();
 }
 
 void list_list()
 {
-    /*
     cout << "---- list/list ----" << endl;
     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_implicit_disconnect_vertex<Graph>();
-    test_add_multi_edges<Graph>();
+    // test_add_multi_edges<Graph>();
     // test_remove_multi_edges<Graph>();
     // test_incidence_iterator<Graph>();
     // test_adjacency_iterator<Graph>();