For using the igraph C library
Some algorithms in igraph, e.g. the generation of random graphs, require random number generators (RNGs). Prior to version 0.6 igraph did not have a sophisticated way to deal with random number generators at the C level, but this has changed. From version 0.6 different and multiple random number generators are supported.
igraph_rng_t *igraph_rng_default();
Returns:
A pointer to the default random number generator. |
See also:
igraph_rng_set_default() |
void igraph_rng_set_default(igraph_rng_t *rng);
Arguments:
|
The random number generator to use as default from now
on. Calling |
Time complexity: O(1).
igraph_rng_init — Initialize a random number generator.igraph_rng_destroy — Deallocate memory associated with a random number generator.igraph_rng_seed — Set the seed of a random number generator.igraph_rng_min — Query the minimum possible integer for a random number generator.igraph_rng_max — Query the maximum possible integer for a random number generator.igraph_rng_name — Query the type of a random number generator.
int 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:
|
Pointer to an uninitialized RNG. |
|
The type of the RNG, like |
Returns:
Error code. |
Time complexity: depends on the type of the generator, but usually it should be O(1).
void igraph_rng_destroy(igraph_rng_t *rng);
Arguments:
|
The RNG to destroy. Do not destroy an RNG that is used as the default igraph RNG. |
Time complexity: O(1).
int igraph_rng_seed(igraph_rng_t *rng, unsigned long int seed);
Arguments:
|
The RNG. |
|
The new seed. |
Returns:
Error code. |
Time complexity: usually O(1), but may depend on the type of the RNG.
unsigned long int igraph_rng_min(igraph_rng_t *rng);
Arguments:
|
The RNG. |
Returns:
The smallest possible integer that can be generated by
calling |
Time complexity: O(1).
unsigned long int igraph_rng_max(igraph_rng_t *rng);
Arguments:
|
The RNG. |
Returns:
The largest possible integer that can be generated by
calling |
Time complexity: O(1).
igraph_rng_get_integer — Generate an integer random number from an interval.igraph_rng_get_unif — Generate real, uniform random numbers from an intervaligraph_rng_get_unif01 — Generate real, uniform random number from the unit intervaligraph_rng_get_normal — Normally distributed random numbersigraph_rng_get_geom — Generate geometrically distributed random numbersigraph_rng_get_binom — Generate binomially distributed random numbersigraph_rng_get_gamma — Generate sample from a Gamma distribution
long int igraph_rng_get_integer(igraph_rng_t *rng,
long int l, long int h);
Arguments:
|
Pointer to the RNG to use for the generation. Use |
|
Lower limit, inclusive, it can be negative as well. |
|
Upper limit, inclusive, it can be negative as well, but it
should be at least |
Returns:
The generated random integer. |
Time complexity: depends on the generator, but should be usually O(1).
igraph_real_t igraph_rng_get_unif(igraph_rng_t *rng,
igraph_real_t l, igraph_real_t h);
Arguments:
|
Pointer to the RNG to use. Use |
|
The lower bound, it can be negative. |
|
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.
igraph_real_t igraph_rng_get_unif01(igraph_rng_t *rng);
Arguments:
|
Pointer to the RNG to use. Use |
Returns:
The generated uniformly distributed random number. |
Time complexity: depends on the type of the RNG.
igraph_real_t igraph_rng_get_normal(igraph_rng_t *rng,
igraph_real_t m, igraph_real_t s);
Arguments:
|
Pointer to the RNG to use. Use |
|
The mean. |
|
Standard deviation. |
Returns:
The generated normally distributed random number. |
Time complexity: depends on the type of the RNG.
igraph_real_t igraph_rng_get_geom(igraph_rng_t *rng, igraph_real_t p);
Arguments:
|
Pointer to the RNG to use. Use |
|
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 type of the RNG.
igraph_real_t igraph_rng_get_binom(igraph_rng_t *rng, long int n,
igraph_real_t p);
Arguments:
|
Pointer to the RNG to use. Use |
|
Number of observations. |
|
Probability of an event. |
Returns:
The generated binomially distributed random number. |
Time complexity: depends on the type of the RNG.
igraph_real_t igraph_rng_get_gamma(igraph_rng_t *rng, igraph_real_t shape,
igraph_real_t scale);
Arguments:
|
Pointer to the RNG to use. Use |
|
Shape parameter. |
|
Scale parameter. |
Returns:
The generated sample |
Time complexity: depends on RNG.
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 RAND generator on others.
const igraph_rng_type_t igraph_rngtype_mt19937 = {
/* name= */ "MT19937",
/* min= */ 0,
/* max= */ 0xffffffffUL,
/* init= */ igraph_rng_mt19937_init,
/* destroy= */ igraph_rng_mt19937_destroy,
/* seed= */ igraph_rng_mt19937_seed,
/* get= */ igraph_rng_mt19937_get,
/* get_real= */ igraph_rng_mt19937_get_real,
/* get_norm= */ 0,
/* get_geom= */ 0,
/* get_binom= */ 0,
/* get_exp= */ 0,
/* get_gamma= */ 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
gsl_rng_set 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.
const igraph_rng_type_t igraph_rngtype_glibc2 = {
/* name= */ "LIBC",
/* min= */ 0,
/* max= */ 0x7fffffffUL,
/* init= */ igraph_rng_glibc2_init,
/* destroy= */ igraph_rng_glibc2_destroy,
/* seed= */ igraph_rng_glibc2_seed,
/* get= */ igraph_rng_glibc2_get,
/* get_real= */ igraph_rng_glibc2_get_real,
/* get_norm= */ 0,
/* get_geom= */ 0,
/* get_binom= */ 0,
/* get_exp= */ 0,
/* get_gamma= */ 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.
const igraph_rng_type_t igraph_rngtype_rand = {
/* name= */ "RAND",
/* min= */ 0,
/* max= */ 0x7fffffffUL,
/* init= */ igraph_rng_rand_init,
/* destroy= */ igraph_rng_rand_destroy,
/* seed= */ igraph_rng_rand_seed,
/* get= */ igraph_rng_rand_get,
/* get_real= */ igraph_rng_rand_get_real,
/* get_norm= */ 0,
/* get_geom= */ 0,
/* get_binom= */ 0,
/* get_exp= */ 0,
/* get_gamma= */ 0
};
The sequence is
x_{n+1} = (a x_n + c) mod m
with a = 1103515245, c = 12345 and
m = 2^31 = 2147483648.
The seed specifies the initial value, x_1.
The theoretical value of x_{10001} is 1910041713.
The period of this generator is 2^31.
This generator is not very good—the low bits of successive numbers are correlated.
This generator was ported from the GNU Scientific Library.
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.
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).
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.
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().
Example 8.1. File examples/simple/random_seed.c
#include <igraph.h> int main() { 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; }
| ← Chapter 7. Data structure library: vector, matrix, other data types | Chapter 9. Graph generators → |