pulau_rs/quickunion/heuristics/
by_random.rs

1//! ByRandom heuristic for QuickUnion
2
3use core::marker::PhantomData;
4
5use crate::{quickunion::Heuristic, Owned, VertexType};
6use rand_core::RngCore;
7
8pub struct ByRandom<R, K = Owned>(PhantomData<(R, K)>);
9
10impl<R: RngCore, K> Heuristic for ByRandom<R, K> {
11    type RngProvider = R;
12
13    #[inline]
14    fn handle_decision<T>(
15        a: T::IdentifierType,
16        b: T::IdentifierType,
17        _heuristic: &mut [usize],
18        representative: &mut [T],
19        rng: &mut Self::RngProvider,
20    ) where
21        T: VertexType,
22    {
23        if a == b {
24            return;
25        }
26
27        let root_a = T::usize(a);
28        let root_b = T::usize(b);
29
30        // coin flip to decide which root becomes the parent
31        if rng.next_u32() % 2 == 0 {
32            representative[root_a] = representative[root_b];
33        } else {
34            representative[root_b] = representative[root_a];
35        }
36    }
37}

pulau_rs/quickunion/heuristics/by_random.rs

pulau_rs/quickunion/heuristics/
by_random.rs