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