wilderfield::UnionFind< T > Class Template Reference

Union Find class. More...

#include <union_find.hpp>

Public Member Functions
void	InsertNode (T u)
	Insert a new node. More...
void	Union (T u, T v)
	Perform union operation on two nodes. More...
T	Find (T u)
	Find the representative of a node. More...
std::size_t	GetMaxRank () const
	Get the maximum rank in the union find structure. More...
std::size_t	GetNumComponents () const
	Get the number of connected components. More...

Protected Attributes
std::unordered_map< T, T >	parent_of_
std::unordered_map< T, size_t >	rank_of_
std::size_t	max_rank_ = 0
std::size_t	num_cc_ = 0

Detailed Description

template<typename T>
class wilderfield::UnionFind< T >

Union Find class.

Implements the union find data structure.

Template Parameters

T	The type used to label graph nodes.

Member Function Documentation

Find()

template<typename T >

T wilderfield::UnionFind< T >::Find ( T  u )

inline

Find the representative of a node.

Parameters

u	The node to find

Returns

The representative of the node

GetMaxRank()

template<typename T >

std::size_t wilderfield::UnionFind< T >::GetMaxRank ( ) const

inline

Get the maximum rank in the union find structure.

Returns

The maximum rank

GetNumComponents()

template<typename T >

std::size_t wilderfield::UnionFind< T >::GetNumComponents ( ) const

inline

Get the number of connected components.

Returns

The number of connected components

InsertNode()

template<typename T >

void wilderfield::UnionFind< T >::InsertNode ( T  u )

inline

Insert a new node.

Parameters

u	The node to insert

Union()

template<typename T >

void wilderfield::UnionFind< T >::Union ( T  u, T  v  )

inline

Perform union operation on two nodes.

Parameters

u	First node
v	Second node

---

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

• /home/runner/work/wilderfield/wilderfield/include/wilderfield/union_find.hpp