Subject: [Boost-commit] svn:boost r54769 - trunk/boost/graph
From: asutton_at_[hidden]
Date: 2009-07-07 09:02:33
Author: asutton
Date: 2009-07-07 09:02:32 EDT (Tue, 07 Jul 2009)
New Revision: 54769
URL: http://svn.boost.org/trac/boost/changeset/54769
Log:
Changed the default probability to the sorted_erdos_renyi_generator to 0.5
in order to avoid assertion.
Fixed a couple of warnings in rmat and small_world generators.
Text files modified:
trunk/boost/graph/erdos_renyi_generator.hpp | 49 +++++++-------
trunk/boost/graph/rmat_graph_generator.hpp | 127 ++++++++++++++++++++-------------------
trunk/boost/graph/small_world_generator.hpp | 22 +++---
3 files changed, 100 insertions(+), 98 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-07 09:02:32 EDT (Tue, 07 Jul 2009)
@@ -44,28 +44,28 @@
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,
+ erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
double fraction = 0.0, bool allow_self_loops = false)
: gen(&gen), n(n), edges(edges_size_type(fraction * n * n)),
allow_self_loops(allow_self_loops)
- {
+ {
if (is_undirected) edges = edges / 2;
- next();
+ next();
}
- erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
+ erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
edges_size_type m, bool allow_self_loops = false)
: gen(&gen), n(n), edges(m),
allow_self_loops(allow_self_loops)
- {
- next();
+ {
+ next();
}
reference operator*() const { return current; }
pointer operator->() const { return ¤t; }
-
+
erdos_renyi_iterator& operator++()
- {
+ {
--edges;
next();
return *this;
@@ -122,29 +122,30 @@
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) {}
- sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
- double prob = 0.0,
- bool allow_self_loops = false)
- : gen(),
- // The "1.0 - prob" in the next line is to work around a Boost.Random
- // (and TR1) bug in the specification of geometric_distribution. It
- // should be replaced by "prob" when the issue is fixed.
- rand_vertex(1.0 - prob),
- n(n), allow_self_loops(allow_self_loops), src(0), tgt(0), prob(prob)
- {
+ : gen(), rand_vertex(0.5), n(0), allow_self_loops(false)
+ , src((std::numeric_limits<vertices_size_type>::max)()), tgt(0), prob(0)
+ { }
+
+ // NOTE: The default probability has been changed to be the same as that
+ // used by the geometic distribution. It was previously 0.0, which would
+ // cause an assertion.
+ 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)
+ {
this->gen.reset(new uniform_01<RandomGenerator>(gen));
if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
- next();
+ next();
}
reference operator*() const { return current; }
pointer operator->() const { return ¤t; }
-
+
sorted_erdos_renyi_iterator& operator++()
- {
+ {
next();
return *this;
}
@@ -194,7 +195,7 @@
if (src + src_increment >= n) {
src = n;
} else {
- tgt -= (src + allow_self_loops) * src_increment +
+ tgt -= (src + allow_self_loops) * src_increment +
src_increment * (src_increment - 1) / 2;
src += src_increment;
}
Modified: trunk/boost/graph/rmat_graph_generator.hpp
==============================================================================
--- trunk/boost/graph/rmat_graph_generator.hpp (original)
+++ trunk/boost/graph/rmat_graph_generator.hpp 2009-07-07 09:02:32 EDT (Tue, 07 Jul 2009)
@@ -47,7 +47,7 @@
{ }
template <typename T>
- bool operator()(const T& x, const T& y)
+ bool operator()(const T& x, const T& y)
{ return distrib(x) == id || distrib(y) == id; }
private:
@@ -58,16 +58,16 @@
template <typename RandomGenerator, typename T>
void
generate_permutation_vector(RandomGenerator& gen, std::vector<T>& vertexPermutation, T n)
-{
+{
using boost::uniform_int;
vertexPermutation.resize(n);
-
+
// Generate permutation map of vertex numbers
uniform_int<T> rand_vertex(0, n-1);
for (T i = 0; i < n; ++i)
vertexPermutation[i] = i;
-
+
// Can't use std::random_shuffle unless we create another (synchronized) PRNG
for (T i = 0; i < n; ++i)
std::swap(vertexPermutation[i], vertexPermutation[rand_vertex(gen)]);
@@ -75,14 +75,14 @@
template <typename RandomGenerator, typename T>
std::pair<T,T>
-generate_edge(shared_ptr<uniform_01<RandomGenerator> > prob, T n,
+generate_edge(shared_ptr<uniform_01<RandomGenerator> > prob, T n,
unsigned int SCALE, double a, double b, double c, double d)
{
T u = 0, v = 0;
T step = n/2;
for (unsigned int j = 0; j < SCALE; ++j) {
double p = (*prob)();
-
+
if (p < a)
;
else if (p >= a && p < a + b)
@@ -93,18 +93,18 @@
u += step;
v += step;
}
-
+
step /= 2;
// 0.2 and 0.9 are hardcoded in the reference SSCA implementation.
// The maximum change in any given value should be less than 10%
- a *= 0.9 + 0.2 * (*prob)();
- b *= 0.9 + 0.2 * (*prob)();
- c *= 0.9 + 0.2 * (*prob)();
- d *= 0.9 + 0.2 * (*prob)();
-
+ a *= 0.9 + 0.2 * (*prob)();
+ b *= 0.9 + 0.2 * (*prob)();
+ c *= 0.9 + 0.2 * (*prob)();
+ d *= 0.9 + 0.2 * (*prob)();
+
double S = a + b + c + d;
-
+
a /= S; b /= S; c /= S;
// d /= S;
// Ensure all values add up to 1, regardless of floating point errors
@@ -119,8 +119,8 @@
/*
Chakrabarti's R-MAT scale free generator.
- For all flavors of the R-MAT iterator a+b+c+d must equal 1 and for the
- unique_rmat_iterator 'm' << 'n^2'. If 'm' is too close to 'n^2' the
+ For all flavors of the R-MAT iterator a+b+c+d must equal 1 and for the
+ unique_rmat_iterator 'm' << 'n^2'. If 'm' is too close to 'n^2' the
generator may be unable to generate sufficient unique edges
To get a true scale free distribution {a, b, c, d : a > b, a > c, a > d}
@@ -145,19 +145,19 @@
: gen(), edge(0) { }
// Initialize for edge generation
- rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
+ rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
double d, bool permute_vertices = true)
- : gen(), n(n), a(a), b(b), c(c), d(d), edge(m),
- permute_vertices(permute_vertices),
+ : gen(), n(n), a(a), b(b), c(c), d(d), edge(m),
+ permute_vertices(permute_vertices),
SCALE(int_log2(n))
-
+
{
this->gen.reset(new uniform_01<RandomGenerator>(gen));
assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
- if (permute_vertices)
+ if (permute_vertices)
generate_permutation_vector(gen, vertexPermutation, n);
// TODO: Generate the entire adjacency matrix then "Clip and flip" if undirected graph
@@ -167,9 +167,9 @@
tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
if (permute_vertices)
- current = std::make_pair(vertexPermutation[u],
+ current = std::make_pair(vertexPermutation[u],
vertexPermutation[v]);
- else
+ else
current = std::make_pair(u, v);
--edge;
@@ -177,16 +177,16 @@
reference operator*() const { return current; }
pointer operator->() const { return ¤t; }
-
+
rmat_iterator& operator++()
{
vertices_size_type u, v;
tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
if (permute_vertices)
- current = std::make_pair(vertexPermutation[u],
+ current = std::make_pair(vertexPermutation[u],
vertexPermutation[v]);
- else
+ else
current = std::make_pair(u, v);
--edge;
@@ -223,15 +223,15 @@
std::vector<vertices_size_type> vertexPermutation;
value_type current;
};
-
+
// Sorted version for CSR
template <typename T>
struct sort_pair {
bool operator() (const std::pair<T,T>& x, const std::pair<T,T>& y)
- {
+ {
if (x.first == y.first)
return x.second > y.second;
- else
+ else
return x.first > y.first;
}
};
@@ -257,25 +257,25 @@
{ }
// Initialize for edge generation
- sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
+ sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
double d, bool permute_vertices = true,
EdgePredicate ep = keep_all_edges())
: gen(), permute_vertices(permute_vertices),
values(sort_pair<vertices_size_type>()), done(false)
-
+
{
assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
this->gen.reset(new uniform_01<RandomGenerator>(gen));
std::vector<vertices_size_type> vertexPermutation;
- if (permute_vertices)
+ if (permute_vertices)
generate_permutation_vector(gen, vertexPermutation, n);
-
+
// TODO: "Clip and flip" if undirected graph
int SCALE = int_log2(n);
-
+
for (edges_size_type i = 0; i < m; ++i) {
vertices_size_type u, v;
@@ -297,7 +297,7 @@
reference operator*() const { return current; }
pointer operator->() const { return ¤t; }
-
+
sorted_rmat_iterator& operator++()
{
if (!values.empty()) {
@@ -359,23 +359,23 @@
{ }
// Initialize for edge generation
- unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
+ unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
double d, bool permute_vertices = true,
EdgePredicate ep = keep_all_edges())
: gen(), done(false)
-
+
{
assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
this->gen.reset(new uniform_01<RandomGenerator>(gen));
std::vector<vertices_size_type> vertexPermutation;
- if (permute_vertices)
+ if (permute_vertices)
generate_permutation_vector(gen, vertexPermutation, n);
int SCALE = int_log2(n);
-
+
std::map<value_type, bool> edge_map;
edges_size_type edges = 0;
@@ -383,14 +383,14 @@
vertices_size_type u, v;
tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
- // Lowest vertex number always comes first
+ // Lowest vertex number always comes first
// (this means we don't have to worry about i->j and j->i being in the edge list)
if (u > v && is_same<directed_category, undirected_tag>::value)
std::swap(u, v);
if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
edge_map[std::make_pair(u, v)] = true;
-
+
if (permute_vertices) {
if (ep(vertexPermutation[u], vertexPermutation[v]))
values.push_back(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
@@ -404,20 +404,20 @@
} while (edges < m);
// NGE - Asking for more than n^2 edges will result in an infinite loop here
// Asking for a value too close to n^2 edges may as well
-
+
current = values.back();
values.pop_back();
}
reference operator*() const { return current; }
pointer operator->() const { return ¤t; }
-
+
unique_rmat_iterator& operator++()
{
if (!values.empty()) {
current = values.back();
values.pop_back();
- } else
+ } else
done = true;
return *this;
@@ -470,30 +470,30 @@
: gen(), values(sort_pair<vertices_size_type>()), done(true) { }
// Initialize for edge generation
- sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
- double d, bool bidirectional = false,
+ sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
+ double d, bool bidirectional = false,
bool permute_vertices = true,
EdgePredicate ep = keep_all_edges())
- : gen(), bidirectional(bidirectional),
+ : gen(), bidirectional(bidirectional),
values(sort_pair<vertices_size_type>()), done(false)
-
+
{
assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));
this->gen.reset(new uniform_01<RandomGenerator>(gen));
-
+
std::vector<vertices_size_type> vertexPermutation;
if (permute_vertices)
generate_permutation_vector(gen, vertexPermutation, n);
int SCALE = int_log2(n);
-
+
std::map<value_type, bool> edge_map;
-
+
edges_size_type edges = 0;
do {
-
+
vertices_size_type u, v;
tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
@@ -501,8 +501,8 @@
if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
edge_map[std::make_pair(u, v)] = true;
edge_map[std::make_pair(v, u)] = true;
-
- if (ep(u, v))
+
+ if (ep(u, v)) {
if (permute_vertices) {
values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
values.push(std::make_pair(vertexPermutation[v], vertexPermutation[u]));
@@ -510,15 +510,16 @@
values.push(std::make_pair(u, v));
values.push(std::make_pair(v, u));
}
+ }
++edges;
}
} else {
- // Lowest vertex number always comes first
+ // Lowest vertex number always comes first
// (this means we don't have to worry about i->j and j->i being in the edge list)
if (u > v && is_same<directed_category, undirected_tag>::value)
std::swap(u, v);
-
+
if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
edge_map[std::make_pair(u, v)] = true;
@@ -533,7 +534,7 @@
++edges;
}
}
-
+
} while (edges < m);
// NGE - Asking for more than n^2 edges will result in an infinite loop here
// Asking for a value too close to n^2 edges may as well
@@ -544,13 +545,13 @@
reference operator*() const { return current; }
pointer operator->() const { return ¤t; }
-
+
sorted_unique_rmat_iterator& operator++()
{
if (!values.empty()) {
current = values.top();
values.pop();
- } else
+ } else
done = true;
return *this;
@@ -578,7 +579,7 @@
bool bidirectional;
// Internal data structures
- std::priority_queue<value_type, std::vector<value_type>,
+ std::priority_queue<value_type, std::vector<value_type>,
sort_pair<vertices_size_type> > values;
value_type current;
bool done;
Modified: trunk/boost/graph/small_world_generator.hpp
==============================================================================
--- trunk/boost/graph/small_world_generator.hpp (original)
+++ trunk/boost/graph/small_world_generator.hpp 2009-07-07 09:02:32 EDT (Tue, 07 Jul 2009)
@@ -20,7 +20,7 @@
template<typename RandomGenerator, typename Graph>
class small_world_iterator
{
- typedef typename graph_traits<Graph>::vertices_size_type
+ typedef typename graph_traits<Graph>::vertices_size_type
vertices_size_type;
public:
@@ -31,20 +31,20 @@
typedef void difference_type;
small_world_iterator() : gen(0) {}
- small_world_iterator(RandomGenerator& gen, vertices_size_type n,
- vertices_size_type k, double prob = 0.0,
- bool allow_self_loops = false)
- : gen(&gen), n(n), k(k), prob(prob), source(0),
- target(allow_self_loops? 0 : 1),
- allow_self_loops(allow_self_loops),
+ small_world_iterator(RandomGenerator& gen, vertices_size_type n,
+ vertices_size_type k, double prob = 0.0,
+ bool allow_self_loops = false)
+ : gen(&gen), n(n), k(k), prob(prob), source(0),
+ target(allow_self_loops? 0 : 1),
+ allow_self_loops(allow_self_loops),
current(0, allow_self_loops? 0 : 1)
{ }
reference operator*() const { return current; }
pointer operator->() const { return ¤t; }
-
+
small_world_iterator& operator++()
- {
+ {
target = (target + 1) % n;
if (target == (source + k/2 + 1) % n) {
++source;
@@ -62,8 +62,8 @@
vertices_size_type upper = (source + k/2) % n;
do {
current.second = rand_vertex_gen(*gen);
- } while (current.second >= lower && current.second <= upper
- || (upper < lower
+ } while ((current.second >= lower && current.second <= upper)
+ || (upper < lower
&& (current.second >= lower || current.second <= upper)));
} else {
current.second = target;