Erdos-Renyi (Uniform Random)

Generates random graphs following the Erdos-Renyi model G(n, p) or G(n, m).

Defined in: <boost/graph/erdos_renyi_generator.hpp>

Synopsis

template <typename RandomGenerator, typename Graph>
class erdos_renyi_iterator;

erdos_renyi_iterator();
erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, double fraction = 0.0, bool allow_self_loops = false);
erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, edges_size_type m, bool allow_self_loops = false);

erdos_renyi_iterator produces edges by selecting source and target vertices uniformly at random. It generates exactly m edges (or fraction * n * n edges, halved for undirected graphs). Edges are not sorted and parallel edges are possible. A default-constructed iterator serves as the past-the-end sentinel.

Parameters

Direction Parameter Description

Direction	Parameter	Description
IN	`RandomGenerator& gen`	A random number generator (e.g. `boost::minstd_rand`).
IN	`vertices_size_type n`	Number of vertices in the generated graph.
IN	`double fraction`	Fraction of the maximum possible edges to generate. Defaults to `0.0`.
IN	`edges_size_type m`	Exact number of edges to generate (alternative to `fraction`).
IN	`bool allow_self_loops`	When `true`, edges from a vertex to itself are permitted. Defaults to `false`.

RandomGenerator& gen

A random number generator (e.g. boost::minstd_rand).

vertices_size_type n

Number of vertices in the generated graph.

double fraction

Fraction of the maximum possible edges to generate. Defaults to 0.0.

edges_size_type m

Exact number of edges to generate (alternative to fraction).

bool allow_self_loops

When true, edges from a vertex to itself are permitted. Defaults to false.

The fraction and m constructors are ambiguous when passing an integer literal: erdos_renyi_iterator(gen, 100, 50) silently calls the fraction overload (converting 50 to double), not the edge count overload. Always cast explicitly when using the edge count constructor: erdos_renyi_iterator(gen, 100, edges_size_type(50)).

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/random/linear_congruential.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>

int main() {
    using namespace boost;
    using Graph = adjacency_list<>;
    using EdgeCount = graph_traits<Graph>::edges_size_type;
    using ERGen = erdos_renyi_iterator<minstd_rand, Graph>;

    minstd_rand gen(42);
    Graph g(ERGen(gen, 6, EdgeCount(8)), ERGen(), 6);

    std::cout << num_edges(g) << " edges\n";
    for (auto e : make_iterator_range(edges(g))) {
        std::cout << "  " << source(e, g) << " -> " << target(e, g) << "\n";
    }
}

8 edges
  0 -> 3
  0 -> 1
  1 -> 2
  2 -> 0
  3 -> 5
  3 -> 4
  4 -> 3
  5 -> 2

Variants

sorted_erdos_renyi_iterator

template <typename RandomGenerator, typename Graph>
class sorted_erdos_renyi_iterator;

sorted_erdos_renyi_iterator();
sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, double prob = 0.5, bool loops = false);

sorted_erdos_renyi_iterator produces edges in sorted order using a geometric distribution to skip non-present edges efficiently. Each possible edge is independently included with probability prob. This makes the output suitable for constructing a compressed_sparse_row_graph, which requires sorted edge input. No parallel edges are produced.

Parameter differences from erdos_renyi_iterator:

Direction Parameter Description

Direction	Parameter	Description
IN	`double prob`	Independent probability that any given edge exists. Defaults to `0.5` (not `0.0`). A value of `0.0` produces an empty graph.
IN	`bool loops`	When `true`, self-loops are permitted. Defaults to `false`.

double prob

Independent probability that any given edge exists. Defaults to 0.5 (not 0.0). A value of 0.0 produces an empty graph.

bool loops

When true, self-loops are permitted. Defaults to false.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/random/linear_congruential.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>

int main() {
    using namespace boost;
    using Graph = adjacency_list<>;
    using SERGen = sorted_erdos_renyi_iterator<minstd_rand, Graph>;

    minstd_rand gen(42);
    double prob = 0.3;
    Graph g(SERGen(gen, 6, prob), SERGen(), 6);

    std::cout << num_edges(g) << " edges\n";
    for (auto e : make_iterator_range(edges(g))) {
        std::cout << "  " << source(e, g) << " -> " << target(e, g) << "\n";
    }
}

9 edges
  0 -> 1
  0 -> 4
  0 -> 5
  1 -> 3
  2 -> 3
  3 -> 0
  3 -> 1
  4 -> 2
  4 -> 5

Edit this Page