Boost C++ Libraries

boost/graph/erdos_renyi_generator.hpp

// Copyright 2004, 2005 The Trustees of Indiana University.

// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Jeremiah Willcock
//           Douglas Gregor
//           Andrew Lumsdaine
#ifndef BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
#define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP

#include <boost/assert.hpp>
#include <iterator>
#include <utility>
#include <boost/shared_ptr.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/random/geometric_distribution.hpp>
#include <boost/type_traits/is_base_of.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/config/no_tr1/cmath.hpp>
#include <boost/iterator/iterator_facade.hpp>

namespace boost {

  template<typename RandomGenerator, typename Graph>
  class erdos_renyi_iterator
    : public iterator_facade<
               erdos_renyi_iterator<RandomGenerator, Graph>,
               std::pair<typename graph_traits<Graph>::vertices_size_type,
                         typename graph_traits<Graph>::vertices_size_type>,
               std::input_iterator_tag,
               const 
                 std::pair<typename graph_traits<Graph>::vertices_size_type,
                           typename graph_traits<Graph>::vertices_size_type>&>
  {
    typedef typename graph_traits<Graph>::directed_category directed_category;
    typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
    typedef typename graph_traits<Graph>::edges_size_type edges_size_type;

    BOOST_STATIC_CONSTANT
      (bool,
       is_undirected = (is_base_of<undirected_tag, directed_category>::value));

  public:
    erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
    erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                         double fraction = 0.0, bool allow_self_loops = false)
      : gen(&gen), n(n), edges(edges_size_type(fraction * n * n)),
        allow_self_loops(allow_self_loops)
    {
      if (is_undirected) edges = edges / 2;
      next();
    }

    erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                         edges_size_type m, bool allow_self_loops = false)
      : gen(&gen), n(n), edges(m),
        allow_self_loops(allow_self_loops)
    {
      next();
    }

    const std::pair<vertices_size_type, vertices_size_type>&
    dereference() const { return current; }

    void increment() {
      --edges;
      next();
    }

    bool equal(const erdos_renyi_iterator& other) const
    { return edges == other.edges; }

  private:
    void next()
    {
      uniform_int<vertices_size_type> rand_vertex(0, n-1);
      current.first = rand_vertex(*gen);
      do {
        current.second = rand_vertex(*gen);
      } while (current.first == current.second && !allow_self_loops);
    }

    RandomGenerator* gen;
    vertices_size_type n;
    edges_size_type edges;
    bool allow_self_loops;
    std::pair<vertices_size_type, vertices_size_type> current;
  };

  template<typename RandomGenerator, typename Graph>
  class sorted_erdos_renyi_iterator
    : public iterator_facade<
               sorted_erdos_renyi_iterator<RandomGenerator, Graph>,
               std::pair<typename graph_traits<Graph>::vertices_size_type,
                         typename graph_traits<Graph>::vertices_size_type>,
               std::input_iterator_tag,
               const 
                 std::pair<typename graph_traits<Graph>::vertices_size_type,
                           typename graph_traits<Graph>::vertices_size_type>&>
  {
    typedef typename graph_traits<Graph>::directed_category directed_category;
    typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
    typedef typename graph_traits<Graph>::edges_size_type edges_size_type;

    BOOST_STATIC_CONSTANT
      (bool,
       is_undirected = (is_base_of<undirected_tag, directed_category>::value));

  public:
    sorted_erdos_renyi_iterator()
      : gen(), rand_vertex(0.5), n(0), allow_self_loops(false)
      , src((std::numeric_limits<vertices_size_type>::max)()),
        tgt_index(vertices_size_type(-1)), prob(.5)
    { }

    // NOTE: The default probability has been changed to be the same as that
    // used by the geometic distribution. It was previously 0.0, which would
    // cause an assertion.
    sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                                double prob = 0.5,
                                bool loops = false)
      : gen(), rand_vertex(1. - prob), n(n), allow_self_loops(loops), src(0)
      , tgt_index(vertices_size_type(-1)), prob(prob)
    {
      this->gen.reset(new uniform_01<RandomGenerator*>(&gen));

      if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
      next();
    }

    const std::pair<vertices_size_type, vertices_size_type>&
    dereference() const {
      return current;
    }

    bool equal(const sorted_erdos_renyi_iterator& o) const {
      return src == o.src && tgt_index == o.tgt_index;
    }

    void increment() {
      next();
    }

  private:
    void next()
    {
      // In order to get the edges from the generator in sorted order, one
      // effective (but slow) procedure would be to use a
      // bernoulli_distribution for each legal (src, tgt_index) pair.  Because of
      // the O(|V|^2) cost of that, a geometric distribution is used.  The
      // geometric distribution tells how many times the
      // bernoulli_distribution would need to be run until it returns true.
      // Thus, this distribution can be used to step through the edges
      // which are actually present.
      BOOST_ASSERT (src != (std::numeric_limits<vertices_size_type>::max)() &&
                    src != n);
      while (src != n) {
        vertices_size_type increment = rand_vertex(*gen);
        size_t tgt_index_limit =
                 (is_undirected ? src + 1 : n) +
                 (allow_self_loops ? 0 : -1);
        if (tgt_index + increment >= tgt_index_limit) {
          // Overflowed this source; go to the next one and try again.
          ++src;
          // This bias is because the geometric distribution always returns
          // values >=1, and we want to allow 0 as a valid target.
          tgt_index = vertices_size_type(-1);
          continue;
        } else {
          tgt_index += increment;
          current.first = src;
          current.second =
            tgt_index +
            (!allow_self_loops && !is_undirected && tgt_index >= src ? 1 : 0);
          break;
        }
      }
      if (src == n) src = (std::numeric_limits<vertices_size_type>::max)();
    }

    shared_ptr<uniform_01<RandomGenerator*> > gen;
    geometric_distribution<vertices_size_type> rand_vertex;
    vertices_size_type n;
    bool allow_self_loops;
    vertices_size_type src, tgt_index;
    std::pair<vertices_size_type, vertices_size_type> current;
    double prob;
  };

} // end namespace boost

#endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP