This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

R-MAT Generator (Input Iterator)

Generate scale-free graphs using the Recursive Matrix (R-MAT) model.

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

Synopsis

template <typename RandomGenerator, typename Graph>
class rmat_iterator;

rmat_iterator();
rmat_iterator(RandomGenerator& gen, vertices_size_type n, edges_size_type m, double a, double b, double c, double d, bool permute_vertices = true);

The R-MAT model generates graphs with a power-law degree distribution and community structure, similar to many real-world networks. The algorithm recursively partitions the adjacency matrix into four quadrants, choosing each quadrant with probabilities a, b, c, d. The sum a + b + c + d must equal 1. The number of vertices n must be a power of 2.

Typical parameters for a Graph500-style generator: a=0.57, b=0.19, c=0.19, d=0.05.

May produce parallel edges and self-loops.

Parameters

Direction Parameter Description

IN

RandomGenerator& gen

A random number generator.

IN

vertices_size_type n

Number of vertices. Must be a power of 2.

IN

edges_size_type m

Number of edges to generate.

IN

double a

Probability for quadrant (low, low). Typically ~0.57.

IN

double b

Probability for quadrant (low, high). Typically ~0.19.

IN

double c

Probability for quadrant (high, low). Typically ~0.19.

IN

double d

Probability for quadrant (high, high). Typically ~0.05.

IN

bool permute_vertices

If true, randomly permute vertex labels. Default: true.

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/rmat_graph_generator.hpp>
#include <boost/random/mersenne_twister.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 RGen = rmat_iterator<mt19937, Graph>;

    mt19937 gen(42);
    double a = 0.57, b = 0.19, c = 0.19, d = 0.05;
    Graph g(RGen(gen, 8, EdgeCount(10), a, b, c, d), RGen(), 8);

    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
  2 -> 3
  2 -> 2
  2 -> 7
  3 -> 2
  3 -> 0
  3 -> 1
  4 -> 1
  7 -> 2
  7 -> 2

Variants

sorted_rmat_iterator

template <typename RandomGenerator, typename Graph, typename EdgePredicate = keep_all_edges>
class sorted_rmat_iterator;

sorted_rmat_iterator();
sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n, edges_size_type m, double a, double b, double c, double d, bool permute_vertices = true, EdgePredicate ep = keep_all_edges());

Same parameters as rmat_iterator, but generates all edges up front and returns them in sorted order. Suitable for building CSR graphs.

Additional parameters:

Direction Parameter Description

IN

bool permute_vertices

If true, randomly permute vertex labels. Default: true.

IN

EdgePredicate ep

A binary predicate (vertices_size_type, vertices_size_type) → bool that filters which edges are kept. Default: keep_all_edges (keeps everything).

 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/rmat_graph_generator.hpp>
#include <boost/random/mersenne_twister.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 SGen = sorted_rmat_iterator<mt19937, Graph>;

    mt19937 gen(42);
    double a = 0.57, b = 0.19, c = 0.19, d = 0.05;
    Graph g(SGen(gen, 8, EdgeCount(10), a, b, c, d), SGen(), 8);

    std::cout << num_edges(g) << " edges\n";
    for (auto e : make_iterator_range(edges(g))) {
        std::cout << "  " << source(e, g) << " -> " << target(e, g) << "\n";
    }
}
10 edges
  2 -> 2
  2 -> 3
  2 -> 7
  3 -> 0
  3 -> 1
  3 -> 2
  4 -> 1
  7 -> 2
  7 -> 2
  7 -> 2

unique_rmat_iterator

template <typename RandomGenerator, typename Graph, typename EdgePredicate = keep_all_edges>
class unique_rmat_iterator;

unique_rmat_iterator();
unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, edges_size_type m, double a, double b, double c, double d, bool permute_vertices = true, EdgePredicate ep = keep_all_edges());

Same parameters as rmat_iterator, but filters out duplicate edges. For undirected graphs, edges (u,v) and (v,u) are considered identical. Requesting m close to n^2 may cause very slow generation or an infinite loop.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/rmat_graph_generator.hpp>
#include <boost/random/mersenne_twister.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 UGen = unique_rmat_iterator<mt19937, Graph>;

    mt19937 gen(42);
    double a = 0.57, b = 0.19, c = 0.19, d = 0.05;
    Graph g(UGen(gen, 8, EdgeCount(10), a, b, c, d), UGen(), 8);

    std::cout << num_edges(g) << " edges\n";
    for (auto e : make_iterator_range(edges(g))) {
        std::cout << "  " << source(e, g) << " -> " << target(e, g) << "\n";
    }
}
10 edges
  2 -> 7
  2 -> 2
  2 -> 3
  3 -> 1
  3 -> 0
  3 -> 2
  4 -> 1
  6 -> 0
  7 -> 0
  7 -> 2

Additional parameters:

Direction Parameter Description

IN

bool permute_vertices

If true, randomly permute vertex labels. Default: true.

IN

EdgePredicate ep

A binary predicate (vertices_size_type, vertices_size_type) → bool that filters which edges are kept. Default: keep_all_edges (keeps everything).

sorted_unique_rmat_iterator

template <typename RandomGenerator, typename Graph, typename EdgePredicate = keep_all_edges>
class sorted_unique_rmat_iterator;

sorted_unique_rmat_iterator();
sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, edges_size_type m, double a, double b, double c, double d, bool bidirectional = false, bool permute_vertices = true, EdgePredicate ep = keep_all_edges());

Produces edges that are both sorted and deduplicated. Combines the behaviors of sorted_rmat_iterator and unique_rmat_iterator.

Additional parameters:

Direction Parameter Description

IN

bool bidirectional

If true, for each generated edge (u,v) also insert (v,u). Default: false.

IN

bool permute_vertices

If true, randomly permute vertex labels. Default: true.

IN

EdgePredicate ep

A binary predicate (vertices_size_type, vertices_size_type) → bool that filters which edges are kept. Default: keep_all_edges (keeps everything).

 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/rmat_graph_generator.hpp>
#include <boost/random/mersenne_twister.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 SUGen = sorted_unique_rmat_iterator<mt19937, Graph>;

    mt19937 gen(42);
    double a = 0.57, b = 0.19, c = 0.19, d = 0.05;
    bool bidirectional = false;
    Graph g(SUGen(gen, 8, EdgeCount(10), a, b, c, d, bidirectional), SUGen(), 8);

    std::cout << num_edges(g) << " edges\n";
    for (auto e : make_iterator_range(edges(g))) {
        std::cout << "  " << source(e, g) << " -> " << target(e, g) << "\n";
    }
}
10 edges
  2 -> 2
  2 -> 3
  2 -> 7
  3 -> 0
  3 -> 1
  3 -> 2
  4 -> 1
  6 -> 0
  7 -> 0
  7 -> 2
Edit this Page