Boost logo

Boost-Commit :

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"
 


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk