epoc32/include/stdapis/boost/graph/erdos_renyi_generator.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/erdos_renyi_generator.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,228 @@
     1.4 +// Copyright 2004, 2005 The Trustees of Indiana University.
     1.5 +
     1.6 +// Distributed under the Boost Software License, Version 1.0.
     1.7 +// (See accompanying file LICENSE_1_0.txt or copy at
     1.8 +// http://www.boost.org/LICENSE_1_0.txt)
     1.9 +
    1.10 +//  Authors: Jeremiah Willcock
    1.11 +//           Douglas Gregor
    1.12 +//           Andrew Lumsdaine
    1.13 +#ifndef BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
    1.14 +#define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
    1.15 +
    1.16 +#include <cassert>
    1.17 +#include <iterator>
    1.18 +#include <utility>
    1.19 +#include <boost/shared_ptr.hpp>
    1.20 +#include <boost/random/uniform_int.hpp>
    1.21 +#include <boost/graph/graph_traits.hpp>
    1.22 +#include <boost/random/geometric_distribution.hpp>
    1.23 +#include <boost/type_traits/is_base_and_derived.hpp>
    1.24 +#include <boost/type_traits/is_same.hpp>
    1.25 +#include <cmath>
    1.26 +
    1.27 +namespace boost {
    1.28 +
    1.29 +  template<typename RandomGenerator, typename Graph>
    1.30 +  class erdos_renyi_iterator
    1.31 +  {
    1.32 +    typedef typename graph_traits<Graph>::directed_category directed_category;
    1.33 +    typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
    1.34 +    typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
    1.35 +
    1.36 +    BOOST_STATIC_CONSTANT
    1.37 +      (bool,
    1.38 +       is_undirected = (is_base_and_derived<undirected_tag,
    1.39 +                                            directed_category>::value
    1.40 +                        || is_same<undirected_tag, directed_category>::value));
    1.41 +
    1.42 +  public:
    1.43 +    typedef std::input_iterator_tag iterator_category;
    1.44 +    typedef std::pair<vertices_size_type, vertices_size_type> value_type;
    1.45 +    typedef const value_type& reference;
    1.46 +    typedef const value_type* pointer;
    1.47 +    typedef void difference_type;
    1.48 +
    1.49 +    erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
    1.50 +    erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 
    1.51 +                         double fraction = 0.0, bool allow_self_loops = false)
    1.52 +      : gen(&gen), n(n), edges(edges_size_type(fraction * n * n)),
    1.53 +        allow_self_loops(allow_self_loops)
    1.54 +    { 
    1.55 +      if (is_undirected) edges = edges / 2;
    1.56 +      next(); 
    1.57 +    }
    1.58 +
    1.59 +    erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 
    1.60 +                         edges_size_type m, bool allow_self_loops = false)
    1.61 +      : gen(&gen), n(n), edges(m),
    1.62 +        allow_self_loops(allow_self_loops)
    1.63 +    { 
    1.64 +      next(); 
    1.65 +    }
    1.66 +
    1.67 +    reference operator*() const { return current; }
    1.68 +    pointer operator->() const { return &current; }
    1.69 +    
    1.70 +    erdos_renyi_iterator& operator++()
    1.71 +    { 
    1.72 +      --edges;
    1.73 +      next();
    1.74 +      return *this;
    1.75 +    }
    1.76 +
    1.77 +    erdos_renyi_iterator operator++(int)
    1.78 +    {
    1.79 +      erdos_renyi_iterator temp(*this);
    1.80 +      ++(*this);
    1.81 +      return temp;
    1.82 +    }
    1.83 +
    1.84 +    bool operator==(const erdos_renyi_iterator& other) const
    1.85 +    { return edges == other.edges; }
    1.86 +
    1.87 +    bool operator!=(const erdos_renyi_iterator& other) const
    1.88 +    { return !(*this == other); }
    1.89 +
    1.90 +  private:
    1.91 +    void next()
    1.92 +    {
    1.93 +      uniform_int<vertices_size_type> rand_vertex(0, n-1);
    1.94 +      current.first = rand_vertex(*gen);
    1.95 +      do {
    1.96 +        current.second = rand_vertex(*gen);
    1.97 +      } while (current.first == current.second && !allow_self_loops);
    1.98 +    }
    1.99 +
   1.100 +    RandomGenerator* gen;
   1.101 +    vertices_size_type n;
   1.102 +    edges_size_type edges;
   1.103 +    bool allow_self_loops;
   1.104 +    value_type current;
   1.105 +  };
   1.106 +
   1.107 +  template<typename RandomGenerator, typename Graph>
   1.108 +  class sorted_erdos_renyi_iterator
   1.109 +  {
   1.110 +    typedef typename graph_traits<Graph>::directed_category directed_category;
   1.111 +    typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
   1.112 +    typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
   1.113 +
   1.114 +    BOOST_STATIC_CONSTANT
   1.115 +      (bool,
   1.116 +       is_undirected = (is_base_and_derived<undirected_tag,
   1.117 +                                            directed_category>::value
   1.118 +                        || is_same<undirected_tag, directed_category>::value));
   1.119 +
   1.120 +  public:
   1.121 +    typedef std::input_iterator_tag iterator_category;
   1.122 +    typedef std::pair<vertices_size_type, vertices_size_type> value_type;
   1.123 +    typedef const value_type& reference;
   1.124 +    typedef const value_type* pointer;
   1.125 +    typedef void difference_type;
   1.126 +
   1.127 +    sorted_erdos_renyi_iterator()
   1.128 +      : gen(), rand_vertex(0.5), n(0), allow_self_loops(false),
   1.129 +    src((std::numeric_limits<vertices_size_type>::max)()), tgt(0), prob(0) {}
   1.130 +    sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 
   1.131 +                    double prob = 0.0, 
   1.132 +                                bool allow_self_loops = false)
   1.133 +      : gen(),
   1.134 +        // The "1.0 - prob" in the next line is to work around a Boost.Random
   1.135 +        // (and TR1) bug in the specification of geometric_distribution.  It
   1.136 +        // should be replaced by "prob" when the issue is fixed.
   1.137 +        rand_vertex(1.0 - prob),
   1.138 +    n(n), allow_self_loops(allow_self_loops), src(0), tgt(0), prob(prob)
   1.139 +    { 
   1.140 +      this->gen.reset(new uniform_01<RandomGenerator>(gen));
   1.141 +
   1.142 +      if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
   1.143 +      next(); 
   1.144 +    }
   1.145 +
   1.146 +    reference operator*() const { return current; }
   1.147 +    pointer operator->() const { return &current; }
   1.148 +    
   1.149 +    sorted_erdos_renyi_iterator& operator++()
   1.150 +    { 
   1.151 +      next();
   1.152 +      return *this;
   1.153 +    }
   1.154 +
   1.155 +    sorted_erdos_renyi_iterator operator++(int)
   1.156 +    {
   1.157 +      sorted_erdos_renyi_iterator temp(*this);
   1.158 +      ++(*this);
   1.159 +      return temp;
   1.160 +    }
   1.161 +
   1.162 +    bool operator==(const sorted_erdos_renyi_iterator& other) const
   1.163 +    { return src == other.src && tgt == other.tgt; }
   1.164 +
   1.165 +    bool operator!=(const sorted_erdos_renyi_iterator& other) const
   1.166 +    { return !(*this == other); }
   1.167 +
   1.168 +  private:
   1.169 +    void next()
   1.170 +    {
   1.171 +      using std::sqrt;
   1.172 +      using std::floor;
   1.173 +
   1.174 +      // In order to get the edges from the generator in sorted order, one
   1.175 +      // effective (but slow) procedure would be to use a
   1.176 +      // bernoulli_distribution for each legal (src, tgt) pair.  Because of the
   1.177 +      // O(n^2) cost of that, a geometric distribution is used.  The geometric
   1.178 +      // distribution tells how many times the bernoulli_distribution would
   1.179 +      // need to be run until it returns true.  Thus, this distribution can be
   1.180 +      // used to step through the edges which are actually present.  Everything
   1.181 +      // beyond "tgt += increment" is done to effectively convert linear
   1.182 +      // indexing (the partial sums of the geometric distribution output) into
   1.183 +      // graph edges.
   1.184 +      assert (src != (std::numeric_limits<vertices_size_type>::max)());
   1.185 +      vertices_size_type increment = rand_vertex(*gen);
   1.186 +      tgt += increment;
   1.187 +      if (is_undirected) {
   1.188 +    // Update src and tgt based on position of tgt
   1.189 +    // Basically, we want the greatest src_increment such that (in \bbQ):
   1.190 +    // src_increment * (src + allow_self_loops + src_increment - 1/2) <= tgt
   1.191 +    // The result of the LHS of this, evaluated with the computed
   1.192 +    // src_increment, is then subtracted from tgt
   1.193 +    double src_minus_half = (src + allow_self_loops) - 0.5;
   1.194 +    double disc = src_minus_half * src_minus_half + 2 * tgt;
   1.195 +    double src_increment_fp = floor(sqrt(disc) - src_minus_half);
   1.196 +    vertices_size_type src_increment = vertices_size_type(src_increment_fp);
   1.197 +    if (src + src_increment >= n) {
   1.198 +      src = n;
   1.199 +    } else {
   1.200 +      tgt -= (src + allow_self_loops) * src_increment + 
   1.201 +         src_increment * (src_increment - 1) / 2;
   1.202 +      src += src_increment;
   1.203 +    }
   1.204 +      } else {
   1.205 +    // Number of out edge positions possible from each vertex in this graph
   1.206 +    vertices_size_type possible_out_edges = n - (allow_self_loops ? 0 : 1);
   1.207 +    src += (std::min)(n - src, tgt / possible_out_edges);
   1.208 +    tgt %= possible_out_edges;
   1.209 +      }
   1.210 +      // Set end of graph code so (src, tgt) will be the same as for the end
   1.211 +      // sorted_erdos_renyi_iterator
   1.212 +      if (src >= n) {src = (std::numeric_limits<vertices_size_type>::max)(); tgt = 0;}
   1.213 +      // Copy (src, tgt) into current
   1.214 +      current.first = src;
   1.215 +      current.second = tgt;
   1.216 +      // Adjust for (src, src) edge being forbidden
   1.217 +      if (!allow_self_loops && tgt >= src) ++current.second;
   1.218 +    }
   1.219 +
   1.220 +    shared_ptr<uniform_01<RandomGenerator> > gen;
   1.221 +    geometric_distribution<vertices_size_type> rand_vertex;
   1.222 +    vertices_size_type n;
   1.223 +    bool allow_self_loops;
   1.224 +    vertices_size_type src, tgt;
   1.225 +    value_type current;
   1.226 +    double prob;
   1.227 +  };
   1.228 +
   1.229 +} // end namespace boost
   1.230 +
   1.231 +#endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP