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
17namespace 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 &current; }
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

source code of boost/boost/graph/small_world_generator.hpp