Subject: [Boost-commit] svn:boost r55156 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2009-07-30 14:41:48
Author: jewillco
Date: 2009-07-25 15:41:01 EDT (Sat, 25 Jul 2009)
New Revision: 55156
URL: http://svn.boost.org/trac/boost/changeset/55156
Log:
Changed to use Boost.Iterator, and fixed precision and overflow issues in the sorted generator
Text files modified:
trunk/boost/graph/erdos_renyi_generator.hpp | 166 +++++++++++++++------------------------
1 files changed, 66 insertions(+), 100 deletions(-)
Modified: trunk/boost/graph/erdos_renyi_generator.hpp
==============================================================================
--- trunk/boost/graph/erdos_renyi_generator.hpp (original)
+++ trunk/boost/graph/erdos_renyi_generator.hpp 2009-07-25 15:41:01 EDT (Sat, 25 Jul 2009)
@@ -17,14 +17,23 @@
#include <boost/random/uniform_int.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/random/geometric_distribution.hpp>
-#include <boost/type_traits/is_base_and_derived.hpp>
+#include <boost/type_traits/is_base_of.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/config/no_tr1/cmath.hpp>
+#include <boost/iterator/iterator_facade.hpp>
namespace boost {
template<typename RandomGenerator, typename Graph>
class erdos_renyi_iterator
+ : public iterator_facade<
+ erdos_renyi_iterator<RandomGenerator, Graph>,
+ std::pair<typename graph_traits<Graph>::vertices_size_type,
+ typename graph_traits<Graph>::vertices_size_type>,
+ std::input_iterator_tag,
+ const
+ std::pair<typename graph_traits<Graph>::vertices_size_type,
+ typename graph_traits<Graph>::vertices_size_type>&>
{
typedef typename graph_traits<Graph>::directed_category directed_category;
typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
@@ -32,17 +41,9 @@
BOOST_STATIC_CONSTANT
(bool,
- is_undirected = (is_base_and_derived<undirected_tag,
- directed_category>::value
- || is_same<undirected_tag, directed_category>::value));
+ is_undirected = (is_base_of<undirected_tag, directed_category>::value));
public:
- typedef std::input_iterator_tag iterator_category;
- typedef std::pair<vertices_size_type, vertices_size_type> value_type;
- typedef const value_type& reference;
- typedef const value_type* pointer;
- typedef void difference_type;
-
erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
double fraction = 0.0, bool allow_self_loops = false)
@@ -61,29 +62,17 @@
next();
}
- reference operator*() const { return current; }
- pointer operator->() const { return ¤t; }
+ const std::pair<vertices_size_type, vertices_size_type>&
+ dereference() const { return current; }
- erdos_renyi_iterator& operator++()
- {
+ void increment() {
--edges;
next();
- return *this;
- }
-
- erdos_renyi_iterator operator++(int)
- {
- erdos_renyi_iterator temp(*this);
- ++(*this);
- return temp;
}
- bool operator==(const erdos_renyi_iterator& other) const
+ bool equal(const erdos_renyi_iterator& other) const
{ return edges == other.edges; }
- bool operator!=(const erdos_renyi_iterator& other) const
- { return !(*this == other); }
-
private:
void next()
{
@@ -98,11 +87,19 @@
vertices_size_type n;
edges_size_type edges;
bool allow_self_loops;
- value_type current;
+ std::pair<vertices_size_type, vertices_size_type> current;
};
template<typename RandomGenerator, typename Graph>
class sorted_erdos_renyi_iterator
+ : public iterator_facade<
+ sorted_erdos_renyi_iterator<RandomGenerator, Graph>,
+ std::pair<typename graph_traits<Graph>::vertices_size_type,
+ typename graph_traits<Graph>::vertices_size_type>,
+ std::input_iterator_tag,
+ const
+ std::pair<typename graph_traits<Graph>::vertices_size_type,
+ typename graph_traits<Graph>::vertices_size_type>&>
{
typedef typename graph_traits<Graph>::directed_category directed_category;
typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
@@ -110,20 +107,13 @@
BOOST_STATIC_CONSTANT
(bool,
- is_undirected = (is_base_and_derived<undirected_tag,
- directed_category>::value
- || is_same<undirected_tag, directed_category>::value));
+ is_undirected = (is_base_of<undirected_tag, directed_category>::value));
public:
- typedef std::input_iterator_tag iterator_category;
- typedef std::pair<vertices_size_type, vertices_size_type> value_type;
- typedef const value_type& reference;
- typedef const value_type* pointer;
- typedef void difference_type;
-
sorted_erdos_renyi_iterator()
: gen(), rand_vertex(0.5), n(0), allow_self_loops(false)
- , src((std::numeric_limits<vertices_size_type>::max)()), tgt(0), prob(0)
+ , src((std::numeric_limits<vertices_size_type>::max)()),
+ tgt_index(vertices_size_type(-1)), prob(.5)
{ }
// NOTE: The default probability has been changed to be the same as that
@@ -132,8 +122,8 @@
sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
double prob = 0.5,
bool loops = false)
- : gen(), rand_vertex(prob), n(n), allow_self_loops(loops), src(0)
- , tgt(0), prob(prob)
+ : gen(), rand_vertex(1. - prob), n(n), allow_self_loops(loops), src(0)
+ , tgt_index(vertices_size_type(-1)), prob(prob)
{
this->gen.reset(new uniform_01<RandomGenerator>(gen));
@@ -141,86 +131,62 @@
next();
}
- reference operator*() const { return current; }
- pointer operator->() const { return ¤t; }
-
- sorted_erdos_renyi_iterator& operator++()
- {
- next();
- return *this;
+ const std::pair<vertices_size_type, vertices_size_type>&
+ dereference() const {
+ return current;
}
- sorted_erdos_renyi_iterator operator++(int)
- {
- sorted_erdos_renyi_iterator temp(*this);
- ++(*this);
- return temp;
+ bool equal(const sorted_erdos_renyi_iterator& o) const {
+ return src == o.src && tgt_index == o.tgt_index;
}
- bool operator==(const sorted_erdos_renyi_iterator& other) const
- { return src == other.src && tgt == other.tgt; }
-
- bool operator!=(const sorted_erdos_renyi_iterator& other) const
- { return !(*this == other); }
+ void increment() {
+ next();
+ }
private:
void next()
{
- using std::sqrt;
- using std::floor;
-
// In order to get the edges from the generator in sorted order, one
// effective (but slow) procedure would be to use a
- // bernoulli_distribution for each legal (src, tgt) pair. Because of the
- // O(n^2) cost of that, a geometric distribution is used. The geometric
- // distribution tells how many times the bernoulli_distribution would
- // need to be run until it returns true. Thus, this distribution can be
- // used to step through the edges which are actually present. Everything
- // beyond "tgt += increment" is done to effectively convert linear
- // indexing (the partial sums of the geometric distribution output) into
- // graph edges.
- assert (src != (std::numeric_limits<vertices_size_type>::max)());
- vertices_size_type increment = rand_vertex(*gen);
- tgt += increment;
- if (is_undirected) {
- // Update src and tgt based on position of tgt
- // Basically, we want the greatest src_increment such that (in \bbQ):
- // src_increment * (src + allow_self_loops + src_increment - 1/2) <= tgt
- // The result of the LHS of this, evaluated with the computed
- // src_increment, is then subtracted from tgt
- double src_minus_half = (src + allow_self_loops) - 0.5;
- double disc = src_minus_half * src_minus_half + 2 * tgt;
- double src_increment_fp = floor(sqrt(disc) - src_minus_half);
- vertices_size_type src_increment = vertices_size_type(src_increment_fp);
- if (src + src_increment >= n) {
- src = n;
+ // bernoulli_distribution for each legal (src, tgt_index) pair. Because of
+ // the O(|V|^2) cost of that, a geometric distribution is used. The
+ // geometric distribution tells how many times the
+ // bernoulli_distribution would need to be run until it returns true.
+ // Thus, this distribution can be used to step through the edges
+ // which are actually present.
+ assert (src != (std::numeric_limits<vertices_size_type>::max)() &&
+ src != n);
+ while (src != n) {
+ vertices_size_type increment = rand_vertex(*gen);
+ size_t tgt_index_limit =
+ (is_undirected ? src + 1 : n) +
+ (allow_self_loops ? 0 : -1);
+ if (tgt_index + increment >= tgt_index_limit) {
+ // Overflowed this source; go to the next one and try again.
+ ++src;
+ // This bias is because the geometric distribution always returns
+ // values >=1, and we want to allow 0 as a valid target.
+ tgt_index = vertices_size_type(-1);
+ continue;
} else {
- tgt -= (src + allow_self_loops) * src_increment +
- src_increment * (src_increment - 1) / 2;
- src += src_increment;
+ tgt_index += increment;
+ current.first = src;
+ current.second =
+ tgt_index +
+ (!allow_self_loops && !is_undirected && tgt_index >= src ? 1 : 0);
+ break;
}
- } else {
- // Number of out edge positions possible from each vertex in this graph
- vertices_size_type possible_out_edges = n - (allow_self_loops ? 0 : 1);
- src += (std::min)(n - src, tgt / possible_out_edges);
- tgt %= possible_out_edges;
}
- // Set end of graph code so (src, tgt) will be the same as for the end
- // sorted_erdos_renyi_iterator
- if (src >= n) {src = (std::numeric_limits<vertices_size_type>::max)(); tgt = 0;}
- // Copy (src, tgt) into current
- current.first = src;
- current.second = tgt;
- // Adjust for (src, src) edge being forbidden
- if (!allow_self_loops && tgt >= src) ++current.second;
+ if (src == n) src = (std::numeric_limits<vertices_size_type>::max)();
}
shared_ptr<uniform_01<RandomGenerator> > gen;
geometric_distribution<vertices_size_type> rand_vertex;
vertices_size_type n;
bool allow_self_loops;
- vertices_size_type src, tgt;
- value_type current;
+ vertices_size_type src, tgt_index;
+ std::pair<vertices_size_type, vertices_size_type> current;
double prob;
};