Struct UnionFind

Source

pub struct UnionFind<'a, A, T, const N: usize>where
    T: VertexType + 'a,
    A: AlgorithmContainer,
{ /* private fields */ }

Expand description

UnionFind data structure

This data structure stores a collection of disjoint (non-overlapping) sets.

UnionFind is parameterized by the following

A - Algorithm, e.g., QuickFind, QuickUnion
T - Any unsigned integral types, e.g., u8, u16, u32, u64, usize or any type that implements VertexType
N - Constant size of internal representative buffer

§Example

use pulau_rs::{UnionFind, QuickFind, QuickUnion};
fn make_uf_quickfind() {
    // construct with quickfind algorithm with fixed size 10
    let mut uf = UnionFind::<QuickFind, u32, 10>::default();
}

fn make_uf_quickunion() {
    // construct with weighted quickunion with path compression algorithm with fixed size 10
    let mut uf = UnionFind::<QuickUnion, u32, 10>::default();
}

§Size Guarantees

Size of UnionFind depends on whether the algorithm you have chosen is weighted

Assuming no padding, If it’s weighted then, size of UnionFind is T * N + size_of(usize) * N

Else it will be T * N

If you are using borrowed buffers, then the size will be the core::mem::size_of::<usize>() * 2 if it’s weighted, else it will just be core::mem::size_of::<usize>()

Implementations§

Source §

impl<'a, T, const N: usize> UnionFind<'a, QuickFind<Borrowed>, T, N>
where T: VertexType,

Source

pub fn new(representative: &'a mut [T]) -> Self

Source §

impl<'a, T, const N: usize, const P: bool> UnionFind<'a, QuickUnion<ByRank<Borrowed<Fat>>, P>, T, N>
where T: VertexType,

Source

pub fn new(representative: &'a mut [T], heuristic: &'a mut [usize]) -> Self

Source §

impl<'a, T, const N: usize, const P: bool> UnionFind<'a, QuickUnion<ByRank<Borrowed<Thin>>, P>, T, N>
where T: VertexType,

Source

pub fn new( representative: &'a mut [T; N], heuristic: &'a mut [usize; N], ) -> Self

Source §

impl<'a, T, const N: usize, const P: bool> UnionFind<'a, QuickUnion<BySize<Borrowed<Fat>>, P>, T, N>
where T: VertexType,

Source

pub fn new(representative: &'a mut [T], heuristic: &'a mut [usize]) -> Self

Source §

impl<'a, T, const N: usize, const P: bool> UnionFind<'a, QuickUnion<BySize<Borrowed<Thin>>, P>, T, N>
where T: VertexType,

Source

pub fn new( representative: &'a mut [T; N], heuristic: &'a mut [usize; N], ) -> Self

Source §

impl<'a, T, const N: usize, const P: bool> UnionFind<'a, QuickUnion<Unweighted<Borrowed<Fat>>, P>, T, N>
where T: VertexType,

Source

pub fn new(representative: &'a mut [T]) -> Self

Source §

impl<'a, T, const N: usize, const P: bool> UnionFind<'a, QuickUnion<Unweighted<Borrowed<Thin>>, P>, T, N>
where T: VertexType,

Source

pub fn new(representative: &'a mut [T; N]) -> Self

Source §

impl<'a, R, T, const N: usize, const P: bool> UnionFind<'a, QuickUnion<ByRandom<R, Borrowed<Fat>>, P>, T, N>
where T: VertexType, R: RngCore + AsMut<R> + AsRef<R>,

Source

pub fn new( representative: &'a mut [T], heuristic: &'a mut [usize], rng: R, ) -> Self

Source §

impl<'a, R, T, const N: usize, const P: bool> UnionFind<'a, QuickUnion<ByRandom<R, Borrowed<Thin>>, P>, T, N>
where T: VertexType, R: RngCore + AsMut<R> + AsRef<R>,

Source

pub fn new( representative: &'a mut [T; N], heuristic: &'a mut [usize; N], rng: R, ) -> Self

Source §

impl<R, const N: usize, const P: bool> UnionFind<'_, QuickUnion<ByRandom<R, Owned>, P>, u8, N>
where R: RngCore,

Source

pub fn new(rng: R) -> Self

Source §

impl<R, const N: usize, const P: bool> UnionFind<'_, QuickUnion<ByRandom<R, Owned>, P>, u16, N>
where R: RngCore,

Source

pub fn new(rng: R) -> Self

Source §

impl<R, const N: usize, const P: bool> UnionFind<'_, QuickUnion<ByRandom<R, Owned>, P>, u32, N>
where R: RngCore,

Source

pub fn new(rng: R) -> Self

Source §

impl<R, const N: usize, const P: bool> UnionFind<'_, QuickUnion<ByRandom<R, Owned>, P>, u64, N>
where R: RngCore,

Source

pub fn new(rng: R) -> Self

Source §

impl<R, const N: usize, const P: bool> UnionFind<'_, QuickUnion<ByRandom<R, Owned>, P>, usize, N>
where R: RngCore,

Source

pub fn new(rng: R) -> Self

Source §

impl<'a, A, T, const N: usize> UnionFind<'a, A, T, N>
where T: VertexType, A: AlgorithmContainer + Union<T, A::HeuristicKind<'a>> + Find<T> + Connected<T>,

Source

pub fn connected(&mut self, a: T::IdentifierType, b: T::IdentifierType) -> bool

Checks whether 2 nodes are connected to each other

Source

pub fn find(&mut self, a: T::IdentifierType) -> T

Finds a node

Source

pub fn union_sets(&mut self, a: T::IdentifierType, b: T::IdentifierType)

Unions 2 node. If those 2 nodes are already part of the same component then this does nothing

Source

pub fn representative(&self) -> &A::RepresentativeContainer<'a, T, N>

Gets the representative slice

Source

pub fn heuristic(&self) -> &A::HeuristicContainer<'a, N>

Gets the heuristic slice

Trait Implementations§

Source §