ceph/src/boost/boost/graph/plod_generator.hpp

   1 // Copyright 2004-2006 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_PLOD_GENERATOR_HPP
  10 #define BOOST_GRAPH_PLOD_GENERATOR_HPP
  11
  12 #include <iterator>
  13 #include <utility>
  14 #include <boost/random/uniform_int.hpp>
  15 #include <boost/shared_ptr.hpp>
  16 #include <boost/graph/graph_traits.hpp>
  17 #include <vector>
  18 #include <map>
  19 #include <boost/config/no_tr1/cmath.hpp>
  20 #include <boost/mpl/if.hpp>
  21
  22 namespace boost {
  23   template<typename RandomGenerator>
  24   class out_directed_plod_iterator
  25   {
  26   public:
  27     typedef std::forward_iterator_tag            iterator_category;
  28     typedef std::pair<std::size_t, std::size_t>  value_type;
  29     typedef const value_type&                    reference;
  30     typedef const value_type*                    pointer;
  31     typedef std::ptrdiff_t                       difference_type;
  32
  33     out_directed_plod_iterator() : gen(0), at_end(true) { }
  34
  35     out_directed_plod_iterator(RandomGenerator& gen, std::size_t n,
  36                                double alpha, double beta,
  37                                bool allow_self_loops)
  38       : gen(&gen), n(n), alpha(alpha), beta(beta),
  39         allow_self_loops(allow_self_loops), at_end(false), degree(0),
  40         current(0, 0)
  41     {
  42       using std::pow;
  43
  44       uniform_int<std::size_t> x(0, n-1);
  45       std::size_t xv = x(gen);
  46       degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
  47     }
  48
  49     reference operator*() const { return current; }
  50     pointer operator->() const { return &current; }
  51
  52     out_directed_plod_iterator& operator++()
  53     {
  54       using std::pow;
  55
  56       uniform_int<std::size_t> x(0, n-1);
  57
  58       // Continue stepping through source nodes until the
  59       // (out)degree is > 0
  60       while (degree == 0) {
  61         // Step to the next source node. If we've gone past the
  62         // number of nodes we're responsible for, we're done.
  63         if (++current.first >= n) {
  64           at_end = true;
  65           return *this;
  66         }
  67
  68         std::size_t xv = x(*gen);
  69         degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
  70       }
  71
  72       do {
  73         current.second = x(*gen);
  74       } while (current.first == current.second && !allow_self_loops);
  75       --degree;
  76
  77       return *this;
  78     }
  79
  80     out_directed_plod_iterator operator++(int)
  81     {
  82       out_directed_plod_iterator temp(*this);
  83       ++(*this);
  84       return temp;
  85     }
  86
  87     bool operator==(const out_directed_plod_iterator& other) const
  88     {
  89       return at_end == other.at_end;
  90     }
  91
  92     bool operator!=(const out_directed_plod_iterator& other) const
  93     {
  94       return !(*this == other);
  95     }
  96
  97   private:
  98     RandomGenerator* gen;
  99     std::size_t n;
 100     double alpha;
 101     double beta;
 102     bool allow_self_loops;
 103     bool at_end;
 104     std::size_t degree;
 105     value_type current;
 106   };
 107
 108   template<typename RandomGenerator>
 109   class undirected_plod_iterator
 110   {
 111     typedef std::vector<std::pair<std::size_t, std::size_t> > out_degrees_t;
 112
 113   public:
 114     typedef std::input_iterator_tag              iterator_category;
 115     typedef std::pair<std::size_t, std::size_t>  value_type;
 116     typedef const value_type&                    reference;
 117     typedef const value_type*                    pointer;
 118     typedef std::ptrdiff_t                       difference_type;
 119
 120     undirected_plod_iterator()
 121       : gen(0), out_degrees(), degrees_left(0), allow_self_loops(false) { }
 122
 123     undirected_plod_iterator(RandomGenerator& gen, std::size_t n,
 124                              double alpha, double beta,
 125                              bool allow_self_loops = false)
 126       : gen(&gen), n(n), out_degrees(new out_degrees_t),
 127         degrees_left(0), allow_self_loops(allow_self_loops)
 128     {
 129       using std::pow;
 130
 131       uniform_int<std::size_t> x(0, n-1);
 132       for (std::size_t i = 0; i != n; ++i) {
 133         std::size_t xv = x(gen);
 134         std::size_t degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
 135         if (degree == 0) degree = 1;
 136         else if (degree >= n) degree = n-1;
 137         out_degrees->push_back(std::make_pair(i, degree));
 138         degrees_left += degree;
 139       }
 140
 141       next();
 142     }
 143
 144     reference operator*() const { return current; }
 145     pointer operator->() const { return &current; }
 146
 147     undirected_plod_iterator& operator++()
 148     {
 149       next();
 150       return *this;
 151     }
 152
 153     undirected_plod_iterator operator++(int)
 154     {
 155       undirected_plod_iterator temp(*this);
 156       ++(*this);
 157       return temp;
 158     }
 159
 160     bool operator==(const undirected_plod_iterator& other) const
 161     {
 162       return degrees_left == other.degrees_left;
 163     }
 164
 165     bool operator!=(const undirected_plod_iterator& other) const
 166     { return !(*this == other); }
 167
 168   private:
 169     void next()
 170     {
 171       std::size_t source, target;
 172       while (true) {
 173         /* We may get to the point where we can't actually find any
 174            new edges, so we just add some random edge and set the
 175            degrees left = 0 to signal termination. */
 176         if (out_degrees->size() < 2) {
 177           uniform_int<std::size_t> x(0, n-1);
 178           current.first  = x(*gen);
 179           do {
 180             current.second = x(*gen);
 181           } while (current.first == current.second && !allow_self_loops);
 182           degrees_left = 0;
 183           out_degrees->clear();
 184           return;
 185         }
 186
 187         uniform_int<std::size_t> x(0, out_degrees->size()-1);
 188
 189         // Select source vertex
 190         source = x(*gen);
 191         if ((*out_degrees)[source].second == 0) {
 192           (*out_degrees)[source] = out_degrees->back();
 193           out_degrees->pop_back();
 194           continue;
 195         }
 196
 197         // Select target vertex
 198         target = x(*gen);
 199         if ((*out_degrees)[target].second == 0) {
 200           (*out_degrees)[target] = out_degrees->back();
 201           out_degrees->pop_back();
 202           continue;
 203         } else if (source != target
 204                    || (allow_self_loops && (*out_degrees)[source].second > 2)) {
 205           break;
 206         }
 207       }
 208
 209       // Update degree counts
 210       --(*out_degrees)[source].second;
 211       --degrees_left;
 212       --(*out_degrees)[target].second;
 213       --degrees_left;
 214       current.first  = (*out_degrees)[source].first;
 215       current.second = (*out_degrees)[target].first;
 216     }
 217
 218     RandomGenerator* gen;
 219     std::size_t n;
 220     shared_ptr<out_degrees_t> out_degrees;
 221     std::size_t degrees_left;
 222     bool allow_self_loops;
 223     value_type current;
 224   };
 225
 226
 227   template<typename RandomGenerator, typename Graph>
 228   class plod_iterator
 229     : public mpl::if_<is_convertible<
 230                         typename graph_traits<Graph>::directed_category,
 231                         directed_tag>,
 232                       out_directed_plod_iterator<RandomGenerator>,
 233                       undirected_plod_iterator<RandomGenerator> >::type
 234   {
 235     typedef typename mpl::if_<
 236                        is_convertible<
 237                          typename graph_traits<Graph>::directed_category,
 238                          directed_tag>,
 239                         out_directed_plod_iterator<RandomGenerator>,
 240                         undirected_plod_iterator<RandomGenerator> >::type
 241       inherited;
 242
 243   public:
 244     plod_iterator() : inherited() { }
 245
 246     plod_iterator(RandomGenerator& gen, std::size_t n,
 247                   double alpha, double beta, bool allow_self_loops = false)
 248       : inherited(gen, n, alpha, beta, allow_self_loops) { }
 249   };
 250
 251 } // end namespace boost
 252
 253 #endif // BOOST_GRAPH_PLOD_GENERATOR_HPP