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

From: asutton_at_[hidden]
Date: 2008-07-08 07:29:26

Author: asutton
Date: 2008-07-08 07:29:25 EDT (Tue, 08 Jul 2008)
New Revision: 47213
URL: http://svn.boost.org/trac/boost/changeset/47213

Log:
Initial rewrite of out edge stores.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp      |    66 +++++++++++++++++++++------------------ 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp       |    45 ++++++++++++++++----------              
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp    |     2                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp |     1                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp        |     4 +-                                      
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp      |    42 ++++++++++++++----------                
   6 files changed, 90 insertions(+), 70 deletions(-)

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-07-08 07:29:25 EDT (Tue, 08 Jul 2008)
@@ -3,8 +3,11 @@
 #define OUT_LIST_HPP
 
 #include <list>
+#include <algorithm>
 
-#include <boost/next_prior.hpp>
+#include <boost/triple.hpp>
+#include <boost/descriptors.hpp>
+#include <boost/graphs/utility.hpp>
 
 /**
  * The out list implements list-based, out-edge storage for directed graphs.
@@ -19,32 +22,30 @@
 template <typename Edge, typename Alloc>
 class out_list
 {
-    typedef std::list<Edge, Alloc> store_type;
 public:
-    typedef Edge out_tuple;
     typedef typename Edge::first_type vertex_descriptor;
     typedef typename Edge::second_type edge_properties;
-private:
-    typedef typename Edge::third_type in_edge_place;
-public:
+    typedef typename Edge::third_type in_descriptor;
+
+    typedef std::list<Edge, Alloc> store_type;
     typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;
 
+    typedef typename descriptor_traits<store_type>::descriptor_type out_descriptor;
+
     inline out_list()
-        : _edges()
-        , _size(0)
+        : _edges(), _size(0)
     { }
 
-    /** Allow an edge insertion? */
-    std::pair<iterator, bool> allow(vertex_descriptor v) const
-    { return std::make_pair(_edges.end(), true); }
-
-    /** Add the edge to the list. */
-    iterator add(vertex_descriptor v, edge_properties const& ep)
+    /**
+     * Add the edge to the list.
+     * @complexity O(1)
+     */
+    out_descriptor add(vertex_descriptor v, edge_properties const& ep)
     {
         ++_size;
-        _edges.push_back(out_tuple(v, ep, in_edge_place()));
-        return boost::prior(_edges.end());
+        iterator i = _edges.insert(_edges.end(), make_triple(v, ep, in_descriptor()));
+        return make_descriptor(_edges, i);
     }
 
     /**
@@ -52,22 +53,20 @@
      * the sequence.
      * @complexity O(1)
      */
-    iterator remove(iterator i)
+    iterator remove(out_descriptor d)
     {
         --_size;
-        return _edges.erase(i);
+        return _edges.erase(make_iterator(_edges, d));
     }
 
-
-    /** Find the edge with the given vertex. */
-    iterator find(vertex_descriptor v) const
+    /**
+     * Find the edge with the given vertex.
+     * @complexity O(d)
+     */
+    out_descriptor find(vertex_descriptor v) const
     {
-        // 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;
+        iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
+        return make_descriptor(_edges, i);
     }
 
     /** Remove all incoming edges from the list, resetting the size to 0. */
@@ -77,6 +76,15 @@
         _edges.clear();
     }
 
+    /** Get the number of outgoing edges. */
+    inline size_type size() const
+    { return _size; }
+
+    /** Returns true if there are not out edges. */
+    inline bool empty() const
+    { return _edges.empty(); }
+
+
     /** @name Iterators and Size */
     //@{
     inline iterator begin() const
@@ -86,10 +94,6 @@
     { return _edges.end(); }
     //@}
 
-    /** Get the number of outgoing edges. */
-    inline size_type size() const
-    { return _size; }
-
 private:
     mutable store_type  _edges;
     size_type           _size;

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp	2008-07-08 07:29:25 EDT (Tue, 08 Jul 2008)
@@ -6,6 +6,8 @@
 #include <memory>
 
 #include <boost/type_traits.hpp>
+#include <boost/triple.hpp>
+#include <boost/descriptors.hpp>
 
 #include "mapped_iterator.hpp"
 
@@ -29,24 +31,24 @@
 class out_set
 {
 public:
-    typedef Edge out_tuple;
     typedef typename Edge::first_type vertex_descriptor;
     typedef typename Edge::second_type edge_properties;
-private:
-    typedef typename Edge::third_type in_edge_place;
+    typedef typename Edge::third_type in_descriptor;
 
     // Reconstruct the edge triple into a key/value type thing for the map.
     // Unfortunately, we're storing the descriptor twice, but this does make
     // iteration and referencing a bit easier.
     typedef std::map<
             vertex_descriptor,
-            triple<vertex_descriptor, edge_properties, in_edge_place>,
+            triple<vertex_descriptor, edge_properties, in_descriptor>,
             Compare, Alloc
         > store_type;
-public:
-    typedef mapped_iterator<typename store_type::iterator> iterator;
+    typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;
 
+    typedef typename descriptor_traits<store_type>::descriptor_type out_descriptor;
+
+    // Constructor
     inline out_set()
         : _edges()
     { }
@@ -56,30 +58,43 @@
     { return std::make_pair(_edges.find(v), true); }
 
     /**
-     * Add the edge to the set.
+     * Try to add the given edge to the set. If the edge already exists, return
+     * a null descriptor.
      * @complexity O(log(deg(v)))
      */
-    iterator add(vertex_descriptor v, edge_properties const& ep)
-    { return _edges.insert(std::make_pair(v, make_triple(v, ep, in_edge_place()))).first; }
+    out_descriptor add(vertex_descriptor v, edge_properties const& ep)
+    {
+        std::pair<iterator, bool> i =
+            _edges.insert(std::make_pair(v, make_triple(v, ep, in_descriptor())));
+        return i.second ? make_descriptor(_edges, i.first) : out_descriptor();
+    }
 
     /**
      * Find the edge with the given vertex descriptor.
      * @complexity O(log(deg(v)))
      */
-    iterator find(vertex_descriptor v) const
-    { return _edges.find(v); }
+    out_descriptor find(vertex_descriptor v) const
+    { return make_descriptor(_edges, _edges.find(v)); }
 
     /**
      * Remove the edge with the given vertex descriptor.
      * @complexity O(log(deg(u)))
      */
-    void remove(iterator d)
-    { _edges.erase(d.iter); }
+    void remove(out_descriptor d)
+    { _edges.erase(make_iterator(_edges, d)); }
 
     /** Remove all edges. */
     void clear()
     { _edges.clear(); }
 
+    /** Get the number of outgoing edges. */
+    inline size_type size() const
+    { return _edges.size(); }
+
+    /** Returns true if there are no out edges. */
+    inline bool empty() const
+    { return _edges.empty(); }
+
     /** @name Iterators */
     //@{
     inline iterator begin() const
@@ -89,10 +104,6 @@
     { return iterator(); }
     //@}
 
-    /** Get the number of outgoing edges. */
-    inline size_type size() const
-    { return _edges.size(); }
-
 private:
     mutable store_type _edges;
 };

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-07-08 07:29:25 EDT (Tue, 08 Jul 2008)
@@ -23,7 +23,7 @@
     typedef typename Edge::first_type vertex_descriptor;
     typedef typename Edge::second_type edge_properties;
     typedef typename Edge::third_type in_descriptor;
-    
+
     typedef std::vector<Edge, Alloc> store_type;
     typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp	2008-07-08 07:29:25 EDT (Tue, 08 Jul 2008)
@@ -60,7 +60,6 @@
     typedef std::vector<Vertex, Allocator> store_type;
     typedef typename store_type::size_type size_type;
     typedef typename store_type::iterator iterator;
-    typedef typename store_type::const_iterator const_iterator;
 
     typedef Vertex vertex_type;
     typedef typename Vertex::vertex_properties vertex_properties;

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp	2008-07-08 07:29:25 EDT (Tue, 08 Jul 2008)
@@ -29,8 +29,8 @@
 
     Vertex u = VertexDesc(0);
 
-    // This is a little different protocol.. First, try to insert the edge
-    // into the incidence list, but lave the property slot "empty".
+    // This is a little different protocol. First, try to insert the edge into
+    // the incidence list, but lave the property slot "empty".
     IncDesc i = incs.add(v);
     if(incs.valid(i)) {
         PropDesc p = props.add(ep);

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp	2008-07-08 07:29:25 EDT (Tue, 08 Jul 2008)
@@ -2,35 +2,34 @@
 #include <iostream>
 
 #include <boost/graphs/out_vector.hpp>
-
+#include <boost/graphs/out_list.hpp>
+#include <boost/graphs/out_set.hpp>
 #include "typestr.hpp"
+#include "out_edge_traits.hpp"
 
 using namespace std;
 using namespace boost;
 
-struct out_vector_tag : sequence_tag, unstable_remove_tag { };
-struct out_list_tag : sequence_tag, stable_mutators_tag { };
-struct out_set_tag : associative_container_tag, stable_mutators_tag { };
-
-template <typename Outs>
-struct out_edge_traits
-{ typedef typename Outs::category cateogry; };
-
-template <typename Outs>
-typename out_edge_traits<Outs>::category
-out_edge_category(Outs const&)
-{ return typename out_edge_traits<Outs>::category(); }
-
-template <typename Edge, typename Alloc>
-struct out_edge_traits<out_vector<Edge, Alloc>>
-{ typedef out_vector_tag category; };
-
 
 typedef index_descriptor<size_t> VertexDesc;
 typedef index_descriptor<size_t> InDesc;
 typedef int EdgeProps;
 typedef triple<VertexDesc, EdgeProps, InDesc> OutEdge;
 typedef allocator<OutEdge> Alloc;
+typedef less<VertexDesc> Compare;
+
+template <typename Outs>
+void test_remove(Outs& outs, stable_mutators_tag)
+{
+    size_t n = outs.size();
+    outs.remove(outs.find(3));
+    BOOST_ASSERT(outs.size() == n - 1);
+    cout << "  * size after remove: " << outs.size() << endl;
+}
+
+template <typename Outs>
+void test_remove(Outs& outs, unstable_remove_tag)
+{ /* Don't do anything. */ }
 
 template <typename Outs>
 void test()
@@ -38,15 +37,22 @@
     Outs outs;
     cout << "--- " << typestr(out_edge_category(outs)) << " ---" <<  endl;
 
+    // Add some vertices.
     BOOST_ASSERT(outs.empty());
     for(int i = 0; i < 5; ++i) {
         outs.add(VertexDesc(i), i * i);
     }
     BOOST_ASSERT(outs.size() == 5);
+    cout << "  * size after building: " << outs.size() << endl;
+
+    test_remove(outs, out_edge_category(outs));
 }
 
 int main()
 {
     test<out_vector<OutEdge, Alloc>>();
+    test<out_list<OutEdge, Alloc>>();
+    test<out_set<OutEdge, Compare, Alloc>>();
+
     return 0;
 }