3 unstable releases
0.2.1 | Oct 8, 2024 |
---|---|
0.2.0 | Sep 24, 2024 |
0.1.0 | Oct 12, 2023 |
#458 in Algorithms
161 downloads per month
18KB
351 lines
Tagged Union-Find Sets
In industrial use, besides testing whether two elements are in a same set, we often want to know the size of a set, iterate over a set or do some other things about the sets. The mergable tags are a natural way to achieve these. That is to say, sets are associated with tags. When two sets are united, their tags are merged.
Recipes
Minimal overhead union-find sets
Just use SizedTag<()>
as tags, like the following example.
use tagged_ufs::{SizedTag, UnionFindSets};
# fn main() {
let mut ufs = UnionFindSets::<u64, SizedTag<()>>::new();
ufs.make_set(0, SizedTag::new(())).unwrap();
ufs.make_set(1, SizedTag::new(())).unwrap();
ufs.make_set(2, SizedTag::new(())).unwrap();
ufs.unite(&0, &1).unwrap();
let set_0 = ufs.find(&0).unwrap();
let set_1 = ufs.find(&1).unwrap();
let set_2 = ufs.find(&2).unwrap();
assert_eq!(ufs.len(), 2);
assert_eq!(set_0.root, set_1.root);
assert_ne!(set_0.root, set_2.root);
# }
Iteration over sets
Users usually need not implement their own iterable types. This crate provides
tag::SizedIterable
, which is suitable in most cases.
First, we need to define a type for tags. In order to efficiently merge tags, we use linked lists to record the elements in the sets.
use std::collections::LinkedList;
use tagged_ufs::{Lengthed, Mergable};
struct MyIterable<Key> {
elems: LinkedList<Key>,
}
Second, we implement Mergable
and Lengthed
for MyIterable
.
# use std::collections::LinkedList;
# use tagged_ufs::{Lengthed, Mergable};
# struct MyIterable<Key> {
# elems: LinkedList<Key>,
# }
impl<Key> Lengthed for MyIterable<Key> {
fn len(&self) -> usize {
self.elems.len()
}
}
impl<Key> Mergable<Key> for MyIterable<Key> {
fn merge<K1, K2>(&mut self, mut other: Self, _key1: &K1, _key2: &K2)
where
K1: std::borrow::Borrow<Key>,
K2: std::borrow::Borrow<Key>,
{
self.elems.append(&mut other.elems);
}
}
Finally, we can test it.
# use std::collections::LinkedList;
# use tagged_ufs::{Lengthed, Mergable};
#
# struct MyIterable<Key> {
# elems: LinkedList<Key>,
# }
#
# impl<Key> Lengthed for MyIterable<Key> {
# fn len(&self) -> usize {
# self.elems.len()
# }
# }
#
# impl<Key> Mergable<Key> for MyIterable<Key> {
# fn merge<K1, K2>(&mut self, mut other: Self, _key1: &K1, _key2: &K2)
# where
# K1: std::borrow::Borrow<Key>,
# K2: std::borrow::Borrow<Key>,
# {
# self.elems.append(&mut other.elems);
# }
# }
#
impl<Key> MyIterable<Key> {
fn new(init: Key) -> Self {
Self {
elems: LinkedList::from([init]),
}
}
}
# fn main() {
use tagged_ufs::UnionFindSets;
let mut ufs = UnionFindSets::<u64, MyIterable<u64>>::new();
ufs.make_set(0, MyIterable::new(0)).unwrap();
ufs.make_set(1, MyIterable::new(1)).unwrap();
ufs.make_set(2, MyIterable::new(2)).unwrap();
ufs.unite(&0, &1).unwrap();
let set_0 = ufs.find(&0).unwrap();
let set_1 = ufs.find(&1).unwrap();
let set_2 = ufs.find(&2).unwrap();
println!("{:?}", set_0.tag.elems); // [0, 1] or [1, 0]
println!("{:?}", set_2.tag.elems); // [2]
# }
For those who want to read the complete example, please refer to examples/my_iterable.rs.
Minimal spanning tree
Please take a look at the example examples/mst.rs.
Dependencies
~0.8–1.1MB
~16K SLoC