]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |