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 | |
25 | namespace 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 | |