MR::UnionFind< I > Class Template Reference

Union-find data structure for representing disjoin sets of elements with few very quick operations: 1) union of two sets in one, 2) checking whether two elements pertain to the same set, 3) finding representative element (root) of each set by any set's element. More...

#include <MRUnionFind.h>

Public Types
using	SizeType = typename I::ValueType
	the type that can hold the number of elements of the maximal set (e.g. int for FaceId and size_t for VoxelId)

Public Member Functions
	UnionFind ()=default
	UnionFind (size_t size)
	creates union-find with given number of elements, each element is the only one in its disjoint set
auto	size () const
	returns the number of elements in union-find
void	reset (size_t size)
	resets union-find to represent given number of elements, each element is the only one in its disjoint set
std::pair< I, bool >	unite (I first, I second)
bool	united (I first, I second)
	returns true if given two elements are from one set
bool	isRoot (I a) const
	returns true if given element is the root of some set
I	parent (I a) const
	return parent element of this element, which is equal to given element only for set's root
I	find (I a)
	finds the root of the set containing given element with optimizing data structure updates
I	findUpdateRange (I a, I begin, I end)
	finds the root of the set containing given element with optimizing data structure in the range [begin, end)
const Vector< I, I > &	roots ()
	sets the root of corresponding set as the parent of each element, then returns the vector
const Vector< I, I > &	parents () const
	gets the parents of all elements as is
SizeType	sizeOfComp (I a)
	returns the number of elements in the set containing given element

Detailed Description

template<typename I>
class MR::UnionFind< I >

Union-find data structure for representing disjoin sets of elements with few very quick operations: 1) union of two sets in one, 2) checking whether two elements pertain to the same set, 3) finding representative element (root) of each set by any set's element.

Template Parameters

I	is the identifier of a set's element, e.g. FaceId

Member Typedef Documentation

SizeType

template<typename I >

using MR::UnionFind< I >::SizeType = typename I::ValueType

the type that can hold the number of elements of the maximal set (e.g. int for FaceId and size_t for VoxelId)

Constructor & Destructor Documentation

UnionFind() [1/2]

template<typename I >

MR::UnionFind< I >::UnionFind ( )

default

UnionFind() [2/2]

template<typename I >

MR::UnionFind< I >::UnionFind ( size_t size )

inlineexplicit

creates union-find with given number of elements, each element is the only one in its disjoint set

Member Function Documentation

find()

template<typename I >

I MR::UnionFind< I >::find ( I a )

inline

finds the root of the set containing given element with optimizing data structure updates

findUpdateRange()

template<typename I >

I MR::UnionFind< I >::findUpdateRange ( I a, I begin, I end )

inline

finds the root of the set containing given element with optimizing data structure in the range [begin, end)

isRoot()

template<typename I >

bool MR::UnionFind< I >::isRoot ( I a ) const

inline

returns true if given element is the root of some set

parent()

template<typename I >

I MR::UnionFind< I >::parent ( I a ) const

inline

return parent element of this element, which is equal to given element only for set's root

parents()

template<typename I >

const Vector< I, I > & MR::UnionFind< I >::parents ( ) const

inline

gets the parents of all elements as is

reset()

template<typename I >

void MR::UnionFind< I >::reset ( size_t size )

inline

resets union-find to represent given number of elements, each element is the only one in its disjoint set

roots()

template<typename I >

const Vector< I, I > & MR::UnionFind< I >::roots ( )

inline

sets the root of corresponding set as the parent of each element, then returns the vector

size()

template<typename I >

auto MR::UnionFind< I >::size ( ) const

inline

returns the number of elements in union-find

sizeOfComp()

template<typename I >

SizeType MR::UnionFind< I >::sizeOfComp ( I a )

inline

returns the number of elements in the set containing given element

unite()

template<typename I >

std::pair< I, bool > MR::UnionFind< I >::unite ( I first, I second )

inline

unite two elements,

Returns

first: new common root, second: true = union was done, false = first and second were already united

select root by size for best performance

united()

template<typename I >

bool MR::UnionFind< I >::united ( I first, I second )

inline

returns true if given two elements are from one set

---

The documentation for this class was generated from the following files:

• MRMesh/MRMeshFwd.h
• MRUnionFind.h