1// Copyright 2004, 2005 The Trustees of Indiana University.
2
3// Distributed under the Boost Software License, Version 1.0.
4// (See accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7// Authors: Jeremiah Willcock
8// Douglas Gregor
9// Andrew Lumsdaine
10#ifndef BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
11#define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
12
13#include <boost/assert.hpp>
14#include <iterator>
15#include <utility>
16#include <boost/shared_ptr.hpp>
17#include <boost/random/uniform_int.hpp>
18#include <boost/graph/graph_traits.hpp>
19#include <boost/random/geometric_distribution.hpp>
20#include <boost/type_traits/is_base_of.hpp>
21#include <boost/type_traits/is_same.hpp>
22#include <boost/config/no_tr1/cmath.hpp>
23#include <boost/iterator/iterator_facade.hpp>
24
25namespace boost {
26
27 template<typename RandomGenerator, typename Graph>
28 class erdos_renyi_iterator
29 : public iterator_facade<
30 erdos_renyi_iterator<RandomGenerator, Graph>,
31 std::pair<typename graph_traits<Graph>::vertices_size_type,
32 typename graph_traits<Graph>::vertices_size_type>,
33 std::input_iterator_tag,
34 const
35 std::pair<typename graph_traits<Graph>::vertices_size_type,
36 typename graph_traits<Graph>::vertices_size_type>&>
37 {
38 typedef typename graph_traits<Graph>::directed_category directed_category;
39 typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
40 typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
41
42 BOOST_STATIC_CONSTANT
43 (bool,
44 is_undirected = (is_base_of<undirected_tag, directed_category>::value));
45
46 public:
47 erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
48 erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
49 double fraction = 0.0, bool allow_self_loops = false)
50 : gen(&gen), n(n), edges(edges_size_type(fraction * n * n)),
51 allow_self_loops(allow_self_loops)
52 {
53 if (is_undirected) edges = edges / 2;
54 next();
55 }
56
57 erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
58 edges_size_type m, bool allow_self_loops = false)
59 : gen(&gen), n(n), edges(m),
60 allow_self_loops(allow_self_loops)
61 {
62 next();
63 }
64
65 const std::pair<vertices_size_type, vertices_size_type>&
66 dereference() const { return current; }
67
68 void increment() {
69 --edges;
70 next();
71 }
72
73 bool equal(const erdos_renyi_iterator& other) const
74 { return edges == other.edges; }
75
76 private:
77 void next()
78 {
79 uniform_int<vertices_size_type> rand_vertex(0, n-1);
80 current.first = rand_vertex(*gen);
81 do {
82 current.second = rand_vertex(*gen);
83 } while (current.first == current.second && !allow_self_loops);
84 }
85
86 RandomGenerator* gen;
87 vertices_size_type n;
88 edges_size_type edges;
89 bool allow_self_loops;
90 std::pair<vertices_size_type, vertices_size_type> current;
91 };
92
93 template<typename RandomGenerator, typename Graph>
94 class sorted_erdos_renyi_iterator
95 : public iterator_facade<
96 sorted_erdos_renyi_iterator<RandomGenerator, Graph>,
97 std::pair<typename graph_traits<Graph>::vertices_size_type,
98 typename graph_traits<Graph>::vertices_size_type>,
99 std::input_iterator_tag,
100 const
101 std::pair<typename graph_traits<Graph>::vertices_size_type,
102 typename graph_traits<Graph>::vertices_size_type>&>
103 {
104 typedef typename graph_traits<Graph>::directed_category directed_category;
105 typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
106 typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
107
108 BOOST_STATIC_CONSTANT
109 (bool,
110 is_undirected = (is_base_of<undirected_tag, directed_category>::value));
111
112 public:
113 sorted_erdos_renyi_iterator()
114 : gen(), rand_vertex(0.5), n(0), allow_self_loops(false)
115 , src((std::numeric_limits<vertices_size_type>::max)()),
116 tgt_index(vertices_size_type(-1)), prob(.5)
117 { }
118
119 // NOTE: The default probability has been changed to be the same as that
120 // used by the geometic distribution. It was previously 0.0, which would
121 // cause an assertion.
122 sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
123 double prob = 0.5,
124 bool loops = false)
125 : gen(), rand_vertex(1. - prob), n(n), allow_self_loops(loops), src(0)
126 , tgt_index(vertices_size_type(-1)), prob(prob)
127 {
128 this->gen.reset(new uniform_01<RandomGenerator*>(&gen));
129
130 if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
131 next();
132 }
133
134 const std::pair<vertices_size_type, vertices_size_type>&
135 dereference() const {
136 return current;
137 }
138
139 bool equal(const sorted_erdos_renyi_iterator& o) const {
140 return src == o.src && tgt_index == o.tgt_index;
141 }
142
143 void increment() {
144 next();
145 }
146
147 private:
148 void next()
149 {
150 // In order to get the edges from the generator in sorted order, one
151 // effective (but slow) procedure would be to use a
152 // bernoulli_distribution for each legal (src, tgt_index) pair. Because of
153 // the O(|V|^2) cost of that, a geometric distribution is used. The
154 // geometric distribution tells how many times the
155 // bernoulli_distribution would need to be run until it returns true.
156 // Thus, this distribution can be used to step through the edges
157 // which are actually present.
158 BOOST_ASSERT (src != (std::numeric_limits<vertices_size_type>::max)() &&
159 src != n);
160 while (src != n) {
161 vertices_size_type increment = rand_vertex(*gen);
162 size_t tgt_index_limit =
163 (is_undirected ? src + 1 : n) +
164 (allow_self_loops ? 0 : -1);
165 if (tgt_index + increment >= tgt_index_limit) {
166 // Overflowed this source; go to the next one and try again.
167 ++src;
168 // This bias is because the geometric distribution always returns
169 // values >=1, and we want to allow 0 as a valid target.
170 tgt_index = vertices_size_type(-1);
171 continue;
172 } else {
173 tgt_index += increment;
174 current.first = src;
175 current.second =
176 tgt_index +
177 (!allow_self_loops && !is_undirected && tgt_index >= src ? 1 : 0);
178 break;
179 }
180 }
181 if (src == n) src = (std::numeric_limits<vertices_size_type>::max)();
182 }
183
184 shared_ptr<uniform_01<RandomGenerator*> > gen;
185 geometric_distribution<vertices_size_type> rand_vertex;
186 vertices_size_type n;
187 bool allow_self_loops;
188 vertices_size_type src, tgt_index;
189 std::pair<vertices_size_type, vertices_size_type> current;
190 double prob;
191 };
192
193} // end namespace boost
194
195#endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
196

source code of boost/boost/graph/erdos_renyi_generator.hpp