Chris@16: // Copyright 2004, 2005 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: // (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Jeremiah Willcock
Chris@16: //           Douglas Gregor
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
Chris@16: #define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <iterator>
Chris@16: #include <utility>
Chris@16: #include <boost/shared_ptr.hpp>
Chris@16: #include <boost/random/uniform_int.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/random/geometric_distribution.hpp>
Chris@16: #include <boost/type_traits/is_base_of.hpp>
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: #include <boost/config/no_tr1/cmath.hpp>
Chris@16: #include <boost/iterator/iterator_facade.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   template<typename RandomGenerator, typename Graph>
Chris@16:   class erdos_renyi_iterator
Chris@16:     : public iterator_facade<
Chris@16:                erdos_renyi_iterator<RandomGenerator, Graph>,
Chris@16:                std::pair<typename graph_traits<Graph>::vertices_size_type,
Chris@16:                          typename graph_traits<Graph>::vertices_size_type>,
Chris@16:                std::input_iterator_tag,
Chris@16:                const 
Chris@16:                  std::pair<typename graph_traits<Graph>::vertices_size_type,
Chris@16:                            typename graph_traits<Graph>::vertices_size_type>&>
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16:     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT
Chris@16:       (bool,
Chris@16:        is_undirected = (is_base_of<undirected_tag, directed_category>::value));
Chris@16: 
Chris@16:   public:
Chris@16:     erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
Chris@16:     erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
Chris@16:                          double fraction = 0.0, bool allow_self_loops = false)
Chris@16:       : gen(&gen), n(n), edges(edges_size_type(fraction * n * n)),
Chris@16:         allow_self_loops(allow_self_loops)
Chris@16:     {
Chris@16:       if (is_undirected) edges = edges / 2;
Chris@16:       next();
Chris@16:     }
Chris@16: 
Chris@16:     erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
Chris@16:                          edges_size_type m, bool allow_self_loops = false)
Chris@16:       : gen(&gen), n(n), edges(m),
Chris@16:         allow_self_loops(allow_self_loops)
Chris@16:     {
Chris@16:       next();
Chris@16:     }
Chris@16: 
Chris@16:     const std::pair<vertices_size_type, vertices_size_type>&
Chris@16:     dereference() const { return current; }
Chris@16: 
Chris@16:     void increment() {
Chris@16:       --edges;
Chris@16:       next();
Chris@16:     }
Chris@16: 
Chris@16:     bool equal(const erdos_renyi_iterator& other) const
Chris@16:     { return edges == other.edges; }
Chris@16: 
Chris@16:   private:
Chris@16:     void next()
Chris@16:     {
Chris@16:       uniform_int<vertices_size_type> rand_vertex(0, n-1);
Chris@16:       current.first = rand_vertex(*gen);
Chris@16:       do {
Chris@16:         current.second = rand_vertex(*gen);
Chris@16:       } while (current.first == current.second && !allow_self_loops);
Chris@16:     }
Chris@16: 
Chris@16:     RandomGenerator* gen;
Chris@16:     vertices_size_type n;
Chris@16:     edges_size_type edges;
Chris@16:     bool allow_self_loops;
Chris@16:     std::pair<vertices_size_type, vertices_size_type> current;
Chris@16:   };
Chris@16: 
Chris@16:   template<typename RandomGenerator, typename Graph>
Chris@16:   class sorted_erdos_renyi_iterator
Chris@16:     : public iterator_facade<
Chris@16:                sorted_erdos_renyi_iterator<RandomGenerator, Graph>,
Chris@16:                std::pair<typename graph_traits<Graph>::vertices_size_type,
Chris@16:                          typename graph_traits<Graph>::vertices_size_type>,
Chris@16:                std::input_iterator_tag,
Chris@16:                const 
Chris@16:                  std::pair<typename graph_traits<Graph>::vertices_size_type,
Chris@16:                            typename graph_traits<Graph>::vertices_size_type>&>
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16:     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT
Chris@16:       (bool,
Chris@16:        is_undirected = (is_base_of<undirected_tag, directed_category>::value));
Chris@16: 
Chris@16:   public:
Chris@16:     sorted_erdos_renyi_iterator()
Chris@16:       : gen(), rand_vertex(0.5), n(0), allow_self_loops(false)
Chris@16:       , src((std::numeric_limits<vertices_size_type>::max)()),
Chris@16:         tgt_index(vertices_size_type(-1)), prob(.5)
Chris@16:     { }
Chris@16: 
Chris@16:     // NOTE: The default probability has been changed to be the same as that
Chris@16:     // used by the geometic distribution. It was previously 0.0, which would
Chris@16:     // cause an assertion.
Chris@16:     sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
Chris@16:                                 double prob = 0.5,
Chris@16:                                 bool loops = false)
Chris@16:       : gen(), rand_vertex(1. - prob), n(n), allow_self_loops(loops), src(0)
Chris@16:       , tgt_index(vertices_size_type(-1)), prob(prob)
Chris@16:     {
Chris@16:       this->gen.reset(new uniform_01<RandomGenerator*>(&gen));
Chris@16: 
Chris@16:       if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
Chris@16:       next();
Chris@16:     }
Chris@16: 
Chris@16:     const std::pair<vertices_size_type, vertices_size_type>&
Chris@16:     dereference() const {
Chris@16:       return current;
Chris@16:     }
Chris@16: 
Chris@16:     bool equal(const sorted_erdos_renyi_iterator& o) const {
Chris@16:       return src == o.src && tgt_index == o.tgt_index;
Chris@16:     }
Chris@16: 
Chris@16:     void increment() {
Chris@16:       next();
Chris@16:     }
Chris@16: 
Chris@16:   private:
Chris@16:     void next()
Chris@16:     {
Chris@16:       // In order to get the edges from the generator in sorted order, one
Chris@16:       // effective (but slow) procedure would be to use a
Chris@16:       // bernoulli_distribution for each legal (src, tgt_index) pair.  Because of
Chris@16:       // the O(|V|^2) cost of that, a geometric distribution is used.  The
Chris@16:       // geometric distribution tells how many times the
Chris@16:       // bernoulli_distribution would need to be run until it returns true.
Chris@16:       // Thus, this distribution can be used to step through the edges
Chris@16:       // which are actually present.
Chris@16:       BOOST_ASSERT (src != (std::numeric_limits<vertices_size_type>::max)() &&
Chris@16:                     src != n);
Chris@16:       while (src != n) {
Chris@16:         vertices_size_type increment = rand_vertex(*gen);
Chris@16:         size_t tgt_index_limit =
Chris@16:                  (is_undirected ? src + 1 : n) +
Chris@16:                  (allow_self_loops ? 0 : -1);
Chris@16:         if (tgt_index + increment >= tgt_index_limit) {
Chris@16:           // Overflowed this source; go to the next one and try again.
Chris@16:           ++src;
Chris@16:           // This bias is because the geometric distribution always returns
Chris@16:           // values >=1, and we want to allow 0 as a valid target.
Chris@16:           tgt_index = vertices_size_type(-1);
Chris@16:           continue;
Chris@16:         } else {
Chris@16:           tgt_index += increment;
Chris@16:           current.first = src;
Chris@16:           current.second =
Chris@16:             tgt_index +
Chris@16:             (!allow_self_loops && !is_undirected && tgt_index >= src ? 1 : 0);
Chris@16:           break;
Chris@16:         }
Chris@16:       }
Chris@16:       if (src == n) src = (std::numeric_limits<vertices_size_type>::max)();
Chris@16:     }
Chris@16: 
Chris@16:     shared_ptr<uniform_01<RandomGenerator*> > gen;
Chris@16:     geometric_distribution<vertices_size_type> rand_vertex;
Chris@16:     vertices_size_type n;
Chris@16:     bool allow_self_loops;
Chris@16:     vertices_size_type src, tgt_index;
Chris@16:     std::pair<vertices_size_type, vertices_size_type> current;
Chris@16:     double prob;
Chris@16:   };
Chris@16: 
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP