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

From: asutton_at_[hidden]
Date: 2008-07-08 07:58:57

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

Log:
Finished rewriting the in edge stores and corresponding test files.

Added:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_multiset.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_multiset.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_multiset.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_multiset.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp   |    62 +++++++++++++++++++++------------------ 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp    |    59 ++++++++++++++++++--------------------  
   sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp |    41 +++++++++++++++++++-------              
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp   |    14 +-------                                
   sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile        |     3 +                                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp  |     1                                         
   6 files changed, 96 insertions(+), 84 deletions(-)

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_multiset.hpp
==============================================================================

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-07-08 07:58:56 EDT (Tue, 08 Jul 2008)
@@ -3,6 +3,10 @@
 #define IN_LIST_HPP
 
 #include <list>
+#include <algorithm>
+
+#include <boost/descriptors.hpp>
+#include <boost/graphs/utility.hpp>
 
 /**
  * The in-edge list references incoming edges from other vertices. Each edge
@@ -14,73 +18,73 @@
 template <typename Edge, typename Alloc>
 class in_list
 {
-    typedef std::list<Edge, Alloc> store_type;
 public:
-    typedef Edge in_pair;
     typedef typename Edge::first_type vertex_descriptor;
-private:
-    typedef typename Edge::second_type out_edge_place;
-public:
+    typedef typename Edge::second_type out_descriptor;
+
+    typedef std::list<Edge, Alloc> store_type;
     typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;
 
-    in_list()
-        : _edges()
-        , _size(0)
+    typedef typename descriptor_traits<store_type>::descriptor_type in_descriptor;
+
+    // Constructor
+    inline in_list()
+        : _edges(), _size(0)
     { }
 
     /**
      * Add the edge to list.
      * @complexity O(1)
      */
-    iterator add(vertex_descriptor v)
+    inline in_descriptor add(vertex_descriptor v)
     {
         ++_size;
-        _edges.push_back(make_pair(v, out_edge_place()));
-        return boost::prior(_edges.end());
+        iterator i = _edges.insert(_edges.end(), std::make_pair(v, out_descriptor()));
+        return make_descriptor(_edges, i);
     }
 
     /**
-     * Remove the edge referenced by the given iterator.
-     * @complexity O(1)
+     * Find the edge whose source originates at the given vertex descriptor.
+     * @complexity O(d)
      */
-    iterator remove(iterator i)
+    inline in_descriptor find(vertex_descriptor v) const
     {
-        --_size;
-        return _edges.erase(i);
+        iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
+        return make_descriptor(_edges, i);
     }
 
     /**
-     * Find the edge with the given iterator. Is this function ever actually
-     * called? I have no idea...
-     * @complexity O(deg(u))
+     * Remove the edge referenced by the given iterator.
+     * @complexity O(1)
      */
-    iterator find(vertex_descriptor v) const
+    inline void remove(in_descriptor d)
     {
-        iterator i = _edges.begin(), end = _edges.end();
-        for( ; i != end; ++i) {
-            if(i->first == v) return i;
-        }
-        return end;
+        _edges.erase(make_iterator(_edges, d));
+        --_size;
     }
 
     /** Remove all incoming edges from the list, resetting the size to 0. */
-    void clear()
+    inline void clear()
     {
         _size = 0;
         _edges.clear();
     }
 
     /** Get the number of incoming edges (in degree). */
-    size_type size() const
+    inline size_type size() const
     { return _size; }
 
+    /** Returns true if there are no in edges. */
+    inline bool empty() const
+    { return _edges.empty(); }
+
     /** @name Iterators */
     //@{
-    iterator begin() const
+    inline iterator begin() const
     { return _edges.begin(); }
 
-    iterator end() const
+    inline iterator end() const
     { return _edges.end(); }
     //@}
 

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_multiset.hpp
==============================================================================

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp	2008-07-08 07:58:56 EDT (Tue, 08 Jul 2008)
@@ -4,7 +4,7 @@
 
 #include <map>
 
-#include "mapped_iterator.hpp"
+#include <boost/descriptors.hpp>
 
 /**
  * The in-edge set references incoming edges from other vertices. Each edge
@@ -17,59 +17,56 @@
 class in_set
 {
 public:
-    typedef Edge in_pair;
     typedef typename Edge::first_type vertex_descriptor;
-private:
-    typedef typename Edge::second_type out_edge_place;
-    typedef std::map<
-            vertex_descriptor,
-            std::pair<vertex_descriptor const, out_edge_place>,
-            Compare, Alloc
-        > store_type;
-public:
-    typedef mapped_iterator<typename store_type::iterator> iterator;
+    typedef typename Edge::second_type out_descriptor;
+
+    typedef std::map<vertex_descriptor, out_descriptor, Compare, Alloc> store_type;
+    typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;
 
-    in_set()
+    typedef typename descriptor_traits<store_type>::descriptor_type in_descriptor;
+
+    // Constructor
+    inline in_set()
         : _edges()
     { }
 
     /**
-     * Add the edge to the set.
-     * @complexity O(deg(u))
+     * Try to add the given vertex to the result set.
+     * @complexity O(lg(d))
      */
-    iterator add(vertex_descriptor v)
+    inline in_descriptor add(vertex_descriptor v)
     {
-        return _edges.insert(std::make_pair(v,
-                                std::make_pair(v, out_edge_place()))
-                            ).first;
+        std::pair<iterator, bool> i = _edges.insert(std::make_pair(v, out_descriptor()));
+        return i.second ? make_descriptor(_edges, i.first) : in_descriptor();
     }
 
-    /** Find the edge with the given vertex. */
-    iterator find(vertex_descriptor v)
-    { return _edges.find(v); }
-
     /**
-     * Find the edge with the given vertex. Is this function ever called?
+     * Find the edge whose source originates at the given vertex descriptor.
+     * @complexity O(lg(d))
      */
-    iterator find(vertex_descriptor v) const
-    { return _edges.find(v); }
+    inline in_descriptor find(vertex_descriptor v) const
+    { return make_descriptor(_edges, _edges.find(v)); }
 
     /**
      * Remove the edge with the given descriptor.
-     * @complexity O(log(in-deg(v)))
+     * @complexity O(lg(d))
      */
-    void remove(iterator i)
-    { _edges.erase(i.iter); }
+    inline void remove(in_descriptor d)
+    { _edges.erase(make_iterator(_edges, d)); }
 
     /** Remove all edges. */
-    void clear()
+    inline void clear()
     { _edges.clear(); }
 
     /** Get the number of incoming edges (in degree). */
-    size_type size() const
+    inline size_type size() const
     { return _edges.size(); }
 
+    /** Return true if there are no in edges. */
+    inline bool empty() const
+    { return _edges.empty(); }
+
     /** @name Iterators */
     //@{
     inline iterator begin() const
@@ -80,7 +77,7 @@
     //@}
 
 private:
-   mutable  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-07-08 07:58:56 EDT (Tue, 08 Jul 2008)
@@ -3,6 +3,10 @@
 #define IN_VECTOR_HPP
 
 #include <vector>
+#include <algorithm>
+
+#include <boost/descriptors.hpp>
+#include <boost/graphs/utility.hpp>
 
 /**
  * The in-edge vector references incoming edges from other vertices. Each edge
@@ -14,17 +18,18 @@
 template <typename Edge, typename Alloc>
 class in_vector
 {
-    typedef std::vector<Edge, Alloc> store_type;
 public:
-    typedef Edge in_pair;
     typedef typename Edge::first_type vertex_descriptor;
-private:
-    typedef typename Edge::second_type out_edge_place;
-public:
+    typedef typename Edge::second_type out_descriptor;
+
+    typedef std::vector<Edge, Alloc> store_type;
     typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;
 
-    in_vector()
+    typedef typename descriptor_traits<store_type>::descriptor_type in_descriptor;
+
+    // Constructor
+    inline in_vector()
         : _edges()
     { }
 
@@ -32,18 +37,32 @@
      * Add the edge to the vector, returning an iterator to the added element.
      * @complexity O(1)
      */
-    iterator add(vertex_descriptor e)
+    inline in_descriptor add(vertex_descriptor e)
     {
-        _edges.push_back(std::make_pair(e, out_edge_place()));
-        return boost::prior(_edges.end());
+        iterator i = _edges.insert(_edges.end(), std::make_pair(e, out_descriptor()));
+        return make_descriptor(_edges, i);
+    }
+
+    /**
+     * Find the edge whose source originates at the given vertex descriptor.
+     * @complexity O(d)
+     */
+    inline in_descriptor find(vertex_descriptor v) const
+    {
+        iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
+        return make_descriptor(_edges, i);
     }
 
     /** Get the number of incoming edges (in degree). */
-    size_type size() const
+    inline size_type size() const
     { return _edges.size(); }
 
+    /** Returns true if there are no in edges. */
+    inline bool empty() const
+    { return _edges.empty(); }
+
 private:
-    store_type _edges;
+    mutable store_type _edges;
 };
 
 #endif

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_multiset.hpp
==============================================================================

Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_multiset.hpp
==============================================================================

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:58:56 EDT (Tue, 08 Jul 2008)
@@ -5,12 +5,9 @@
 #include <map>
 #include <memory>
 
-#include <boost/type_traits.hpp>
 #include <boost/triple.hpp>
 #include <boost/descriptors.hpp>
 
-#include "mapped_iterator.hpp"
-
 /**
  * The out set implements set-based, out-edge storage for directed graphs.
  * out-edges are uniquely identified by their target vertex and property
@@ -36,13 +33,7 @@
     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_descriptor>,
-            Compare, Alloc
-        > store_type;
+    typedef std::map< vertex_descriptor, std::pair<edge_properties, in_descriptor>, Compare, Alloc> store_type;
     typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;
 
@@ -64,8 +55,7 @@
      */
     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())));
+        std::pair<iterator, bool> i = _edges.insert(std::make_pair(v, std::make_pair(ep, in_descriptor())));
         return i.second ? make_descriptor(_edges, i.first) : out_descriptor();
     }
 

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	2008-07-08 07:58:56 EDT (Tue, 08 Jul 2008)
@@ -19,5 +19,6 @@
 exe test_verts : test_verts.cpp : <include>../../ ;
 exe test_props : test_props.cpp : <include>../../ ;
 exe test_incs : test_incs.cpp : <include>../../ ;
-exe test_es : test_es.cpp : <include>../../ ;
 exe test_outs : test_outs.cpp : <include>../../ ;
+exe test_ins : test_ins.cpp : <include>../../ ;
+exe test_es : test_es.cpp : <include>../../ ;

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:58:56 EDT (Tue, 08 Jul 2008)
@@ -4,6 +4,7 @@
 #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"