ceph/src/boost/boost/graph/small_world_generator.hpp

   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
  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, 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
  47     reference operator*() const { return current; }
  48     pointer operator->() const { return &current; }
  49
  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
  85     small_world_iterator operator++(int)
  86     {
  87         small_world_iterator temp(*this);
  88         ++(*this);
  89         return temp;
  90     }
  91
  92     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
 103     bool operator!=(const small_world_iterator& other) const
 104     {
 105         return !(*this == other);
 106     }
 107
 108 private:
 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