pbat::graph::DisjointSetUnionFind< TIndex > Class Template Reference

Disjoint Set Union-Find data structure. More...

#include <DisjointSetUnionFind.h>

Public Types
using	IndexType = TIndex
	Index type used in the disjoint set union-find structure.

Public Member Functions
	DisjointSetUnionFind (IndexType n)
	Construct a new Disjoint Set Union-Find object.
void	Prepare (IndexType n)
	Reserve memory for n vertices and reset the structure.
IndexType	Find (IndexType u)
	Find the root of the set containing vertex u
IndexType	Union (IndexType u, IndexType v)
	Merge the sets containing vertices u and v
IndexType	Root (IndexType u) const
	Find the root of the set containing vertex u without path compression.
IndexType	Size (IndexType u) const
	Find the size of the set containing vertex u
IndexType	NumVertices () const
	Get the number of vertices in the disjoint set union-find structure.

Detailed Description

template<common::CIndex TIndex = Index>
class pbat::graph::DisjointSetUnionFind< TIndex >

Disjoint Set Union-Find data structure.

Template Parameters

TIndex

Index type used in the disjoint set union-find structure.

This class implements a disjoint set union-find data structure with path compression and union by rank. It is used to efficiently manage and merge disjoint sets, which is useful in various graph algorithms.

Constructor & Destructor Documentation

DisjointSetUnionFind()

template<common::CIndex TIndex>

pbat::graph::DisjointSetUnionFind< TIndex >::DisjointSetUnionFind

(

IndexType

n

)

Construct a new Disjoint Set Union-Find object.

Parameters

n	Number of vertices

Member Function Documentation

Find()

template<common::CIndex TIndex>

TIndex pbat::graph::DisjointSetUnionFind< TIndex >::Find

(

IndexType

u

)

Find the root of the set containing vertex u

Parameters

u	Vertex index

Returns

Root of the set containing vertex u

NumVertices()

template<common::CIndex TIndex>

TIndex pbat::graph::DisjointSetUnionFind< TIndex >::NumVertices

(

)

const

Get the number of vertices in the disjoint set union-find structure.

Returns

Number of vertices

Prepare()

template<common::CIndex TIndex>

void pbat::graph::DisjointSetUnionFind< TIndex >::Prepare

(

IndexType

n

)

Reserve memory for n vertices and reset the structure.

Parameters

n	Number of vertices

Root()

template<common::CIndex TIndex>

TIndex pbat::graph::DisjointSetUnionFind< TIndex >::Root ( IndexType u ) const

inline

Find the root of the set containing vertex u without path compression.

Parameters

u	Vertex index

Returns

Root of the set containing vertex u

Size()

template<common::CIndex TIndex>

TIndex pbat::graph::DisjointSetUnionFind< TIndex >::Size

(

IndexType

u

)

const

Find the size of the set containing vertex u

Parameters

u	Vertex index

Returns

Size of the set containing vertex u

Union()

template<common::CIndex TIndex>

TIndex pbat::graph::DisjointSetUnionFind< TIndex >::Union	(	IndexType	u,
		IndexType	v )

Merge the sets containing vertices u and v

Parameters

u	Vertex index of the first set
v	Vertex index of the second set

Returns

Root of the merged tree

---

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

• C:/git/PhysicsBasedAnimationToolkit/source/pbat/graph/DisjointSetUnionFind.h