Skip to main content

igraph/
rng.rs

1//! Random number generation (`igraph_random.h`).
2//!
3//! Every randomized igraph function (the random graph generators of
4//! [`games`](crate::games), randomized community detection, layouts with a
5//! random start, [`Vector::shuffle`](crate::vector::Vector::shuffle), ...)
6//! draws from the calling thread's *default* random number generator. Each
7//! thread gets its own (a PCG32 generator, igraph's default algorithm,
8//! seeded randomly the first time the thread calls into igraph), so threads
9//! never share random state, and [`seed`] makes the results of a thread
10//! reproducible, whatever the other threads do.
11//!
12//! The generators are igraph's own, so a seed gives the very numbers that
13//! igraph's C test suite pins (`tests/unit/igraph_rng_get_integer.out`):
14//!
15//! ```
16//! use igraph::prelude::*;
17//!
18//! rng::seed(42).unwrap();
19//! let a: Vec<i64> = (0..10).map(|_| rng::integer(10, 100)).collect();
20//! assert_eq!(a, vec![22, 59, 86, 99, 99, 77, 93, 12, 20, 62]);
21//! rng::seed(42).unwrap();
22//! let b: Vec<i64> = (0..10).map(|_| rng::integer(10, 100)).collect();
23//! assert_eq!(a, b);
24//!
25//! // Random graphs are reproducible too.
26//! rng::seed(7).unwrap();
27//! let g = Graph::erdos_renyi_game_gnp(30, 0.2, false, EdgeTypeSw::Simple, false).unwrap();
28//! rng::seed(7).unwrap();
29//! let h = Graph::erdos_renyi_game_gnp(30, 0.2, false, EdgeTypeSw::Simple, false).unwrap();
30//! assert_eq!(g, h);
31//! ```
32//!
33//! Independent generators of a chosen [`RngType`] are created as owned
34//! [`Rng`] values, and can be installed as the default for the duration of a
35//! closure with [`Rng::scoped`].
36//!
37//! | C function (`igraph_random.h`) | Default generator | Owned [`Rng`] |
38//! |------------|-------------------|---------------|
39//! | `igraph_rng_init` / `_destroy` | (per thread, automatic) | [`Rng::new`] / [`Drop`] |
40//! | `igraph_rng_seed` | [`seed`] | [`Rng::set_seed`] |
41//! | `igraph_rng_name`, `_bits`, `_max` | [`name`], [`bits`], [`max`] | [`Rng::name`], [`Rng::bits`], [`Rng::max`] |
42//! | (the `is_seeded` field) | | [`Rng::is_seeded`] |
43//! | `igraph_rng_get_integer` | [`integer`] | [`Rng::get_integer`] |
44//! | `igraph_rng_get_unif(01)` | [`uniform`], [`uniform01`] | [`Rng::get_unif`], [`Rng::get_unif01`] |
45//! | `igraph_rng_get_bool` | [`boolean`] | [`Rng::get_bool`] |
46//! | `igraph_rng_get_normal` | [`normal`] | [`Rng::get_normal`] |
47//! | `igraph_rng_get_geom`, `_binom`, `_exp`, `_gamma`, `_pois` | [`geometric`], [`binomial`], [`exponential`], [`gamma`], [`poisson`] | [`Rng::get_geom`], [`Rng::get_binom`], [`Rng::get_exp`], [`Rng::get_gamma`], [`Rng::get_pois`] |
48//! | `igraph_rng_default`, `igraph_rng_set_default` | | [`Rng::scoped`] |
49//! | (Fisher-Yates in Rust) | [`shuffle`] | |
50//!
51//! See also [`games`](crate::games) for random graph models, and
52//! [`misc::sample_sphere_surface`](crate::misc::sample_sphere_surface),
53//! [`misc::sample_sphere_volume`](crate::misc::sample_sphere_volume) and
54//! [`misc::sample_dirichlet`](crate::misc::sample_dirichlet) (also
55//! available as methods of an owned [`Rng`]) for random points and
56//! [`misc::random_sample`](crate::misc::random_sample) for sampling integers
57//! without replacement.
58
59use crate::{error::Result, ffi::*, igraph_call};
60use std::mem::MaybeUninit;
61
62/// An owned random number generator (`igraph_rng_t`).
63pub type Rng = igraph_rng_t;
64
65/// The random number generator algorithms shipped with igraph.
66#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
67pub enum RngType {
68    /// Mersenne Twister MT19937.
69    Mt19937,
70    /// The generator of the GNU C library (`random()`).
71    Glibc2,
72    /// PCG32 (the algorithm of igraph's default generator).
73    Pcg32,
74    /// PCG64.
75    Pcg64,
76}
77
78impl RngType {
79    /// All the generator types, in declaration order.
80    pub const ALL: [RngType; 4] = [Self::Mt19937, Self::Glibc2, Self::Pcg32, Self::Pcg64];
81
82    fn raw(self) -> *const igraph_rng_type_t {
83        match self {
84            Self::Mt19937 => &raw const igraph_rngtype_mt19937,
85            Self::Glibc2 => &raw const igraph_rngtype_glibc2,
86            Self::Pcg32 => &raw const igraph_rngtype_pcg32,
87            Self::Pcg64 => &raw const igraph_rngtype_pcg64,
88        }
89    }
90}
91
92/// Installs a fresh, randomly seeded PCG32 generator (igraph's default
93/// algorithm) as the default generator of the calling thread. Called once per
94/// thread by [`ensure_init`](crate::error::ensure_init).
95///
96/// The generator is intentionally leaked: igraph keeps a raw pointer to it
97/// in thread-local storage that may outlive any Rust thread-local destructor.
98pub(crate) fn install_thread_default_rng() {
99    use std::hash::{BuildHasher, Hasher};
100    let mut raw = MaybeUninit::<igraph_rng_t>::zeroed();
101    let code = unsafe { igraph_rng_init(raw.as_mut_ptr(), RngType::Pcg32.raw()) };
102    if code != igraph_error_type_t_IGRAPH_SUCCESS {
103        // Out of memory while setting up a thread: keep igraph's default.
104        return;
105    }
106    let rng: &'static mut igraph_rng_t = Box::leak(Box::new(unsafe { raw.assume_init() }));
107    // `RandomState` is seeded from the OS once per thread and varies per call.
108    let mut h = std::collections::hash_map::RandomState::new().build_hasher();
109    h.write_u64(
110        std::time::SystemTime::now()
111            .duration_since(std::time::UNIX_EPOCH)
112            .map_or(0, |d| d.as_nanos() as u64),
113    );
114    unsafe {
115        igraph_rng_seed(rng, h.finish());
116        igraph_rng_set_default(rng);
117    }
118}
119
120fn default_rng() -> *mut igraph_rng_t {
121    crate::error::ensure_init();
122    unsafe { igraph_rng_default() }
123}
124
125/// Seeds the default random number generator of the calling thread
126/// ([`igraph_rng_seed`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_seed)).
127///
128/// Only the calling thread is affected: every thread has its own default
129/// generator, so seeded computations are reproducible even when other
130/// threads use random numbers at the same time. A generator installed with
131/// [`Rng::scoped`] is the default while it is in scope, so it is the one
132/// seeded then.
133///
134/// # Errors
135/// Only if igraph fails to seed the generator (it never does for the
136/// generators shipped with igraph).
137pub fn seed(seed: u64) -> Result<()> {
138    igraph_call!(igraph_rng_seed(default_rng(), seed))
139}
140
141/// igraph 1.0.0 and 1.0.1 only `assert` the order of the bounds (aborting,
142/// or computing garbage in release builds of the C library): check them in
143/// Rust.
144#[track_caller]
145fn check_int_bounds(min: i64, max: i64) {
146    assert!(min <= max, "empty integer interval [{min}, {max}]");
147}
148
149/// The bounds of a uniform real must be finite (an infinite width makes
150/// igraph 1.0.0 and 1.0.1 loop, practically forever) and ordered (only
151/// `assert`ed by igraph).
152#[track_caller]
153fn check_real_bounds(min: f64, max: f64) {
154    assert!(
155        min.is_finite() && max.is_finite() && min <= max && (max - min).is_finite(),
156        "invalid real interval [{min}, {max})"
157    );
158}
159
160/// A uniform random integer in the closed interval `[min, max]`
161/// ([`igraph_rng_get_integer`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_integer)).
162///
163/// # Panics
164/// If `min > max`.
165#[track_caller]
166pub fn integer(min: i64, max: i64) -> i64 {
167    check_int_bounds(min, max);
168    unsafe { igraph_rng_get_integer(default_rng(), min, max) }
169}
170
171/// A uniform random real in `[min, max)` (`min` itself if `min == max`)
172/// ([`igraph_rng_get_unif`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_unif)).
173///
174/// # Panics
175/// If a bound is not finite, `max - min` overflows, or `min > max`.
176#[track_caller]
177pub fn uniform(min: f64, max: f64) -> f64 {
178    check_real_bounds(min, max);
179    unsafe { igraph_rng_get_unif(default_rng(), min, max) }
180}
181
182/// A uniform random real in the half-open interval `[0, 1)`
183/// ([`igraph_rng_get_unif01`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_unif01)).
184pub fn uniform01() -> f64 {
185    unsafe { igraph_rng_get_unif01(default_rng()) }
186}
187
188/// A random boolean, `true` with probability 1/2
189/// ([`igraph_rng_get_bool`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_bool)).
190pub fn boolean() -> bool {
191    unsafe { igraph_rng_get_bool(default_rng()) }
192}
193
194/// A normally distributed random real with mean `mean` and standard
195/// deviation `sd`, i.e. with density proportional to
196/// `exp(-(x - mean)² / (2 sd²))`
197/// ([`igraph_rng_get_normal`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_normal)).
198pub fn normal(mean: f64, sd: f64) -> f64 {
199    unsafe { igraph_rng_get_normal(default_rng(), mean, sd) }
200}
201
202/// A geometrically distributed random number (failures before the first
203/// success) with success probability `p` in `(0, 1]`; NaN for an invalid `p`
204/// ([`igraph_rng_get_geom`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_geom)).
205pub fn geometric(p: f64) -> f64 {
206    unsafe { igraph_rng_get_geom(default_rng(), p) }
207}
208
209/// A binomially distributed random number: the number of successes in `n`
210/// independent trials of success probability `p`, i.e. `k` with
211/// probability `C(n, k) p^k (1 - p)^(n - k)`
212/// ([`igraph_rng_get_binom`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_binom)).
213pub fn binomial(n: i64, p: f64) -> f64 {
214    unsafe { igraph_rng_get_binom(default_rng(), n, p) }
215}
216
217/// An exponentially distributed random number with rate `rate` (mean
218/// `1 / rate`); NaN for a non-positive rate, `0` for an infinite one
219/// ([`igraph_rng_get_exp`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_exp)).
220pub fn exponential(rate: f64) -> f64 {
221    unsafe { igraph_rng_get_exp(default_rng(), rate) }
222}
223
224/// A gamma distributed random number with density proportional to
225/// `x^(shape - 1) exp(-x / scale)` (mean `shape * scale`)
226/// ([`igraph_rng_get_gamma`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_gamma)).
227pub fn gamma(shape: f64, scale: f64) -> f64 {
228    unsafe { igraph_rng_get_gamma(default_rng(), shape, scale) }
229}
230
231/// A Poisson distributed random number with mean `mean`; NaN if `mean` is
232/// negative or NaN
233/// ([`igraph_rng_get_pois`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_pois)).
234pub fn poisson(mean: f64) -> f64 {
235    unsafe { igraph_rng_get_pois(default_rng(), mean) }
236}
237
238/// The name of the algorithm of the thread's default generator
239/// ([`igraph_rng_name`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_name)),
240/// e.g. `"PCG64"`.
241pub fn name() -> String {
242    let ptr = unsafe { igraph_rng_name(default_rng()) };
243    unsafe { std::ffi::CStr::from_ptr(ptr) }
244        .to_string_lossy()
245        .into_owned()
246}
247
248/// Number of random bits produced at once by the default generator
249/// ([`igraph_rng_bits`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_bits)).
250pub fn bits() -> u32 {
251    unsafe { igraph_rng_bits(default_rng()) as u32 }
252}
253
254/// The largest integer the default generator can produce natively
255/// ([`igraph_rng_max`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_max)).
256pub fn max() -> u64 {
257    unsafe { igraph_rng_max(default_rng()) }
258}
259
260/// Shuffles a slice in place (Fisher-Yates) with the default generator, so
261/// that the outcome is reproducible with [`seed`]; the slice counterpart of
262/// [`Vector::shuffle`](crate::vector::Vector::shuffle) (`igraph_vector_shuffle`),
263/// which runs the same algorithm: for the same seed both produce the same
264/// permutation.
265///
266/// ```
267/// use igraph::prelude::*;
268/// let mut a: Vec<u32> = (0..10).collect();
269/// rng::seed(1).unwrap();
270/// rng::shuffle(&mut a);
271/// let mut b: Vec<u32> = (0..10).collect();
272/// rng::seed(1).unwrap();
273/// rng::shuffle(&mut b);
274/// assert_eq!(a, b);
275/// a.sort();
276/// assert_eq!(a, (0..10).collect::<Vec<_>>());
277/// ```
278pub fn shuffle<T>(slice: &mut [T]) {
279    for i in (1..slice.len()).rev() {
280        let j = integer(0, i as i64) as usize;
281        slice.swap(i, j);
282    }
283}
284
285impl igraph_rng_t {
286    /// Creates a new generator of the given type, seeded with `seed`
287    /// ([`igraph_rng_init`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_init) and
288    /// [`igraph_rng_seed`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_seed)).
289    ///
290    /// Two generators of the same type and seed produce the same numbers,
291    /// on any thread:
292    ///
293    /// ```
294    /// use igraph::prelude::*;
295    /// // Pinned by igraph's own tests (`rng_init_destroy_max_bits_name_set_default.out`).
296    /// let mut mt = Rng::new(RngType::Mt19937, 42).unwrap();
297    /// let draws: Vec<i64> = (0..5).map(|_| mt.get_integer(0, 100)).collect();
298    /// assert_eq!(draws, vec![37, 80, 96, 18, 73]);
299    /// ```
300    ///
301    /// # Errors
302    /// [`ErrorKind::OutOfMemory`](crate::error::ErrorKind::OutOfMemory) if
303    /// the state cannot be allocated.
304    pub fn new(kind: RngType, seed: u64) -> Result<Self> {
305        crate::error::ensure_init();
306        let mut raw = MaybeUninit::<Self>::zeroed();
307        igraph_call!(igraph_rng_init(raw.as_mut_ptr(), kind.raw()))?;
308        let mut rng = unsafe { raw.assume_init() };
309        rng.set_seed(seed)?;
310        Ok(rng)
311    }
312
313    /// Re-seeds this generator
314    /// ([`igraph_rng_seed`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_seed)): the numbers it produces
315    /// afterwards depend only on its type and on `seed`.
316    pub fn set_seed(&mut self, seed: u64) -> Result<()> {
317        igraph_call!(igraph_rng_seed(self, seed))
318    }
319
320    /// The name of the algorithm, e.g. `"MT19937"`, `"LIBC"`, `"PCG32"` or
321    /// `"PCG64"` ([`igraph_rng_name`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_name)).
322    pub fn name(&self) -> String {
323        let ptr = unsafe { igraph_rng_name(self) };
324        unsafe { std::ffi::CStr::from_ptr(ptr) }
325            .to_string_lossy()
326            .into_owned()
327    }
328
329    /// A uniform random integer in the closed interval `[min, max]`
330    /// ([`igraph_rng_get_integer`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_integer)).
331    ///
332    /// # Panics
333    /// If `min > max`.
334    #[track_caller]
335    pub fn get_integer(&mut self, min: i64, max: i64) -> i64 {
336        check_int_bounds(min, max);
337        unsafe { igraph_rng_get_integer(self, min, max) }
338    }
339
340    /// A uniform random real in `[min, max)`
341    /// ([`igraph_rng_get_unif`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_unif)).
342    ///
343    /// # Panics
344    /// If a bound is not finite, `max - min` overflows, or `min > max`.
345    #[track_caller]
346    pub fn get_unif(&mut self, min: f64, max: f64) -> f64 {
347        check_real_bounds(min, max);
348        unsafe { igraph_rng_get_unif(self, min, max) }
349    }
350
351    /// A uniform random real in `[0, 1)`
352    /// ([`igraph_rng_get_unif01`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_unif01)).
353    pub fn get_unif01(&mut self) -> f64 {
354        unsafe { igraph_rng_get_unif01(self) }
355    }
356
357    /// A normally distributed random real with mean `mean` and standard
358    /// deviation `sd`
359    /// ([`igraph_rng_get_normal`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_normal)).
360    pub fn get_normal(&mut self, mean: f64, sd: f64) -> f64 {
361        unsafe { igraph_rng_get_normal(self, mean, sd) }
362    }
363
364    /// A random boolean ([`igraph_rng_get_bool`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_bool)).
365    pub fn get_bool(&mut self) -> bool {
366        unsafe { igraph_rng_get_bool(self) }
367    }
368
369    /// A geometric random number: the number of failures before the first
370    /// success, with success probability `p`
371    /// ([`igraph_rng_get_geom`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_geom)).
372    pub fn get_geom(&mut self, p: f64) -> f64 {
373        unsafe { igraph_rng_get_geom(self, p) }
374    }
375
376    /// A binomial random number with `n` trials of probability `p`
377    /// ([`igraph_rng_get_binom`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_binom)).
378    pub fn get_binom(&mut self, n: i64, p: f64) -> f64 {
379        unsafe { igraph_rng_get_binom(self, n, p) }
380    }
381
382    /// An exponential random number with the given `rate`
383    /// ([`igraph_rng_get_exp`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_exp)).
384    pub fn get_exp(&mut self, rate: f64) -> f64 {
385        unsafe { igraph_rng_get_exp(self, rate) }
386    }
387
388    /// A gamma random number with the given `shape` and `scale`
389    /// ([`igraph_rng_get_gamma`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_gamma)).
390    pub fn get_gamma(&mut self, shape: f64, scale: f64) -> f64 {
391        unsafe { igraph_rng_get_gamma(self, shape, scale) }
392    }
393
394    /// A Poisson random number with the given `mean`
395    /// ([`igraph_rng_get_pois`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_get_pois)).
396    pub fn get_pois(&mut self, mean: f64) -> f64 {
397        unsafe { igraph_rng_get_pois(self, mean) }
398    }
399
400    /// Number of random bits produced at once by this generator
401    /// ([`igraph_rng_bits`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_bits)).
402    pub fn bits(&self) -> u32 {
403        unsafe { igraph_rng_bits(self) as u32 }
404    }
405
406    /// The largest integer this generator produces natively
407    /// ([`igraph_rng_max`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_max)).
408    pub fn max(&self) -> u64 {
409        unsafe { igraph_rng_max(self) }
410    }
411
412    /// Whether the generator has been seeded (always true for generators
413    /// created with [`Rng::new`]): the `is_seeded` flag that
414    /// `igraph_rng_seed` sets, and that `igraph_setup` checks before seeding
415    /// the default generator.
416    pub fn is_seeded(&self) -> bool {
417        self.is_seeded
418    }
419
420    /// Runs `f` with this generator installed as the thread's default one
421    /// ([`igraph_rng_set_default`](https://igraph.org/c/html/latest/igraph-Random.html#igraph_rng_set_default)), restoring the
422    /// previous default afterwards, even if `f` panics.
423    ///
424    /// Every randomized igraph function called by `f` on this thread (and
425    /// the free functions of this module) then draws from `self`; other
426    /// threads are not affected.
427    ///
428    /// ```
429    /// use igraph::prelude::*;
430    /// let mut rng = Rng::new(RngType::Mt19937, 7).unwrap();
431    /// let x = rng.scoped(|| rng::integer(0, 1_000_000));
432    /// let mut again = Rng::new(RngType::Mt19937, 7).unwrap();
433    /// assert_eq!(again.scoped(|| rng::integer(0, 1_000_000)), x);
434    /// ```
435    pub fn scoped<R>(&mut self, f: impl FnOnce() -> R) -> R {
436        struct Restore(*mut igraph_rng_t);
437        impl Drop for Restore {
438            fn drop(&mut self) {
439                unsafe { igraph_rng_set_default(self.0) };
440            }
441        }
442        crate::error::ensure_init();
443        let _restore = Restore(unsafe { igraph_rng_set_default(self) });
444        f()
445    }
446}
447
448impl Drop for igraph_rng_t {
449    fn drop(&mut self) {
450        if !self.state.is_null() {
451            unsafe { igraph_rng_destroy(self) };
452        }
453    }
454}
455
456unsafe impl Send for igraph_rng_t {}