]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |