igraph Reference Manual

For using the igraph C library

Search the manual:

Chapter 8. Random numbers

1. About random numbers in igraph

Some algorithms in igraph, such as sampling from random graph models, require random number generators (RNGs). igraph includes a flexible RNG framework that allows hooking up arbitrary random number generators, and comes with several ready-to-use generators. This framework is used in igraph's high-level interfaces to integrate with the host language's own RNG.

2. The default random number generator

2.1. igraph_rng_default — Query the default random number generator.

igraph_rng_t *igraph_rng_default(void);

Returns: 

A pointer to the default random number generator.

See also: 

2.2. igraph_rng_set_default — Set the default igraph random number generator.

void igraph_rng_set_default(igraph_rng_t *rng);

This function copies the internal structure of the given igraph_rng_t object to igraph's internal default RNG structure. The structure itself contains two pointers only, one to the "methods" of the RNG and one to the memory buffer holding the internal state of the RNG. This means that if you keep on generating random numbers from the RNG after setting it as the default, it will affect the state of the default RNG as well because the two share the same state pointer. However, do not expect igraph_rng_default() to return the same pointer as the one you passed in here - the state is shared, but the entire structure is not.

Arguments: 

rng:

The random number generator to use as default from now on. Calling igraph_rng_destroy() on it, while it is still being used as the default will result in crashes and/or unpredictable results.

Time complexity: O(1).

3. Creating random number generators

3.1. igraph_rng_init — Initializes a random number generator.

igraph_error_t igraph_rng_init(igraph_rng_t *rng, const igraph_rng_type_t *type);

This function allocates memory for a random number generator, with the given type, and sets its seed to the default.

Arguments: 

rng:

Pointer to an uninitialized RNG.

type:

The type of the RNG, such as igraph_rngtype_mt19937, igraph_rngtype_glibc2, igraph_rngtype_pcg32 or igraph_rngtype_pcg64.

Returns: 

Error code.

3.2. igraph_rng_destroy — Deallocates memory associated with a random number generator.

void igraph_rng_destroy(igraph_rng_t *rng);

Arguments: 

rng:

The RNG to destroy. Do not destroy an RNG that is used as the default igraph RNG.

Time complexity: O(1).

3.3. igraph_rng_seed — Seeds a random number generator.

igraph_error_t igraph_rng_seed(igraph_rng_t *rng, igraph_uint_t seed);

Arguments: 

rng:

The RNG.

seed:

The new seed.

Returns: 

Error code.

Time complexity: usually O(1), but may depend on the type of the RNG.

3.4. igraph_rng_bits — The number of random bits that a random number generator can produces in a single round.

 igraph_integer_t igraph_rng_bits(const igraph_rng_t* rng);

Arguments: 

rng:

The RNG.

Returns: 

The number of random bits that can be generated in a single round with the RNG.

Time complexity: O(1).

3.5. igraph_rng_max — The maximum possible integer for a random number generator.

igraph_uint_t igraph_rng_max(const igraph_rng_t *rng);

Note that this number is only for informational purposes; it returns the maximum possible integer that can be generated with the RNG with a single call to its internals. It is derived directly from the number of random bits that the RNG can generate in a single round. When this is smaller than what would be needed by other RNG functions like igraph_rng_get_integer(), igraph will call the RNG multiple times to generate more random bits.

Arguments: 

rng:

The RNG.

Returns: 

The largest possible integer that can be generated in a single round with the RNG.

Time complexity: O(1).

3.6. igraph_rng_name — The type of a random number generator.

const char *igraph_rng_name(const igraph_rng_t *rng);

Arguments: 

rng:

The RNG.

Returns: 

The name of the type of the generator. Do not deallocate or change the returned string.

Time complexity: O(1).

4. Generating random numbers

4.1. igraph_rng_get_integer — Generate an integer random number from an interval.

igraph_integer_t igraph_rng_get_integer(
    igraph_rng_t *rng, igraph_integer_t l, igraph_integer_t h
);

Arguments: 

rng:

Pointer to the RNG to use for the generation. Use igraph_rng_default() here to use the default igraph RNG.

l:

Lower limit, inclusive, it can be negative as well.

h:

Upper limit, inclusive, it can be negative as well, but it should be at least l.

Returns: 

The generated random integer.

Time complexity: O(log2(h-l) / bits) where bits is the value of igraph_rng_bits(rng).

4.2. igraph_rng_get_unif01 — Samples uniformly from the unit interval.

igraph_real_t igraph_rng_get_unif01(igraph_rng_t *rng);

Generates uniformly distributed real numbers from the [0, 1) half-open interval.

Arguments: 

rng:

Pointer to the RNG to use. Use igraph_rng_default() here to use the default igraph RNG.

Returns: 

The generated uniformly distributed random number.

Time complexity: depends on the type of the RNG.

4.3. igraph_rng_get_unif — Samples real numbers from a given interval.

igraph_real_t igraph_rng_get_unif(igraph_rng_t *rng,
                                  igraph_real_t l, igraph_real_t h);

Generates uniformly distributed real numbers from the [l, h) half-open interval.

Arguments: 

rng:

Pointer to the RNG to use. Use igraph_rng_default() here to use the default igraph RNG.

l:

The lower bound, it can be negative.

h:

The upper bound, it can be negative, but it has to be larger than the lower bound.

Returns: 

The generated uniformly distributed random number.

Time complexity: depends on the type of the RNG.

4.4. igraph_rng_get_normal — Samples from a normal distribution.

igraph_real_t igraph_rng_get_normal(igraph_rng_t *rng,
                                    igraph_real_t m, igraph_real_t s);

Generates random variates from a normal distribution with probability density

exp( -(x - m)^2 / (2 s^2) ).

Arguments: 

rng:

Pointer to the RNG to use. Use igraph_rng_default() here to use the default igraph RNG.

m:

The mean.

s:

The standard deviation.

Returns: 

The generated normally distributed random number.

Time complexity: depends on the type of the RNG.

4.5. igraph_rng_get_exp — Samples from an exponential distribution.

igraph_real_t igraph_rng_get_exp(igraph_rng_t *rng, igraph_real_t rate);

Generates random variates from an exponential distribution with probability density proportional to

exp(-rate x).

Arguments: 

rng:

Pointer to the RNG to use. Use igraph_rng_default() here to use the default igraph RNG.

rate:

Rate parameter.

Returns: 

The generated sample.

Time complexity: depends on the RNG.

4.6. igraph_rng_get_gamma — Samples from a gamma distribution.

igraph_real_t igraph_rng_get_gamma(igraph_rng_t *rng, igraph_real_t shape,
                                   igraph_real_t scale);

Generates random variates from a gamma distribution with probability density proportional to

x^(shape-1) exp(-x / scale).

Arguments: 

rng:

Pointer to the RNG to use. Use igraph_rng_default() here to use the default igraph RNG.

shape:

Shape parameter.

scale:

Scale parameter.

Returns: 

The generated sample.

Time complexity: depends on the RNG.

4.7. igraph_rng_get_binom — Samples from a binomial distribution.

igraph_real_t igraph_rng_get_binom(igraph_rng_t *rng, igraph_integer_t n, igraph_real_t p);

Generates random variates from a binomial distribution. The number k is generated with probability

(n \choose k) p^k (1-p)^(n-k), k = 0, 1, ..., n.

Arguments: 

rng:

Pointer to the RNG to use. Use igraph_rng_default() here to use the default igraph RNG.

n:

Number of observations.

p:

Probability of an event.

Returns: 

The generated binomially distributed random number.

Time complexity: depends on the RNG.

4.8. igraph_rng_get_geom — Samples from a geometric distribution.

igraph_real_t igraph_rng_get_geom(igraph_rng_t *rng, igraph_real_t p);

Generates random variates from a geometric distribution. The number k is generated with probability

(1 - p)^k p, k = 0, 1, 2, ....

Arguments: 

rng:

Pointer to the RNG to use. Use igraph_rng_default() here to use the default igraph RNG.

p:

The probability of success in each trial. Must be larger than zero and smaller or equal to 1.

Returns: 

The generated geometrically distributed random number.

Time complexity: depends on the RNG.

4.9. igraph_rng_get_pois — Samples from a Poisson distribution.

igraph_real_t igraph_rng_get_pois(igraph_rng_t *rng, igraph_real_t rate);

Generates random variates from a Poisson distribution. The number k is generated with probability

rate^k * exp(-rate) / k!, k = 0, 1, 2, ....

Arguments: 

rng:

Pointer to the RNG to use. Use igraph_rng_default() here to use the default igraph RNG.

rate:

The rate parameter of the Poisson distribution. Must not be negative.

Returns: 

The generated geometrically distributed random number.

Time complexity: depends on the RNG.

5. Supported random number generators

By default igraph uses the MT19937 generator. Prior to igraph version 0.6, the generator supplied by the standard C library was used. This means the GLIBC2 generator on GNU libc 2 systems, and maybe the BSD RAND generator on others. The RAND generator was removed due to poor statistical properties in version 0.10. The PCG32 generator was added in version 0.10.

5.1. igraph_rngtype_mt19937 — The MT19937 random number generator.

const igraph_rng_type_t igraph_rngtype_mt19937 = {
    /* name= */      "MT19937",
    /* bits=  */     32,
    /* init= */      igraph_rng_mt19937_init,
    /* destroy= */   igraph_rng_mt19937_destroy,
    /* seed= */      igraph_rng_mt19937_seed,
    /* get= */       igraph_rng_mt19937_get,
    /* get_int= */   0,
    /* get_real= */  0,
    /* get_norm= */  0,
    /* get_geom= */  0,
    /* get_binom= */ 0,
    /* get_exp= */   0,
    /* get_gamma= */ 0,
    /* get_pois= */  0
};

The MT19937 generator of Makoto Matsumoto and Takuji Nishimura is a variant of the twisted generalized feedback shift-register algorithm, and is known as the “Mersenne Twister” generator. It has a Mersenne prime period of 2^19937 - 1 (about 10^6000) and is equi-distributed in 623 dimensions. It has passed the diehard statistical tests. It uses 624 words of state per generator and is comparable in speed to the other generators. The original generator used a default seed of 4357 and choosing s equal to zero in igraph_rng_mt19937_seed() reproduces this. Later versions switched to 5489 as the default seed, you can choose this explicitly via igraph_rng_seed() instead if you require it.

For more information see, Makoto Matsumoto and Takuji Nishimura, “Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator”. ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1 (Jan. 1998), Pages 3–30

The generator igraph_rngtype_mt19937 uses the second revision of the seeding procedure published by the two authors above in 2002. The original seeding procedures could cause spurious artifacts for some seed values.

This generator was ported from the GNU Scientific Library.

5.2. igraph_rngtype_glibc2 — The random number generator introduced in GNU libc 2.

const igraph_rng_type_t igraph_rngtype_glibc2 = {
    /* name= */      "LIBC",
    /* bits=  */     31,
    /* init= */      igraph_rng_glibc2_init,
    /* destroy= */   igraph_rng_glibc2_destroy,
    /* seed= */      igraph_rng_glibc2_seed,
    /* get= */       igraph_rng_glibc2_get,
    /* get_int= */   0,
    /* get_real= */  0,
    /* get_norm= */  0,
    /* get_geom= */  0,
    /* get_binom= */ 0,
    /* get_exp= */   0,
    /* get_gamma= */ 0,
    /* get_pois= */  0
};

This is a linear feedback shift register generator with a 128-byte buffer. This generator was the default prior to igraph version 0.6, at least on systems relying on GNU libc. This generator was ported from the GNU Scientific Library. It is a reimplementation and does not call the system glibc generator.

5.3. igraph_rngtype_pcg32 — The PCG random number generator (32-bit version).

const igraph_rng_type_t igraph_rngtype_pcg32 = {
    /* name= */      "PCG32",
    /* bits=  */     32,
    /* init= */      igraph_rng_pcg32_init,
    /* destroy= */   igraph_rng_pcg32_destroy,
    /* seed= */      igraph_rng_pcg32_seed,
    /* get= */       igraph_rng_pcg32_get,
    /* get_int= */   0,
    /* get_real= */  0,
    /* get_norm= */  0,
    /* get_geom= */  0,
    /* get_binom= */ 0,
    /* get_exp= */   0,
    /* get_gamma= */ 0,
    /* get_pois= */  0
};

This is an implementation of the PCG random number generator; see https://www.pcg-random.org for more details. This implementation returns 32 random bits in a single iteration.

The generator was ported from the original source code published by the authors at https://github.com/imneme/pcg-c.

5.4. igraph_rngtype_pcg64 — The PCG random number generator (64-bit version).

const igraph_rng_type_t igraph_rngtype_pcg64 = {
    /* name= */      "PCG64",
    /* bits=  */     64,
    /* init= */      igraph_rng_pcg64_init,
    /* destroy= */   igraph_rng_pcg64_destroy,
    /* seed= */      igraph_rng_pcg64_seed,
    /* get= */       igraph_rng_pcg64_get,
    /* get_int= */   0,
    /* get_real= */  0,
    /* get_norm= */  0,
    /* get_geom= */  0,
    /* get_binom= */ 0,
    /* get_exp= */   0,
    /* get_gamma= */ 0,
    /* get_pois= */  0
};

This is an implementation of the PCG random number generator; see https://www.pcg-random.org for more details. This implementation returns 64 random bits in a single iteration. It is only available on 64-bit plaforms with compilers that provide the __uint128_t type.

PCG64 typically provides better performance than PCG32 when sampling floating point numbers or very large integers, as it can provide twice as many random bits in a single generation round.

The generator was ported from the original source code published by the authors at https://github.com/imneme/pcg-c.

6. Use cases

6.1. Normal (default) use

If the user does not use any of the RNG functions explicitly, but calls some of the randomized igraph functions, then a default RNG is set up the first time an igraph function needs random numbers. The seed of this RNG is the output of the time(0) function call, using the time function from the standard C library. This ensures that igraph creates a different random graph, each time the C program is called.

The created default generator is stored internally and can be queried with the igraph_rng_default() function.

6.2. Reproducible simulations

If reproducible results are needed, then the user should set the seed of the default random number generator explicitly, using the igraph_rng_seed() function on the default generator, igraph_rng_default(). When setting the seed to the same number, igraph generates exactly the same random graph (or series of random graphs).

6.3. Changing the default generator

By default igraph uses the igraph_rng_default() random number generator. This can be changed any time by calling igraph_rng_set_default(), with an already initialized random number generator. Note that the old (replaced) generator is not destroyed, so no memory is deallocated.

6.4. Using multiple generators

igraph also provides functions to set up multiple random number generators, using the igraph_rng_init() function, and then generating random numbers from them, e.g. with igraph_rng_get_integer() and/or igraph_rng_get_unif() calls.

Note that initializing a new random number generator is independent of the generator that the igraph functions themselves use. If you want to replace that, then please use igraph_rng_set_default().

6.5. Example

Example 8.1.  File examples/simple/random_seed.c

#include <igraph.h>

int main(void) {

    igraph_t g1, g2;
    igraph_bool_t iso;

    /* Seed the default random number generator and create a random graph. */

    igraph_rng_seed(igraph_rng_default(), 1122);

    igraph_erdos_renyi_game(&g1, IGRAPH_ERDOS_RENYI_GNP,
                            100, 3.0 / 100, /*directed=*/ 0, /*loops=*/ 0);

    /* Seed the generator with the same seed again,
     * and create a graph with the same method. */

    igraph_rng_seed(igraph_rng_default(), 1122);

    igraph_erdos_renyi_game(&g2, IGRAPH_ERDOS_RENYI_GNP,
                            100, 3.0 / 100, /*directed=*/ 0, /*loops=*/ 0);

    /* The two graphs will be identical. */

    igraph_is_same_graph(&g1, &g2, &iso);

    if (!iso) {
        return 1;
    }

    /* Destroy no longer needed data structures. */

    igraph_destroy(&g2);
    igraph_destroy(&g1);

    return 0;
}