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 | // 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 |
115 | |