dip::UnionFind class

An STL-like data structure for the union-find algorithm.

Reference

Operations such as the watershed, connected component labeling, and the area opening, as implemented in DIPlib, use the union-find algorithm. It provides an efficient method to set equivalences in labels. That is, one can re-assign one label to be equivalent to another in O(1) time. Typically, one pass through the image assigns a label to each pixel (Create), and determines which labels should be equivalent (Union); a second pass changes the label for each pixel to that of the representative label for the corresponding set of equivalent labels (FindRoot).

To stream-line the second pass, we provide here a Relabel method that assigns a unique, consecutive label to each of the correspondence sets.

Each tree element has a value associated to it. This must be a type that is copy-constructible and default-initializable. Ideally, it’s small. The value associated to any tree element that is not a root is ignored. The unionFunction that the constructor takes is used to compute the value associated to the merged tree when two trees are merged. It should have the following signature:

ValueType_ unionFunction( ValueType_ const& value1, ValueType_ const& value2 );

The IndexType_ template parameter should be an integer, and probably unsigned.

See the code to any of the algorithms that use this class for an example usage.

Derived classes

template<typename IndexType_> class dip::SimpleUnionFind: A simplified version of dip::UnionFind that doesn’t store any information about the regions, only equivalences.

Constructors, destructors, assignment and conversion operators

UnionFind(UnionFunction_ const& unionFunction) explicit: Default constructor, creates an empty structure
UnionFind(dip::uint n, dip::UnionFind::ValueType value, UnionFunction_ const& unionFunction): Alternate constructor, creates n trees initialized to value.

Aliases

using IndexType = IndexType_: The type of the index (or label) that identifies each tree element
using ValueType = ValueType_: The type of the additional data stored for each tree element

Functions

auto Size() const -> dip::uint: Returns the number of elements in the data structure. Note that the 0th element is counted but not used. This is not the number of trees.
auto FindRoot(dip::UnionFind::IndexType index) const -> dip::UnionFind::IndexType: Returns the index (label) for the root of the tree that contains index.
auto Create(dip::UnionFind::ValueType const& value = {}) -> dip::UnionFind::IndexType: Creates a new element, and places it in its own tree.
auto Union(dip::UnionFind::IndexType index1, dip::UnionFind::IndexType index2) -> dip::UnionFind::IndexType: Merges two trees. Returns the index of the new root.
auto Value(dip::UnionFind::IndexType index) -> dip::UnionFind::ValueType&: Returns a reference to the value associated to the tree that contains index.
auto Value(dip::UnionFind::IndexType index) const -> dip::UnionFind::ValueType const&: Returns a reference to the value associated to the tree that contains index.
template<typename Function> void Iterate(Function function): Calls function for each tree root.
auto Relabel() -> dip::uint: Assigns a new label to each of the trees.
template<typename Constraint> auto Relabel(Constraint constraint) -> dip::uint: Assigns a new label to the trees that satisfy constraint, and 0 to the remainder.
auto Label(dip::UnionFind::IndexType index) const -> dip::UnionFind::IndexType: Returns the new label associated to the tree that contains index. Only useful after calling Relabel.
auto LabelValue(dip::UnionFind::IndexType index) const -> dip::UnionFind::ValueType const&: Returns a const reference to the value associated to the tree that contains index. Only useful after calling Relabel.

Function documentation

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
template<typename Function>
void Iterate(Function function)

Calls function for each tree root.

function is a function or function object that takes the index (IndexType) and ValueType associated to a tree.

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
dip::uint Relabel()

Assigns a new label to each of the trees.

Returns the number of unique labels.

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
template<typename Constraint>
dip::uint Relabel(Constraint constraint)

Assigns a new label to the trees that satisfy constraint, and 0 to the remainder.

constraint is a function or function object that takes the ValueType associated to a tree, and returns true if the tree is to be kept.