This project implements efficient samplers for random connected graphs from selected subcritical block-stable classes. It is based on an R-enriched tree encoding of such graphs and a resulting coupling with simply generated trees. This way, graphs may be viewed as blow-ups of trees, where for each vertex v with children v1, ..., v_k we remove the edges between v and its children and add new edges with endpoints in {v, v_1, ..., v_k} according a random choice that only depends on the outdegree k. These edges are called the decoration of v.

The algorithm proceeds in two steps. First, it generates the underlying simply generated tree using a multithreaded version of an algorithm by Devroye (2012, SIAM Journal of Computing). Second, it generates the decorations of vertices in two phases. In the first phase, the decoration of vertices with small outdegree are generated using precomputed probability weights. In the second phase, decorations of the remaining vertices with large outdegree are generated using a multi-threaded coupon collection algorithm. Each thread uses a Boltzmann sampling procedure to generate randomly sized decorations which are added to the coupon list if the size matches the outdegree of one of the vertices missing a decoration. The parameter for the Boltzmann sampler is adjusted so that the roughly expected size matches the range of the outdegrees.

The program may be instructed to output lists of vertex parameters (degree profile, height profile, closeness centrality) of the generated graph, ordered according to a breadth-first-search of the underlying tree.

Currently, the following graph classes are supported:

• Trees
• Cactus Graphs
• Outerplanar Graphs

This project implements a random generator for uniform simple quadrangulations of the 2-sphere with a given number of quadrangles. It is based on the bijection between simple quadrangulations and 1-blossoming trees by Fusy (2010, PhD thesis at École Polytechnique), and a generating procedure for random blossoming trees by Addario-Berry and Albenque (2017, The Annals of Probability).

This project implements a random generator for uniform simple triangulations of the 2-sphere with a given number of triangles. It is based on the bijection between simple triangulations and blossoming trees by Poulalhon and Schaeffer (2006, Algorithmica), and a generating procedure for random blossoming trees by Addario-Berry and Albenque (2017, The Annals of Probability).

This project implements efficient samplers for random trees. The current version supports the simulation of Bienaymeé-Galton-Watson trees conditioned on having a fixed number of vertices. The simulation uses a multithreaded version of an algorithm by Devroye (2012, SIAM Journal of Computing). The idea is to sample multinomially distributed random variates many times until a certain stopping condition is reached.

The program may be instructed to output lists of vertex parameters in depth-first-search order (degree profile, height profile, closeness centrality) and calculate the looptree corresponding to the simulated random tree (with identical vertex ids).

The closeness centrality of a vertex in a graph is the inverse of the average graph distance from this vertex to all other vertices. This project enables us to calculate the closeness centrality of each vertex in a graph with millions vertices. Implementations of algorithms that significantly reduce the number of calculations exist, but require too much memory. The main reason is that the entire distance matrix is calculated. Hence memory usage is quadratic in the number of vertices of the graph.

For this reason we use a simple breadth-first-search based approach instead. This requires more calculations, but memory usage is only linear in the number of vertices. We mitigate the speed loss using an efficient implementation and distributing the workload on multiple threads.