1 // Copyright 2004 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: Douglas Gregor 8 // Andrew Lumsdaine 9 #ifndef BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP 10 #define BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP 11 12 #include <iterator> 13 #include <utility> 14 #include <boost/random/uniform_01.hpp> 15 #include <boost/random/uniform_int.hpp> 16 17 namespace boost 18 { 19 20 // Assumes undirected 21 template < typename RandomGenerator, typename Graph > class small_world_iterator 22 { 23 typedef 24 typename graph_traits< Graph >::vertices_size_type vertices_size_type; 25 26 public: 27 typedef std::input_iterator_tag iterator_category; 28 typedef std::pair< vertices_size_type, vertices_size_type > value_type; 29 typedef const value_type& reference; 30 typedef const value_type* pointer; 31 typedef void difference_type; 32 small_world_iterator()33 small_world_iterator() : gen(0) {} small_world_iterator(RandomGenerator & gen,vertices_size_type n,vertices_size_type k,double prob=0.0,bool allow_self_loops=false)34 small_world_iterator(RandomGenerator& gen, vertices_size_type n, 35 vertices_size_type k, double prob = 0.0, bool allow_self_loops = false) 36 : gen(&gen) 37 , n(n) 38 , k(k) 39 , prob(prob) 40 , source(0) 41 , target(allow_self_loops ? 0 : 1) 42 , allow_self_loops(allow_self_loops) 43 , current(0, allow_self_loops ? 0 : 1) 44 { 45 } 46 operator *() const47 reference operator*() const { return current; } operator ->() const48 pointer operator->() const { return ¤t; } 49 operator ++()50 small_world_iterator& operator++() 51 { 52 target = (target + 1) % n; 53 if (target == (source + k / 2 + 1) % n) 54 { 55 ++source; 56 if (allow_self_loops) 57 target = source; 58 else 59 target = (source + 1) % n; 60 } 61 current.first = source; 62 63 uniform_01< RandomGenerator, double > rand01(*gen); 64 uniform_int< vertices_size_type > rand_vertex_gen(0, n - 1); 65 double x = rand01(); 66 *gen = rand01.base(); // GRRRR 67 if (x < prob) 68 { 69 vertices_size_type lower = (source + n - k / 2) % n; 70 vertices_size_type upper = (source + k / 2) % n; 71 do 72 { 73 current.second = rand_vertex_gen(*gen); 74 } while ((current.second >= lower && current.second <= upper) 75 || (upper < lower 76 && (current.second >= lower || current.second <= upper))); 77 } 78 else 79 { 80 current.second = target; 81 } 82 return *this; 83 } 84 operator ++(int)85 small_world_iterator operator++(int) 86 { 87 small_world_iterator temp(*this); 88 ++(*this); 89 return temp; 90 } 91 operator ==(const small_world_iterator & other) const92 bool operator==(const small_world_iterator& other) const 93 { 94 if (!gen && other.gen) 95 return other == *this; 96 else if (gen && !other.gen) 97 return source == n; 98 else if (!gen && !other.gen) 99 return true; 100 return source == other.source && target == other.target; 101 } 102 operator !=(const small_world_iterator & other) const103 bool operator!=(const small_world_iterator& other) const 104 { 105 return !(*this == other); 106 } 107 108 private: next()109 void next() 110 { 111 uniform_int< vertices_size_type > rand_vertex(0, n - 1); 112 current.first = rand_vertex(*gen); 113 do 114 { 115 current.second = rand_vertex(*gen); 116 } while (current.first == current.second && !allow_self_loops); 117 } 118 119 RandomGenerator* gen; 120 vertices_size_type n; 121 vertices_size_type k; 122 double prob; 123 vertices_size_type source; 124 vertices_size_type target; 125 bool allow_self_loops; 126 value_type current; 127 }; 128 129 } // end namespace boost 130 131 #endif // BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP 132