Edit: /usr/include/boost/graph/erdos_renyi_generator.hpp (7257B)
// Copyright 2004, 2005 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: Jeremiah Willcock
// Douglas Gregor
// Andrew Lumsdaine
#ifndef BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
#define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
namespace boost
{
template < typename RandomGenerator, typename Graph >
class erdos_renyi_iterator
: public iterator_facade< erdos_renyi_iterator< RandomGenerator, Graph >,
std::pair< typename graph_traits< Graph >::vertices_size_type,
typename graph_traits< Graph >::vertices_size_type >,
std::input_iterator_tag,
const std::pair< typename graph_traits< Graph >::vertices_size_type,
typename graph_traits< Graph >::vertices_size_type >& >
{
typedef typename graph_traits< Graph >::directed_category directed_category;
typedef
typename graph_traits< Graph >::vertices_size_type vertices_size_type;
typedef typename graph_traits< Graph >::edges_size_type edges_size_type;
BOOST_STATIC_CONSTANT(bool,
is_undirected
= (is_base_of< undirected_tag, directed_category >::value));
public:
erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
double fraction = 0.0, bool allow_self_loops = false)
: gen(&gen)
, n(n)
, edges(edges_size_type(fraction * n * n))
, allow_self_loops(allow_self_loops)
{
if (is_undirected)
edges = edges / 2;
next();
}
erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
edges_size_type m, bool allow_self_loops = false)
: gen(&gen), n(n), edges(m), allow_self_loops(allow_self_loops)
{
next();
}
const std::pair< vertices_size_type, vertices_size_type >&
dereference() const
{
return current;
}
void increment()
{
--edges;
next();
}
bool equal(const erdos_renyi_iterator& other) const
{
return edges == other.edges;
}
private:
void next()
{
uniform_int< vertices_size_type > rand_vertex(0, n - 1);
current.first = rand_vertex(*gen);
do
{
current.second = rand_vertex(*gen);
} while (current.first == current.second && !allow_self_loops);
}
RandomGenerator* gen;
vertices_size_type n;
edges_size_type edges;
bool allow_self_loops;
std::pair< vertices_size_type, vertices_size_type > current;
};
template < typename RandomGenerator, typename Graph >
class sorted_erdos_renyi_iterator
: public iterator_facade< sorted_erdos_renyi_iterator< RandomGenerator, Graph >,
std::pair< typename graph_traits< Graph >::vertices_size_type,
typename graph_traits< Graph >::vertices_size_type >,
std::input_iterator_tag,
const std::pair< typename graph_traits< Graph >::vertices_size_type,
typename graph_traits< Graph >::vertices_size_type >& >
{
typedef typename graph_traits< Graph >::directed_category directed_category;
typedef
typename graph_traits< Graph >::vertices_size_type vertices_size_type;
typedef typename graph_traits< Graph >::edges_size_type edges_size_type;
BOOST_STATIC_CONSTANT(bool,
is_undirected
= (is_base_of< undirected_tag, directed_category >::value));
public:
sorted_erdos_renyi_iterator()
: gen()
, rand_vertex(0.5)
, n(0)
, allow_self_loops(false)
, src((std::numeric_limits< vertices_size_type >::max)())
, tgt_index(vertices_size_type(-1))
, prob(.5)
{
}
// NOTE: The default probability has been changed to be the same as that
// used by the geometic distribution. It was previously 0.0, which would
// cause an assertion.
sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
double prob = 0.5, bool loops = false)
: gen()
, rand_vertex(1. - prob)
, n(n)
, allow_self_loops(loops)
, src(0)
, tgt_index(vertices_size_type(-1))
, prob(prob)
{
this->gen.reset(new uniform_01< RandomGenerator* >(&gen));
if (prob == 0.0)
{
src = (std::numeric_limits< vertices_size_type >::max)();
return;
}
next();
}
const std::pair< vertices_size_type, vertices_size_type >&
dereference() const
{
return current;
}
bool equal(const sorted_erdos_renyi_iterator& o) const
{
return src == o.src && tgt_index == o.tgt_index;
}
void increment() { next(); }
private:
void next()
{
// In order to get the edges from the generator in sorted order, one
// effective (but slow) procedure would be to use a
// bernoulli_distribution for each legal (src, tgt_index) pair. Because
// of the O(|V|^2) cost of that, a geometric distribution is used. The
// geometric distribution tells how many times the
// bernoulli_distribution would need to be run until it returns true.
// Thus, this distribution can be used to step through the edges
// which are actually present.
BOOST_ASSERT(src != (std::numeric_limits< vertices_size_type >::max)()
&& src != n);
while (src != n)
{
vertices_size_type increment = rand_vertex(*gen);
size_t tgt_index_limit
= (is_undirected ? src + 1 : n) + (allow_self_loops ? 0 : -1);
if (tgt_index + increment >= tgt_index_limit)
{
// Overflowed this source; go to the next one and try again.
++src;
// This bias is because the geometric distribution always
// returns values >=1, and we want to allow 0 as a valid target.
tgt_index = vertices_size_type(-1);
continue;
}
else
{
tgt_index += increment;
current.first = src;
current.second = tgt_index
+ (!allow_self_loops && !is_undirected && tgt_index >= src
? 1
: 0);
break;
}
}
if (src == n)
src = (std::numeric_limits< vertices_size_type >::max)();
}
shared_ptr< uniform_01< RandomGenerator* > > gen;
geometric_distribution< vertices_size_type > rand_vertex;
vertices_size_type n;
bool allow_self_loops;
vertices_size_type src, tgt_index;
std::pair< vertices_size_type, vertices_size_type > current;
double prob;
};
} // end namespace boost
#endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP