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