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

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

MRUnionFind.h

Public Types

Public Member Functions

Detailed Description