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 28 template < typename RandomGenerator, typename Graph > 29 class erdos_renyi_iterator 30 : public iterator_facade< 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 std::pair< typename graph_traits< Graph >::vertices_size_type, 35 typename graph_traits< Graph >::vertices_size_type >& > 36 { 37 typedef typename graph_traits< Graph >::directed_category directed_category; 38 typedef 39 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(bool, 43 is_undirected 44 = (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) 51 , n(n) 52 , edges(edges_size_type(fraction * n * n)) 53 , allow_self_loops(allow_self_loops) 54 { 55 if (is_undirected) 56 edges = edges / 2; 57 next(); 58 } 59 erdos_renyi_iterator(RandomGenerator & gen,vertices_size_type n,edges_size_type m,bool allow_self_loops=false)60 erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 61 edges_size_type m, bool allow_self_loops = false) 62 : gen(&gen), n(n), edges(m), allow_self_loops(allow_self_loops) 63 { 64 next(); 65 } 66 67 const std::pair< vertices_size_type, vertices_size_type >& dereference() const68 dereference() const 69 { 70 return current; 71 } 72 increment()73 void increment() 74 { 75 --edges; 76 next(); 77 } 78 equal(const erdos_renyi_iterator & other) const79 bool equal(const erdos_renyi_iterator& other) const 80 { 81 return edges == other.edges; 82 } 83 84 private: next()85 void next() 86 { 87 uniform_int< vertices_size_type > rand_vertex(0, n - 1); 88 current.first = rand_vertex(*gen); 89 do 90 { 91 current.second = rand_vertex(*gen); 92 } while (current.first == current.second && !allow_self_loops); 93 } 94 95 RandomGenerator* gen; 96 vertices_size_type n; 97 edges_size_type edges; 98 bool allow_self_loops; 99 std::pair< vertices_size_type, vertices_size_type > current; 100 }; 101 102 template < typename RandomGenerator, typename Graph > 103 class sorted_erdos_renyi_iterator 104 : public iterator_facade< sorted_erdos_renyi_iterator< RandomGenerator, Graph >, 105 std::pair< typename graph_traits< Graph >::vertices_size_type, 106 typename graph_traits< Graph >::vertices_size_type >, 107 std::input_iterator_tag, 108 const std::pair< typename graph_traits< Graph >::vertices_size_type, 109 typename graph_traits< Graph >::vertices_size_type >& > 110 { 111 typedef typename graph_traits< Graph >::directed_category directed_category; 112 typedef 113 typename graph_traits< Graph >::vertices_size_type vertices_size_type; 114 typedef typename graph_traits< Graph >::edges_size_type edges_size_type; 115 116 BOOST_STATIC_CONSTANT(bool, 117 is_undirected 118 = (is_base_of< undirected_tag, directed_category >::value)); 119 120 public: sorted_erdos_renyi_iterator()121 sorted_erdos_renyi_iterator() 122 : gen() 123 , rand_vertex(0.5) 124 , n(0) 125 , allow_self_loops(false) 126 , src((std::numeric_limits< vertices_size_type >::max)()) 127 , tgt_index(vertices_size_type(-1)) 128 , prob(.5) 129 { 130 } 131 132 // NOTE: The default probability has been changed to be the same as that 133 // used by the geometic distribution. It was previously 0.0, which would 134 // cause an assertion. sorted_erdos_renyi_iterator(RandomGenerator & gen,vertices_size_type n,double prob=0.5,bool loops=false)135 sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 136 double prob = 0.5, bool loops = false) 137 : gen() 138 , rand_vertex(1. - prob) 139 , n(n) 140 , allow_self_loops(loops) 141 , src(0) 142 , tgt_index(vertices_size_type(-1)) 143 , prob(prob) 144 { 145 this->gen.reset(new uniform_01< RandomGenerator* >(&gen)); 146 147 if (prob == 0.0) 148 { 149 src = (std::numeric_limits< vertices_size_type >::max)(); 150 return; 151 } 152 next(); 153 } 154 155 const std::pair< vertices_size_type, vertices_size_type >& dereference() const156 dereference() const 157 { 158 return current; 159 } 160 equal(const sorted_erdos_renyi_iterator & o) const161 bool equal(const sorted_erdos_renyi_iterator& o) const 162 { 163 return src == o.src && tgt_index == o.tgt_index; 164 } 165 increment()166 void increment() { next(); } 167 168 private: next()169 void next() 170 { 171 // In order to get the edges from the generator in sorted order, one 172 // effective (but slow) procedure would be to use a 173 // bernoulli_distribution for each legal (src, tgt_index) pair. Because 174 // of the O(|V|^2) cost of that, a geometric distribution is used. The 175 // geometric distribution tells how many times the 176 // bernoulli_distribution would need to be run until it returns true. 177 // Thus, this distribution can be used to step through the edges 178 // which are actually present. 179 BOOST_ASSERT(src != (std::numeric_limits< vertices_size_type >::max)() 180 && src != n); 181 while (src != n) 182 { 183 vertices_size_type increment = rand_vertex(*gen); 184 size_t tgt_index_limit 185 = (is_undirected ? src + 1 : n) + (allow_self_loops ? 0 : -1); 186 if (tgt_index + increment >= tgt_index_limit) 187 { 188 // Overflowed this source; go to the next one and try again. 189 ++src; 190 // This bias is because the geometric distribution always 191 // returns values >=1, and we want to allow 0 as a valid target. 192 tgt_index = vertices_size_type(-1); 193 continue; 194 } 195 else 196 { 197 tgt_index += increment; 198 current.first = src; 199 current.second = tgt_index 200 + (!allow_self_loops && !is_undirected && tgt_index >= src 201 ? 1 202 : 0); 203 break; 204 } 205 } 206 if (src == n) 207 src = (std::numeric_limits< vertices_size_type >::max)(); 208 } 209 210 shared_ptr< uniform_01< RandomGenerator* > > gen; 211 geometric_distribution< vertices_size_type > rand_vertex; 212 vertices_size_type n; 213 bool allow_self_loops; 214 vertices_size_type src, tgt_index; 215 std::pair< vertices_size_type, vertices_size_type > current; 216 double prob; 217 }; 218 219 } // end namespace boost 220 221 #endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP 222