The library infrastructure module
#include "diplib/union_find.h"
template<typename IndexType_, typename ValueType_, typename UnionFunction_>
dip::UnionFind class

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

Contents

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. more...

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 Create(dip::UnionFind::ValueType const& value = {}) -> dip::UnionFind::IndexType
Creates a new element, and places it in its own tree.
auto FindRoot(dip::UnionFind::IndexType index) const -> dip::UnionFind::IndexType
Returns the index (label) for the root of the tree that contains index.
template<typename Function>
void Iterate(Function function)
Calls function for each tree root. more...
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.
auto Relabel() -> dip::uint
Assigns a new label to each of the trees. more...
template<typename Constraint>
auto Relabel(Constraint constraint) -> dip::uint
Assigns a new label to the trees that satisfy constraint, and 0 to the remainder. more...
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 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.

Alias documentation

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
using IndexType = IndexType_

The type of the index (or label) that identifies each tree element

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
using ValueType = ValueType_

The type of the additional data stored for each tree element

Function documentation

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
UnionFind( UnionFunction_ const& unionFunction) explicit

Default constructor, creates an empty structure

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
UnionFind( dip::uint n, dip::UnionFind::ValueType value, UnionFunction_ const& unionFunction)

Alternate constructor, creates n trees initialized to value.

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

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.

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
dip::UnionFind::IndexType FindRoot( dip::UnionFind::IndexType index) const

Returns the index (label) for the root of the tree that contains index.

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
dip::UnionFind::IndexType Create( dip::UnionFind::ValueType const& value = {})

Creates a new element, and places it in its own tree.

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
dip::UnionFind::IndexType Union( dip::UnionFind::IndexType index1, dip::UnionFind::IndexType index2)

Merges two trees. Returns the index of the new root.

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
dip::UnionFind::ValueType& Value( dip::UnionFind::IndexType index)

Returns a reference to the value associated to the tree that contains index.

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
dip::UnionFind::ValueType const& Value( dip::UnionFind::IndexType index) const

Returns a reference to the value associated to the tree that contains index.

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.

Returns the number of unique labels.

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
dip::UnionFind::IndexType Label( dip::UnionFind::IndexType index) const

Returns the new label associated to the tree that contains index. Only useful after calling Relabel.

template<typename IndexType_, typename ValueType_, typename UnionFunction_>
dip::UnionFind::ValueType const& LabelValue( dip::UnionFind::IndexType index) const

Returns a const reference to the value associated to the tree that contains index. Only useful after calling Relabel.