boost/graph/erdos_renyi_generator.hpp

   1 // Copyright 2004, 2005 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: Jeremiah Willcock
   8 //           Douglas Gregor
   9 //           Andrew Lumsdaine
  10 #ifndef BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
  11 #define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
  12
  13 #include <cassert>
  14 #include <iterator>
  15 #include <utility>
  16 #include <boost/shared_ptr.hpp>
  17 #include <boost/random/uniform_int.hpp>
  18 #include <boost/graph/graph_traits.hpp>
  19 #include <boost/random/geometric_distribution.hpp>
  20 #include <boost/type_traits/is_base_and_derived.hpp>
  21 #include <boost/type_traits/is_same.hpp>
  22 #include <boost/config/no_tr1/cmath.hpp>
  23
  24 namespace boost {
  25
  26   template<typename RandomGenerator, typename Graph>
  27   class erdos_renyi_iterator
  28   {
  29     typedef typename graph_traits<Graph>::directed_category directed_category;
  30     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
  31     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
  32
  33     BOOST_STATIC_CONSTANT
  34       (bool,
  35        is_undirected = (is_base_and_derived<undirected_tag,
  36                                             directed_category>::value
  37                         || is_same<undirected_tag, directed_category>::value));
  38
  39   public:
  40     typedef std::input_iterator_tag iterator_category;
  41     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
  42     typedef const value_type& reference;
  43     typedef const value_type* pointer;
  44     typedef void difference_type;
  45
  46     erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
  47     erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
  48                          double fraction = 0.0, bool allow_self_loops = false)
  49       : gen(&gen), n(n), edges(edges_size_type(fraction * n * n)),
  50         allow_self_loops(allow_self_loops)
  51     {
  52       if (is_undirected) edges = edges / 2;
  53       next();
  54     }
  55
  56     erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
  57                          edges_size_type m, bool allow_self_loops = false)
  58       : gen(&gen), n(n), edges(m),
  59         allow_self_loops(allow_self_loops)
  60     {
  61       next();
  62     }
  63
  64     reference operator*() const { return current; }
  65     pointer operator->() const { return &current; }
  66
  67     erdos_renyi_iterator& operator++()
  68     {
  69       --edges;
  70       next();
  71       return *this;
  72     }
  73
  74     erdos_renyi_iterator operator++(int)
  75     {
  76       erdos_renyi_iterator temp(*this);
  77       ++(*this);
  78       return temp;
  79     }
  80
  81     bool operator==(const erdos_renyi_iterator& other) const
  82     { return edges == other.edges; }
  83
  84     bool operator!=(const erdos_renyi_iterator& other) const
  85     { return !(*this == other); }
  86
  87   private:
  88     void next()
  89     {
  90       uniform_int<vertices_size_type> rand_vertex(0, n-1);
  91       current.first = rand_vertex(*gen);
  92       do {
  93         current.second = rand_vertex(*gen);
  94       } while (current.first == current.second && !allow_self_loops);
  95     }
  96
  97     RandomGenerator* gen;
  98     vertices_size_type n;
  99     edges_size_type edges;
 100     bool allow_self_loops;
 101     value_type current;
 102   };
 103
 104   template<typename RandomGenerator, typename Graph>
 105   class sorted_erdos_renyi_iterator
 106   {
 107     typedef typename graph_traits<Graph>::directed_category directed_category;
 108     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
 109     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
 110
 111     BOOST_STATIC_CONSTANT
 112       (bool,
 113        is_undirected = (is_base_and_derived<undirected_tag,
 114                                             directed_category>::value
 115                         || is_same<undirected_tag, directed_category>::value));
 116
 117   public:
 118     typedef std::input_iterator_tag iterator_category;
 119     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
 120     typedef const value_type& reference;
 121     typedef const value_type* pointer;
 122     typedef void difference_type;
 123
 124     sorted_erdos_renyi_iterator()
 125       : gen(), rand_vertex(0.5), n(0), allow_self_loops(false),
 126         src((std::numeric_limits<vertices_size_type>::max)()), tgt(0), prob(0) {}
 127     sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
 128                                 double prob = 0.0,
 129                                 bool allow_self_loops = false)
 130       : gen(),
 131         // The "1.0 - prob" in the next line is to work around a Boost.Random
 132         // (and TR1) bug in the specification of geometric_distribution.  It
 133         // should be replaced by "prob" when the issue is fixed.
 134         rand_vertex(1.0 - prob),
 135         n(n), allow_self_loops(allow_self_loops), src(0), tgt(0), prob(prob)
 136     {
 137       this->gen.reset(new uniform_01<RandomGenerator>(gen));
 138
 139       if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
 140       next();
 141     }
 142
 143     reference operator*() const { return current; }
 144     pointer operator->() const { return &current; }
 145
 146     sorted_erdos_renyi_iterator& operator++()
 147     {
 148       next();
 149       return *this;
 150     }
 151
 152     sorted_erdos_renyi_iterator operator++(int)
 153     {
 154       sorted_erdos_renyi_iterator temp(*this);
 155       ++(*this);
 156       return temp;
 157     }
 158
 159     bool operator==(const sorted_erdos_renyi_iterator& other) const
 160     { return src == other.src && tgt == other.tgt; }
 161
 162     bool operator!=(const sorted_erdos_renyi_iterator& other) const
 163     { return !(*this == other); }
 164
 165   private:
 166     void next()
 167     {
 168       using std::sqrt;
 169       using std::floor;
 170
 171       // In order to get the edges from the generator in sorted order, one
 172       // effective (but slow) procedure would be to use a
 173       // bernoulli_distribution for each legal (src, tgt) pair.  Because of the
 174       // O(n^2) cost of that, a geometric distribution is used.  The geometric
 175       // distribution tells how many times the bernoulli_distribution would
 176       // need to be run until it returns true.  Thus, this distribution can be
 177       // used to step through the edges which are actually present.  Everything
 178       // beyond "tgt += increment" is done to effectively convert linear
 179       // indexing (the partial sums of the geometric distribution output) into
 180       // graph edges.
 181       assert (src != (std::numeric_limits<vertices_size_type>::max)());
 182       vertices_size_type increment = rand_vertex(*gen);
 183       tgt += increment;
 184       if (is_undirected) {
 185         // Update src and tgt based on position of tgt
 186         // Basically, we want the greatest src_increment such that (in \bbQ):
 187         // src_increment * (src + allow_self_loops + src_increment - 1/2) <= tgt
 188         // The result of the LHS of this, evaluated with the computed
 189         // src_increment, is then subtracted from tgt
 190         double src_minus_half = (src + allow_self_loops) - 0.5;
 191         double disc = src_minus_half * src_minus_half + 2 * tgt;
 192         double src_increment_fp = floor(sqrt(disc) - src_minus_half);
 193         vertices_size_type src_increment = vertices_size_type(src_increment_fp);
 194         if (src + src_increment >= n) {
 195           src = n;
 196         } else {
 197           tgt -= (src + allow_self_loops) * src_increment +
 198                  src_increment * (src_increment - 1) / 2;
 199           src += src_increment;
 200         }
 201       } else {
 202         // Number of out edge positions possible from each vertex in this graph
 203         vertices_size_type possible_out_edges = n - (allow_self_loops ? 0 : 1);
 204         src += (std::min)(n - src, tgt / possible_out_edges);
 205         tgt %= possible_out_edges;
 206       }
 207       // Set end of graph code so (src, tgt) will be the same as for the end
 208       // sorted_erdos_renyi_iterator
 209       if (src >= n) {src = (std::numeric_limits<vertices_size_type>::max)(); tgt = 0;}
 210       // Copy (src, tgt) into current
 211       current.first = src;
 212       current.second = tgt;
 213       // Adjust for (src, src) edge being forbidden
 214       if (!allow_self_loops && tgt >= src) ++current.second;
 215     }
 216
 217     shared_ptr<uniform_01<RandomGenerator> > gen;
 218     geometric_distribution<vertices_size_type> rand_vertex;
 219     vertices_size_type n;
 220     bool allow_self_loops;
 221     vertices_size_type src, tgt;
 222     value_type current;
 223     double prob;
 224   };
 225
 226 } // end namespace boost
 227
 228 #endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP