boost/graph/plod_generator.hpp
// Copyright 2004-2006 The Trustees of Indiana University. // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // Authors: Douglas Gregor // Andrew Lumsdaine #ifndef BOOST_GRAPH_PLOD_GENERATOR_HPP #define BOOST_GRAPH_PLOD_GENERATOR_HPP #include <iterator> #include <utility> #include <boost/random/uniform_int.hpp> #include <boost/shared_ptr.hpp> #include <boost/graph/graph_traits.hpp> #include <vector> #include <map> #include <boost/config/no_tr1/cmath.hpp> #include <boost/mpl/if.hpp> namespace boost { template<typename RandomGenerator> class out_directed_plod_iterator { public: typedef std::forward_iterator_tag iterator_category; typedef std::pair<std::size_t, std::size_t> value_type; typedef const value_type& reference; typedef const value_type* pointer; typedef std::ptrdiff_t difference_type; out_directed_plod_iterator() : gen(0), at_end(true) { } out_directed_plod_iterator(RandomGenerator& gen, std::size_t n, double alpha, double beta, bool allow_self_loops) : gen(&gen), n(n), alpha(alpha), beta(beta), allow_self_loops(allow_self_loops), at_end(false), degree(0), current(0, 0) { using std::pow; uniform_int<std::size_t> x(0, n-1); std::size_t xv = x(gen); degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha))); } reference operator*() const { return current; } pointer operator->() const { return ¤t; } out_directed_plod_iterator& operator++() { using std::pow; uniform_int<std::size_t> x(0, n-1); // Continue stepping through source nodes until the // (out)degree is > 0 while (degree == 0) { // Step to the next source node. If we've gone past the // number of nodes we're responsible for, we're done. if (++current.first >= n) { at_end = true; return *this; } std::size_t xv = x(*gen); degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha))); } do { current.second = x(*gen); } while (current.first == current.second && !allow_self_loops); --degree; return *this; } out_directed_plod_iterator operator++(int) { out_directed_plod_iterator temp(*this); ++(*this); return temp; } bool operator==(const out_directed_plod_iterator& other) const { return at_end == other.at_end; } bool operator!=(const out_directed_plod_iterator& other) const { return !(*this == other); } private: RandomGenerator* gen; std::size_t n; double alpha; double beta; bool allow_self_loops; bool at_end; std::size_t degree; value_type current; }; template<typename RandomGenerator> class undirected_plod_iterator { typedef std::vector<std::pair<std::size_t, std::size_t> > out_degrees_t; public: typedef std::input_iterator_tag iterator_category; typedef std::pair<std::size_t, std::size_t> value_type; typedef const value_type& reference; typedef const value_type* pointer; typedef std::ptrdiff_t difference_type; undirected_plod_iterator() : gen(0), out_degrees(), degrees_left(0), allow_self_loops(false) { } undirected_plod_iterator(RandomGenerator& gen, std::size_t n, double alpha, double beta, bool allow_self_loops = false) : gen(&gen), n(n), out_degrees(new out_degrees_t), degrees_left(0), allow_self_loops(allow_self_loops) { using std::pow; uniform_int<std::size_t> x(0, n-1); for (std::size_t i = 0; i != n; ++i) { std::size_t xv = x(gen); std::size_t degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha))); if (degree == 0) degree = 1; else if (degree >= n) degree = n-1; out_degrees->push_back(std::make_pair(i, degree)); degrees_left += degree; } next(); } reference operator*() const { return current; } pointer operator->() const { return ¤t; } undirected_plod_iterator& operator++() { next(); return *this; } undirected_plod_iterator operator++(int) { undirected_plod_iterator temp(*this); ++(*this); return temp; } bool operator==(const undirected_plod_iterator& other) const { return degrees_left == other.degrees_left; } bool operator!=(const undirected_plod_iterator& other) const { return !(*this == other); } private: void next() { std::size_t source, target; while (true) { /* We may get to the point where we can't actually find any new edges, so we just add some random edge and set the degrees left = 0 to signal termination. */ if (out_degrees->size() < 2) { uniform_int<std::size_t> x(0, n-1); current.first = x(*gen); do { current.second = x(*gen); } while (current.first == current.second && !allow_self_loops); degrees_left = 0; out_degrees->clear(); return; } uniform_int<std::size_t> x(0, out_degrees->size()-1); // Select source vertex source = x(*gen); if ((*out_degrees)[source].second == 0) { (*out_degrees)[source] = out_degrees->back(); out_degrees->pop_back(); continue; } // Select target vertex target = x(*gen); if ((*out_degrees)[target].second == 0) { (*out_degrees)[target] = out_degrees->back(); out_degrees->pop_back(); continue; } else if (source != target || (allow_self_loops && (*out_degrees)[source].second > 2)) { break; } } // Update degree counts --(*out_degrees)[source].second; --degrees_left; --(*out_degrees)[target].second; --degrees_left; current.first = (*out_degrees)[source].first; current.second = (*out_degrees)[target].first; } RandomGenerator* gen; std::size_t n; shared_ptr<out_degrees_t> out_degrees; std::size_t degrees_left; bool allow_self_loops; value_type current; }; template<typename RandomGenerator, typename Graph> class plod_iterator : public mpl::if_<is_convertible< typename graph_traits<Graph>::directed_category, directed_tag>, out_directed_plod_iterator<RandomGenerator>, undirected_plod_iterator<RandomGenerator> >::type { typedef typename mpl::if_< is_convertible< typename graph_traits<Graph>::directed_category, directed_tag>, out_directed_plod_iterator<RandomGenerator>, undirected_plod_iterator<RandomGenerator> >::type inherited; public: plod_iterator() : inherited() { } plod_iterator(RandomGenerator& gen, std::size_t n, double alpha, double beta, bool allow_self_loops = false) : inherited(gen, n, alpha, beta, allow_self_loops) { } }; } // end namespace boost #endif // BOOST_GRAPH_PLOD_GENERATOR_HPP