1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/plod_generator.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,161 @@
1.4 +// Copyright 2004 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: Douglas Gregor
1.11 +// Andrew Lumsdaine
1.12 +#ifndef BOOST_GRAPH_PLOD_GENERATOR_HPP
1.13 +#define BOOST_GRAPH_PLOD_GENERATOR_HPP
1.14 +
1.15 +#include <iterator>
1.16 +#include <utility>
1.17 +#include <boost/random/uniform_int.hpp>
1.18 +#include <boost/shared_ptr.hpp>
1.19 +#include <boost/graph/graph_traits.hpp>
1.20 +#include <vector>
1.21 +#include <map>
1.22 +#include <cmath>
1.23 +
1.24 +namespace boost {
1.25 +
1.26 + template<typename RandomGenerator, typename Graph>
1.27 + class plod_iterator
1.28 + {
1.29 + typedef std::vector<std::pair<std::size_t, std::size_t> > out_degrees_t;
1.30 + typedef typename graph_traits<Graph>::directed_category directed_category;
1.31 +
1.32 + public:
1.33 + typedef std::input_iterator_tag iterator_category;
1.34 + typedef std::pair<std::size_t, std::size_t> value_type;
1.35 + typedef const value_type& reference;
1.36 + typedef const value_type* pointer;
1.37 + typedef void difference_type;
1.38 +
1.39 + plod_iterator()
1.40 + : gen(0), out_degrees(), degrees_left(0), allow_self_loops(false) { }
1.41 +
1.42 + plod_iterator(RandomGenerator& gen, std::size_t n,
1.43 + double alpha, double beta, bool allow_self_loops = false)
1.44 + : gen(&gen), n(n), out_degrees(new out_degrees_t),
1.45 + degrees_left(0), allow_self_loops(allow_self_loops)
1.46 + {
1.47 + using std::pow;
1.48 +
1.49 + uniform_int<std::size_t> x(0, n-1);
1.50 + for (std::size_t i = 0; i != n; ++i) {
1.51 + std::size_t xv = x(gen);
1.52 + std::size_t degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
1.53 + if (degree != 0) {
1.54 + out_degrees->push_back(std::make_pair(i, degree));
1.55 + }
1.56 + degrees_left += degree;
1.57 + }
1.58 +
1.59 + next(directed_category());
1.60 + }
1.61 +
1.62 + reference operator*() const { return current; }
1.63 + pointer operator->() const { return ¤t; }
1.64 +
1.65 + plod_iterator& operator++()
1.66 + {
1.67 + next(directed_category());
1.68 + return *this;
1.69 + }
1.70 +
1.71 + plod_iterator operator++(int)
1.72 + {
1.73 + plod_iterator temp(*this);
1.74 + ++(*this);
1.75 + return temp;
1.76 + }
1.77 +
1.78 + bool operator==(const plod_iterator& other) const
1.79 + {
1.80 + return degrees_left == other.degrees_left;
1.81 + }
1.82 +
1.83 + bool operator!=(const plod_iterator& other) const
1.84 + { return !(*this == other); }
1.85 +
1.86 + private:
1.87 + void next(directed_tag)
1.88 + {
1.89 + uniform_int<std::size_t> x(0, out_degrees->size()-1);
1.90 + std::size_t source;
1.91 + do {
1.92 + source = x(*gen);
1.93 + } while ((*out_degrees)[source].second == 0);
1.94 + current.first = (*out_degrees)[source].first;
1.95 + do {
1.96 + current.second = x(*gen);
1.97 + } while (current.first == current.second && !allow_self_loops);
1.98 + --degrees_left;
1.99 + if (--(*out_degrees)[source].second == 0) {
1.100 + (*out_degrees)[source] = out_degrees->back();
1.101 + out_degrees->pop_back();
1.102 + }
1.103 + }
1.104 +
1.105 + void next(undirected_tag)
1.106 + {
1.107 + std::size_t source, target;
1.108 + while (true) {
1.109 + /* We may get to the point where we can't actually find any
1.110 + new edges, so we just add some random edge and set the
1.111 + degrees left = 0 to signal termination. */
1.112 + if (out_degrees->size() < 2) {
1.113 + uniform_int<std::size_t> x(0, n);
1.114 + current.first = x(*gen);
1.115 + do {
1.116 + current.second = x(*gen);
1.117 + } while (current.first == current.second && !allow_self_loops);
1.118 + degrees_left = 0;
1.119 + out_degrees->clear();
1.120 + return;
1.121 + }
1.122 +
1.123 + uniform_int<std::size_t> x(0, out_degrees->size()-1);
1.124 +
1.125 + // Select source vertex
1.126 + source = x(*gen);
1.127 + if ((*out_degrees)[source].second == 0) {
1.128 + (*out_degrees)[source] = out_degrees->back();
1.129 + out_degrees->pop_back();
1.130 + continue;
1.131 + }
1.132 +
1.133 + // Select target vertex
1.134 + target = x(*gen);
1.135 + if ((*out_degrees)[target].second == 0) {
1.136 + (*out_degrees)[target] = out_degrees->back();
1.137 + out_degrees->pop_back();
1.138 + continue;
1.139 + } else if (source != target
1.140 + || (allow_self_loops && (*out_degrees)[source].second > 2)) {
1.141 + break;
1.142 + }
1.143 + }
1.144 +
1.145 + // Update degree counts
1.146 + --(*out_degrees)[source].second;
1.147 + --degrees_left;
1.148 + --(*out_degrees)[target].second;
1.149 + --degrees_left;
1.150 + current.first = (*out_degrees)[source].first;
1.151 + current.second = (*out_degrees)[target].first;
1.152 + }
1.153 +
1.154 + RandomGenerator* gen;
1.155 + std::size_t n;
1.156 + shared_ptr<out_degrees_t> out_degrees;
1.157 + std::size_t degrees_left;
1.158 + bool allow_self_loops;
1.159 + value_type current;
1.160 + };
1.161 +
1.162 +} // end namespace boost
1.163 +
1.164 +#endif // BOOST_GRAPH_PLOD_GENERATOR_HPP