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"