// 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 |