Crate tagged_ufs

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};

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.

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.

impl<Key> MyIterable<Key> {
    fn new(init: Key) -> Self {
        Self {
            elems: LinkedList::from([init]),
        }
    }
}

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.

Structs

• Set
  An individual set of elements, provided in the way of the root element and its tag.
• SizedIterable
  A wrapper to customized tag, which provides iterability over elements.
• SizedTag
  A wrapper to customized tag, which can inspect the size of a set.
• UnionFindSets
  Raw implementation of union-find sets, with built-in balanced union and path compression.

Traits

• Lengthed
  A trait that allows querying the size of a set.
• Mergable
  A trait that allows merging two sets.