Struct graph::dss::DisjointSetStruct
source · pub struct DisjointSetStruct<NI: Idx>(/* private fields */);
Expand description
A thread-safe Disjoint Set Struct implementation, that can be safely shared and accessed across threads.
The implementation is based on the Java implementation [1] which in turn is based on a C++ implementation and some input from a Rust implementation [3].
This implementation is tailored for the graph crate as
it needs to support the Idx
trait.
Implementations§
Trait Implementations§
source§impl<NI: Idx> Components<NI> for DisjointSetStruct<NI>
impl<NI: Idx> Components<NI> for DisjointSetStruct<NI>
source§impl<NI: Idx> UnionFind<NI> for DisjointSetStruct<NI>
impl<NI: Idx> UnionFind<NI> for DisjointSetStruct<NI>
source§fn union(&self, id1: NI, id2: NI)
fn union(&self, id1: NI, id2: NI)
Joins the set of id1
with the set of id2
.
Examples
use graph::prelude::*;
let dss = DisjointSetStruct::new(10);
dss.union(2, 4);
assert_eq!(dss.find(2), 2);
assert_eq!(dss.find(4), 2);
source§fn find(&self, id: NI) -> NI
fn find(&self, id: NI) -> NI
Find the set of id
.
Examples
use graph::prelude::*;
let dss = DisjointSetStruct::new(10);
assert_eq!(dss.find(4), 4);
dss.union(4, 2);
assert_eq!(dss.find(4), 2);
impl<NI: Idx> Send for DisjointSetStruct<NI>
impl<NI: Idx> Sync for DisjointSetStruct<NI>
Auto Trait Implementations§
impl<NI> !RefUnwindSafe for DisjointSetStruct<NI>
impl<NI> Unpin for DisjointSetStruct<NI>
impl<NI> UnwindSafe for DisjointSetStruct<NI>where NI: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more