template<typename IndexType_,
typename ValueType_,
typename UnionFunction_>
UnionFind class
An STLlike data structure for the unionfind algorithm.
Contents
Operations such as the watershed, connected component labeling, and the area opening, as implemented in
DIPlib, use the unionfind algorithm. It provides an efficient method to set equivalences in labels.
That is, one can reassign 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 streamline 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 copyconstructible and
defaultinitializable. 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 tovalue
.
Aliases
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 callingRelabel
.  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 callingRelabel
.
Function documentation
template<typename IndexType_, typename ValueType_, typename UnionFunction_>
template<typename Function>
void
Iterate(Function function)
template<typename 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_>
template<typename Constraint>
dip::uint
Relabel(Constraint constraint)
template<typename 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.
Returns the number of unique labels.