1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
// Copyright 2004, 2005 The Trustees of Indiana University.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
// Authors: Jeremiah Willcock
// Douglas Gregor
// Andrew Lumsdaine
#ifndef BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
#define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
#include <boost/assert.hpp>
#include <iterator>
#include <utility>
#include <boost/shared_ptr.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/random/geometric_distribution.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;
typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
BOOST_STATIC_CONSTANT
(bool,
is_undirected = (is_base_of<undirected_tag, directed_category>::value));
public:
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)
: gen(&gen), n(n), edges(edges_size_type(fraction * n * n)),
allow_self_loops(allow_self_loops)
{
if (is_undirected) edges = edges / 2;
next();
}
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();
}
const std::pair<vertices_size_type, vertices_size_type>&
dereference() const { return current; }
void increment() {
--edges;
next();
}
bool equal(const erdos_renyi_iterator& other) const
{ return edges == other.edges; }
private:
void next()
{
uniform_int<vertices_size_type> rand_vertex(0, n-1);
current.first = rand_vertex(*gen);
do {
current.second = rand_vertex(*gen);
} while (current.first == current.second && !allow_self_loops);
}
RandomGenerator* gen;
vertices_size_type n;
edges_size_type edges;
bool allow_self_loops;
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;
typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
BOOST_STATIC_CONSTANT
(bool,
is_undirected = (is_base_of<undirected_tag, directed_category>::value));
public:
sorted_erdos_renyi_iterator()
: gen(), rand_vertex(0.5), n(0), allow_self_loops(false)
, 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
// 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(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));
if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
next();
}
const std::pair<vertices_size_type, vertices_size_type>&
dereference() const {
return current;
}
bool equal(const sorted_erdos_renyi_iterator& o) const {
return src == o.src && tgt_index == o.tgt_index;
}
void increment() {
next();
}
private:
void next()
{
// 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_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.
BOOST_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_index += increment;
current.first = src;
current.second =
tgt_index +
(!allow_self_loops && !is_undirected && tgt_index >= src ? 1 : 0);
break;
}
}
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_index;
std::pair<vertices_size_type, vertices_size_type> current;
double prob;
};
} // end namespace boost
#endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
|
