• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 &current; }
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