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: erdos_renyi_iterator()47 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)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 erdos_renyi_iterator(RandomGenerator & gen,vertices_size_type n,edges_size_type m,bool allow_self_loops=false)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>& dereference() const66 dereference() const { return current; } 67 increment()68 void increment() { 69 --edges; 70 next(); 71 } 72 equal(const erdos_renyi_iterator & other) const73 bool equal(const erdos_renyi_iterator& other) const 74 { return edges == other.edges; } 75 76 private: next()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: sorted_erdos_renyi_iterator()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. sorted_erdos_renyi_iterator(RandomGenerator & gen,vertices_size_type n,double prob=0.5,bool loops=false)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>& dereference() const135 dereference() const { 136 return current; 137 } 138 equal(const sorted_erdos_renyi_iterator & o) const139 bool equal(const sorted_erdos_renyi_iterator& o) const { 140 return src == o.src && tgt_index == o.tgt_index; 141 } 142 increment()143 void increment() { 144 next(); 145 } 146 147 private: next()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