MR::UnionFind< I > Class Template Reference

Simple union find data structure. More...

#include <MRUnionFind.h>

Public Member Functions
	UnionFind ()=default
	UnionFind (size_t size)
auto	size () const
void	reset (size_t size)
	reset roots to represent each element as disjoint set of rank 0
std::pair< I, bool >	unite (I first, I second)
bool	united (I first, I second)
	returns true if given two elements are from one component
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 as the parent of each element, then returns the vector
const Vector< I, I > &	parents () const
	gets the parents of all elements as in
size_t	sizeOfComp (I a)
	returns the size of component containing given element

Detailed Description

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

Simple union find data structure.

Template Parameters

I	is an id type, e.g. FaceId

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

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)

parents()

template<typename I >

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

inline

gets the parents of all elements as in

reset()

template<typename I >

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

inline

reset roots to represent each element as disjoint set of rank 0

roots()

template<typename I >

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

inline

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

size()

template<typename I >

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

inline

sizeOfComp()

template<typename I >

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

inline

returns the size of component 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 component

---

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

• MRMesh/MRMeshFwd.h
• MRUnionFind.h