[857] | 1 | // Copyright 2004 The Trustees of Indiana University.
|
---|
| 2 |
|
---|
| 3 | // Use, modification and distribution is subject to the Boost Software
|
---|
| 4 | // License, Version 1.0. (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 | // Assumes undirected
|
---|
| 20 | template<typename RandomGenerator, typename Graph>
|
---|
| 21 | class small_world_iterator
|
---|
| 22 | {
|
---|
| 23 | typedef typename graph_traits<Graph>::vertices_size_type
|
---|
| 24 | 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 |
|
---|
| 33 | small_world_iterator() : gen(0) {}
|
---|
| 34 | small_world_iterator(RandomGenerator& gen, vertices_size_type n,
|
---|
| 35 | vertices_size_type k, double prob = 0.0,
|
---|
| 36 | bool allow_self_loops = false)
|
---|
| 37 | : gen(&gen), n(n), k(k), prob(prob), source(0),
|
---|
| 38 | target(allow_self_loops? 0 : 1),
|
---|
| 39 | allow_self_loops(allow_self_loops),
|
---|
| 40 | current(0, allow_self_loops? 0 : 1)
|
---|
| 41 | { }
|
---|
| 42 |
|
---|
| 43 | reference operator*() const { return current; }
|
---|
| 44 | pointer operator->() const { return ¤t; }
|
---|
| 45 |
|
---|
| 46 | small_world_iterator& operator++()
|
---|
| 47 | {
|
---|
| 48 | target = (target + 1) % n;
|
---|
| 49 | if (target == (source + k/2 + 1) % n) {
|
---|
| 50 | ++source;
|
---|
| 51 | if (allow_self_loops) target = source;
|
---|
| 52 | else target = (source + 1) % n;
|
---|
| 53 | }
|
---|
| 54 | current.first = source;
|
---|
| 55 |
|
---|
| 56 | uniform_01<RandomGenerator, double> rand01(*gen);
|
---|
| 57 | uniform_int<vertices_size_type> rand_vertex_gen(0, n-1);
|
---|
| 58 | double x = rand01();
|
---|
| 59 | *gen = rand01.base(); // GRRRR
|
---|
| 60 | if (x < prob) {
|
---|
| 61 | vertices_size_type lower = (source + n - k/2) % n;
|
---|
| 62 | vertices_size_type upper = (source + k/2) % n;
|
---|
| 63 | do {
|
---|
| 64 | current.second = rand_vertex_gen(*gen);
|
---|
| 65 | } while (current.second >= lower && current.second <= upper
|
---|
| 66 | || (upper < lower
|
---|
| 67 | && (current.second >= lower || current.second <= upper)));
|
---|
| 68 | } else {
|
---|
| 69 | current.second = target;
|
---|
| 70 | }
|
---|
| 71 | return *this;
|
---|
| 72 | }
|
---|
| 73 |
|
---|
| 74 | small_world_iterator operator++(int)
|
---|
| 75 | {
|
---|
| 76 | small_world_iterator temp(*this);
|
---|
| 77 | ++(*this);
|
---|
| 78 | return temp;
|
---|
| 79 | }
|
---|
| 80 |
|
---|
| 81 | bool operator==(const small_world_iterator& other) const
|
---|
| 82 | {
|
---|
| 83 | if (!gen && other.gen) return other == *this;
|
---|
| 84 | else if (gen && !other.gen) return source == n;
|
---|
| 85 | else if (!gen && !other.gen) return true;
|
---|
| 86 | return source == other.source && target == other.target;
|
---|
| 87 | }
|
---|
| 88 |
|
---|
| 89 | bool operator!=(const small_world_iterator& other) const
|
---|
| 90 | { return !(*this == other); }
|
---|
| 91 |
|
---|
| 92 | private:
|
---|
| 93 | void next()
|
---|
| 94 | {
|
---|
| 95 | uniform_int<vertices_size_type> rand_vertex(0, n-1);
|
---|
| 96 | current.first = rand_vertex(*gen);
|
---|
| 97 | do {
|
---|
| 98 | current.second = rand_vertex(*gen);
|
---|
| 99 | } while (current.first == current.second && !allow_self_loops);
|
---|
| 100 | }
|
---|
| 101 |
|
---|
| 102 | RandomGenerator* gen;
|
---|
| 103 | vertices_size_type n;
|
---|
| 104 | vertices_size_type k;
|
---|
| 105 | double prob;
|
---|
| 106 | vertices_size_type source;
|
---|
| 107 | vertices_size_type target;
|
---|
| 108 | bool allow_self_loops;
|
---|
| 109 | value_type current;
|
---|
| 110 | };
|
---|
| 111 |
|
---|
| 112 | } // end namespace boost
|
---|
| 113 |
|
---|
| 114 | #endif // BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP
|
---|