epoc32/include/stdapis/boost/graph/erdos_renyi_generator.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     1 // Copyright 2004, 2005 The Trustees of Indiana University.
     2 
     3 // Distributed under the Boost Software License, Version 1.0.
     4 // (See accompanying file LICENSE_1_0.txt or copy at
     5 // http://www.boost.org/LICENSE_1_0.txt)
     6 
     7 //  Authors: Jeremiah Willcock
     8 //           Douglas Gregor
     9 //           Andrew Lumsdaine
    10 #ifndef BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
    11 #define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
    12 
    13 #include <cassert>
    14 #include <iterator>
    15 #include <utility>
    16 #include <boost/shared_ptr.hpp>
    17 #include <boost/random/uniform_int.hpp>
    18 #include <boost/graph/graph_traits.hpp>
    19 #include <boost/random/geometric_distribution.hpp>
    20 #include <boost/type_traits/is_base_and_derived.hpp>
    21 #include <boost/type_traits/is_same.hpp>
    22 #include <cmath>
    23 
    24 namespace boost {
    25 
    26   template<typename RandomGenerator, typename Graph>
    27   class erdos_renyi_iterator
    28   {
    29     typedef typename graph_traits<Graph>::directed_category directed_category;
    30     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
    31     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
    32 
    33     BOOST_STATIC_CONSTANT
    34       (bool,
    35        is_undirected = (is_base_and_derived<undirected_tag,
    36                                             directed_category>::value
    37                         || is_same<undirected_tag, directed_category>::value));
    38 
    39   public:
    40     typedef std::input_iterator_tag iterator_category;
    41     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
    42     typedef const value_type& reference;
    43     typedef const value_type* pointer;
    44     typedef void difference_type;
    45 
    46     erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
    47     erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 
    48                          double fraction = 0.0, bool allow_self_loops = false)
    49       : gen(&gen), n(n), edges(edges_size_type(fraction * n * n)),
    50         allow_self_loops(allow_self_loops)
    51     { 
    52       if (is_undirected) edges = edges / 2;
    53       next(); 
    54     }
    55 
    56     erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 
    57                          edges_size_type m, bool allow_self_loops = false)
    58       : gen(&gen), n(n), edges(m),
    59         allow_self_loops(allow_self_loops)
    60     { 
    61       next(); 
    62     }
    63 
    64     reference operator*() const { return current; }
    65     pointer operator->() const { return &current; }
    66     
    67     erdos_renyi_iterator& operator++()
    68     { 
    69       --edges;
    70       next();
    71       return *this;
    72     }
    73 
    74     erdos_renyi_iterator operator++(int)
    75     {
    76       erdos_renyi_iterator temp(*this);
    77       ++(*this);
    78       return temp;
    79     }
    80 
    81     bool operator==(const erdos_renyi_iterator& other) const
    82     { return edges == other.edges; }
    83 
    84     bool operator!=(const erdos_renyi_iterator& other) const
    85     { return !(*this == other); }
    86 
    87   private:
    88     void next()
    89     {
    90       uniform_int<vertices_size_type> rand_vertex(0, n-1);
    91       current.first = rand_vertex(*gen);
    92       do {
    93         current.second = rand_vertex(*gen);
    94       } while (current.first == current.second && !allow_self_loops);
    95     }
    96 
    97     RandomGenerator* gen;
    98     vertices_size_type n;
    99     edges_size_type edges;
   100     bool allow_self_loops;
   101     value_type current;
   102   };
   103 
   104   template<typename RandomGenerator, typename Graph>
   105   class sorted_erdos_renyi_iterator
   106   {
   107     typedef typename graph_traits<Graph>::directed_category directed_category;
   108     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
   109     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
   110 
   111     BOOST_STATIC_CONSTANT
   112       (bool,
   113        is_undirected = (is_base_and_derived<undirected_tag,
   114                                             directed_category>::value
   115                         || is_same<undirected_tag, directed_category>::value));
   116 
   117   public:
   118     typedef std::input_iterator_tag iterator_category;
   119     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
   120     typedef const value_type& reference;
   121     typedef const value_type* pointer;
   122     typedef void difference_type;
   123 
   124     sorted_erdos_renyi_iterator()
   125       : gen(), rand_vertex(0.5), n(0), allow_self_loops(false),
   126     src((std::numeric_limits<vertices_size_type>::max)()), tgt(0), prob(0) {}
   127     sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 
   128                     double prob = 0.0, 
   129                                 bool allow_self_loops = false)
   130       : gen(),
   131         // The "1.0 - prob" in the next line is to work around a Boost.Random
   132         // (and TR1) bug in the specification of geometric_distribution.  It
   133         // should be replaced by "prob" when the issue is fixed.
   134         rand_vertex(1.0 - prob),
   135     n(n), allow_self_loops(allow_self_loops), src(0), tgt(0), prob(prob)
   136     { 
   137       this->gen.reset(new uniform_01<RandomGenerator>(gen));
   138 
   139       if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
   140       next(); 
   141     }
   142 
   143     reference operator*() const { return current; }
   144     pointer operator->() const { return &current; }
   145     
   146     sorted_erdos_renyi_iterator& operator++()
   147     { 
   148       next();
   149       return *this;
   150     }
   151 
   152     sorted_erdos_renyi_iterator operator++(int)
   153     {
   154       sorted_erdos_renyi_iterator temp(*this);
   155       ++(*this);
   156       return temp;
   157     }
   158 
   159     bool operator==(const sorted_erdos_renyi_iterator& other) const
   160     { return src == other.src && tgt == other.tgt; }
   161 
   162     bool operator!=(const sorted_erdos_renyi_iterator& other) const
   163     { return !(*this == other); }
   164 
   165   private:
   166     void next()
   167     {
   168       using std::sqrt;
   169       using std::floor;
   170 
   171       // In order to get the edges from the generator in sorted order, one
   172       // effective (but slow) procedure would be to use a
   173       // bernoulli_distribution for each legal (src, tgt) pair.  Because of the
   174       // O(n^2) cost of that, a geometric distribution is used.  The geometric
   175       // distribution tells how many times the bernoulli_distribution would
   176       // need to be run until it returns true.  Thus, this distribution can be
   177       // used to step through the edges which are actually present.  Everything
   178       // beyond "tgt += increment" is done to effectively convert linear
   179       // indexing (the partial sums of the geometric distribution output) into
   180       // graph edges.
   181       assert (src != (std::numeric_limits<vertices_size_type>::max)());
   182       vertices_size_type increment = rand_vertex(*gen);
   183       tgt += increment;
   184       if (is_undirected) {
   185     // Update src and tgt based on position of tgt
   186     // Basically, we want the greatest src_increment such that (in \bbQ):
   187     // src_increment * (src + allow_self_loops + src_increment - 1/2) <= tgt
   188     // The result of the LHS of this, evaluated with the computed
   189     // src_increment, is then subtracted from tgt
   190     double src_minus_half = (src + allow_self_loops) - 0.5;
   191     double disc = src_minus_half * src_minus_half + 2 * tgt;
   192     double src_increment_fp = floor(sqrt(disc) - src_minus_half);
   193     vertices_size_type src_increment = vertices_size_type(src_increment_fp);
   194     if (src + src_increment >= n) {
   195       src = n;
   196     } else {
   197       tgt -= (src + allow_self_loops) * src_increment + 
   198          src_increment * (src_increment - 1) / 2;
   199       src += src_increment;
   200     }
   201       } else {
   202     // Number of out edge positions possible from each vertex in this graph
   203     vertices_size_type possible_out_edges = n - (allow_self_loops ? 0 : 1);
   204     src += (std::min)(n - src, tgt / possible_out_edges);
   205     tgt %= possible_out_edges;
   206       }
   207       // Set end of graph code so (src, tgt) will be the same as for the end
   208       // sorted_erdos_renyi_iterator
   209       if (src >= n) {src = (std::numeric_limits<vertices_size_type>::max)(); tgt = 0;}
   210       // Copy (src, tgt) into current
   211       current.first = src;
   212       current.second = tgt;
   213       // Adjust for (src, src) edge being forbidden
   214       if (!allow_self_loops && tgt >= src) ++current.second;
   215     }
   216 
   217     shared_ptr<uniform_01<RandomGenerator> > gen;
   218     geometric_distribution<vertices_size_type> rand_vertex;
   219     vertices_size_type n;
   220     bool allow_self_loops;
   221     vertices_size_type src, tgt;
   222     value_type current;
   223     double prob;
   224   };
   225 
   226 } // end namespace boost
   227 
   228 #endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP