source: NonGTP/Boost/boost/graph/small_world_generator.hpp @ 857

Revision 857, 3.5 KB checked in by igarcia, 19 years ago (diff)
Line 
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
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
Note: See TracBrowser for help on using the repository browser.