boost/graph/erdos_renyi_generator.hpp

0001 // Copyright 2004, 2005 The Trustees of Indiana University.
0002
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Jeremiah Willcock
0008 //           Douglas Gregor
0009 //           Andrew Lumsdaine
0010 #ifndef BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
0011 #define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
0012
0013 #include <boost/assert.hpp>
0014 #include <iterator>
0015 #include <utility>
0016 #include <boost/shared_ptr.hpp>
0017 #include <boost/random/uniform_int.hpp>
0018 #include <boost/graph/graph_traits.hpp>
0019 #include <boost/random/geometric_distribution.hpp>
0020 #include <boost/type_traits/is_base_of.hpp>
0021 #include <boost/type_traits/is_same.hpp>
0022 #include <boost/config/no_tr1/cmath.hpp>
0023 #include <boost/iterator/iterator_facade.hpp>
0024
0025 namespace boost
0026 {
0027
0028 template < typename RandomGenerator, typename Graph >
0029 class erdos_renyi_iterator
0030 : public iterator_facade< erdos_renyi_iterator< RandomGenerator, Graph >,
0031       std::pair< typename graph_traits< Graph >::vertices_size_type,
0032           typename graph_traits< Graph >::vertices_size_type >,
0033       std::input_iterator_tag,
0034       const std::pair< typename graph_traits< Graph >::vertices_size_type,
0035           typename graph_traits< Graph >::vertices_size_type >& >
0036 {
0037     typedef typename graph_traits< Graph >::directed_category directed_category;
0038     typedef
0039         typename graph_traits< Graph >::vertices_size_type vertices_size_type;
0040     typedef typename graph_traits< Graph >::edges_size_type edges_size_type;
0041
0042     BOOST_STATIC_CONSTANT(bool,
0043         is_undirected
0044         = (is_base_of< undirected_tag, directed_category >::value));
0045
0046 public:
0047     erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
0048     erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
0049         double fraction = 0.0, bool allow_self_loops = false)
0050     : gen(&gen)
0051     , n(n)
0052     , edges(edges_size_type(fraction * n * n))
0053     , allow_self_loops(allow_self_loops)
0054     {
0055         if (is_undirected)
0056             edges = edges / 2;
0057         next();
0058     }
0059
0060     erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
0061         edges_size_type m, bool allow_self_loops = false)
0062     : gen(&gen), n(n), edges(m), allow_self_loops(allow_self_loops)
0063     {
0064         next();
0065     }
0066
0067     const std::pair< vertices_size_type, vertices_size_type >&
0068     dereference() const
0069     {
0070         return current;
0071     }
0072
0073     void increment()
0074     {
0075         --edges;
0076         next();
0077     }
0078
0079     bool equal(const erdos_renyi_iterator& other) const
0080     {
0081         return edges == other.edges;
0082     }
0083
0084 private:
0085     void next()
0086     {
0087         uniform_int< vertices_size_type > rand_vertex(0, n - 1);
0088         current.first = rand_vertex(*gen);
0089         do
0090         {
0091             current.second = rand_vertex(*gen);
0092         } while (current.first == current.second && !allow_self_loops);
0093     }
0094
0095     RandomGenerator* gen;
0096     vertices_size_type n;
0097     edges_size_type edges;
0098     bool allow_self_loops;
0099     std::pair< vertices_size_type, vertices_size_type > current;
0100 };
0101
0102 template < typename RandomGenerator, typename Graph >
0103 class sorted_erdos_renyi_iterator
0104 : public iterator_facade< sorted_erdos_renyi_iterator< RandomGenerator, Graph >,
0105       std::pair< typename graph_traits< Graph >::vertices_size_type,
0106           typename graph_traits< Graph >::vertices_size_type >,
0107       std::input_iterator_tag,
0108       const std::pair< typename graph_traits< Graph >::vertices_size_type,
0109           typename graph_traits< Graph >::vertices_size_type >& >
0110 {
0111     typedef typename graph_traits< Graph >::directed_category directed_category;
0112     typedef
0113         typename graph_traits< Graph >::vertices_size_type vertices_size_type;
0114     typedef typename graph_traits< Graph >::edges_size_type edges_size_type;
0115
0116     BOOST_STATIC_CONSTANT(bool,
0117         is_undirected
0118         = (is_base_of< undirected_tag, directed_category >::value));
0119
0120 public:
0121     sorted_erdos_renyi_iterator()
0122     : gen()
0123     , rand_vertex(0.5)
0124     , n(0)
0125     , allow_self_loops(false)
0126     , src((std::numeric_limits< vertices_size_type >::max)())
0127     , tgt_index(vertices_size_type(-1))
0128     , prob(.5)
0129     {
0130     }
0131
0132     // NOTE: The default probability has been changed to be the same as that
0133     // used by the geometic distribution. It was previously 0.0, which would
0134     // cause an assertion.
0135     sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
0136         double prob = 0.5, bool loops = false)
0137     : gen()
0138     , rand_vertex(1. - prob)
0139     , n(n)
0140     , allow_self_loops(loops)
0141     , src(0)
0142     , tgt_index(vertices_size_type(-1))
0143     , prob(prob)
0144     {
0145         this->gen.reset(new uniform_01< RandomGenerator* >(&gen));
0146
0147         if (prob == 0.0)
0148         {
0149             src = (std::numeric_limits< vertices_size_type >::max)();
0150             return;
0151         }
0152         next();
0153     }
0154
0155     const std::pair< vertices_size_type, vertices_size_type >&
0156     dereference() const
0157     {
0158         return current;
0159     }
0160
0161     bool equal(const sorted_erdos_renyi_iterator& o) const
0162     {
0163         return src == o.src && tgt_index == o.tgt_index;
0164     }
0165
0166     void increment() { next(); }
0167
0168 private:
0169     void next()
0170     {
0171         // In order to get the edges from the generator in sorted order, one
0172         // effective (but slow) procedure would be to use a
0173         // bernoulli_distribution for each legal (src, tgt_index) pair.  Because
0174         // of the O(|V|^2) cost of that, a geometric distribution is used.  The
0175         // geometric distribution tells how many times the
0176         // bernoulli_distribution would need to be run until it returns true.
0177         // Thus, this distribution can be used to step through the edges
0178         // which are actually present.
0179         BOOST_ASSERT(src != (std::numeric_limits< vertices_size_type >::max)()
0180             && src != n);
0181         while (src != n)
0182         {
0183             vertices_size_type increment = rand_vertex(*gen);
0184             size_t tgt_index_limit
0185                 = (is_undirected ? src + 1 : n) + (allow_self_loops ? 0 : -1);
0186             if (tgt_index + increment >= tgt_index_limit)
0187             {
0188                 // Overflowed this source; go to the next one and try again.
0189                 ++src;
0190                 // This bias is because the geometric distribution always
0191                 // returns values >=1, and we want to allow 0 as a valid target.
0192                 tgt_index = vertices_size_type(-1);
0193                 continue;
0194             }
0195             else
0196             {
0197                 tgt_index += increment;
0198                 current.first = src;
0199                 current.second = tgt_index
0200                     + (!allow_self_loops && !is_undirected && tgt_index >= src
0201                             ? 1
0202                             : 0);
0203                 break;
0204             }
0205         }
0206         if (src == n)
0207             src = (std::numeric_limits< vertices_size_type >::max)();
0208     }
0209
0210     shared_ptr< uniform_01< RandomGenerator* > > gen;
0211     geometric_distribution< vertices_size_type > rand_vertex;
0212     vertices_size_type n;
0213     bool allow_self_loops;
0214     vertices_size_type src, tgt_index;
0215     std::pair< vertices_size_type, vertices_size_type > current;
0216     double prob;
0217 };
0218
0219 } // end namespace boost
0220
0221 #endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP