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