Union-find data structure for representing disjoint 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. Sequential implementation that selects the root of a united pair by set size for best performance. More...

#include <MRMesh/MRUnionFind.h>

Inheritance diagram for MR::UnionFind< I >:

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 Types inherited from MR::BaseUnionFind< I >
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
	UnionFind (BaseUnionFind< I > &&base)
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)
SizeType	sizeOfComp (I a)
	returns the number of elements in the set containing given element
Public Member Functions inherited from MR::BaseUnionFind< I >
	BaseUnionFind ()=default
	BaseUnionFind (const BaseUnionFind &)=default
	BaseUnionFind (BaseUnionFind &&) noexcept=default
BaseUnionFind &	operator= (const BaseUnionFind &)=default
BaseUnionFind &	operator= (BaseUnionFind &&) noexcept=default
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 >	uniteUnbalanced (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

Additional Inherited Members
Protected Member Functions inherited from MR::BaseUnionFind< I >
I	findRootNoUpdate_ (I a) const
	finds the root of the set containing given element without optimizing data structure updates
I	updateRoot_ (I a, const I r)
	sets new root
I	updateRoot_ (I a)
	find the root of given element, and set it as parent for it and other parents
I	updateRootInRange_ (I a, const I r, I begin, I end)
	sets new root
Protected Attributes inherited from MR::BaseUnionFind< I >
Vector< I, I >	parents_
	parent element of each element

Detailed Description

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

Union-find data structure for representing disjoint 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. Sequential implementation that selects the root of a united pair by set size for best performance.

Template Parameters

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

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

MRMesh/MRMeshFwd.h
MRMesh/MRUnionFind.h

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description