Struct graph::afforest::Afforest

pub struct Afforest<NI: Idx>(/* private fields */);

A union find data structure based on [1].

Note, that this data structure requires calling compress before calling find in order to return the correct set id.

[1] Michael Sutton, Tal Ben-Nun, Amnon Barak: “Optimizing Parallel Graph Connectivity Computation via Subgraph Sampling”, Symposium on Parallel and Distributed Processing, IPDPS 2018

Implementations

impl<NI: Idx> Afforest<NI>

pub fn new(size: usize) -> Self

Creates a new disjoint-set struct of size elements.

Examples

use graph::prelude::*;

let af = Afforest::new(3);
af.union(0, 1);
af.compress();

let set0 = af.find(0);
let set1 = af.find(1);
assert_eq!(set0, set1);

Trait Implementations

impl<NI: Idx> Components<NI> for Afforest<NI>

fn component(&self, node: NI) -> NI

fn to_vec(self) -> Vec<NI>

impl<NI: Idx> UnionFind<NI> for Afforest<NI>

fn union(&self, u: NI, v: NI)

Joins the set of id1 with the set of id2.

fn find(&self, u: NI) -> NI

Find the set of id.

fn len(&self) -> usize

Returns the number of elements in the union find, also referred to as its ‘length’.

fn compress(&self)

Compress the data if possible. After that operation each index stores the final set id.

impl<NI: Idx> Send for Afforest<NI>

impl<NI: Idx> Sync for Afforest<NI>