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 ¤t; }
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 ¤t; }
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