DisjointSets< IndexType > Class Template Reference

Disjoint sets computation. More...

#include <lagrange/utils/DisjointSets.h>

Inheritance diagram for DisjointSets< IndexType >:

Public Member Functions
	DisjointSets ()=default
	Initialize an empty disjoint sets.
	DisjointSets (size_t n)
	Initialize disjoint sets that contains n entries.
void	init (size_t n)
	Initialize disjoint sets that contains n entries.
size_t	size () const
	Get the number of entries in total.
void	clear ()
	Clear all entries in the disjoint sets.
IndexType	find (IndexType i)
	Find the root index corresponding to index i.
IndexType	merge (IndexType i, IndexType j)
	Merge the disjoint set containing entry i and the disjoint set containing entry j.
std::vector< std::vector< IndexType > >	extract_disjoint_sets ()
	Extract disjoint sets.
size_t	extract_disjoint_set_indices (std::vector< IndexType > &index_map)
	Assign all elements their disjoint set index.
size_t	extract_disjoint_set_indices (span< IndexType > index_map)
	Assign all elements their disjoint set index.

Protected Attributes
std::vector< IndexType >	m_parent

Detailed Description

template<typename IndexType>
class lagrange::DisjointSets< IndexType >

Disjoint sets computation.

Template Parameters

IndexType

Index type.

Constructor & Destructor Documentation

DisjointSets()

template<typename IndexType>

DisjointSets ( size_t n )

inlineexplicit

Initialize disjoint sets that contains n entries.

Parameters

[in]

n

The number of entries.

Member Function Documentation

init()

template<typename IndexType>

void init

(

size_t

n

)

Initialize disjoint sets that contains n entries.

Parameters

[in]

n

The number of entries.

find()

template<typename IndexType>

IndexType find

(

IndexType

i

)

Find the root index corresponding to index i.

Parameters

[in]

i

The qurey index.

Returns

The root index that is in the same disjoint set as entry i.

merge()

template<typename IndexType>

IndexType merge ( IndexType i, IndexType j )

inline

Merge the disjoint set containing entry i and the disjoint set containing entry j.

Parameters

[in]	i	Entry index i.
[in]	i	Entry index j.

Returns

The root entry index of the merged set.

extract_disjoint_sets()

template<typename IndexType>

std::vector< std::vector< IndexType > > extract_disjoint_sets

(

)

Extract disjoint sets.

Returns

A vector of disjoint sets.

Deprecated

This function is deprecated and may be removed in a future version.

extract_disjoint_set_indices() [1/2]

template<typename IndexType>

size_t extract_disjoint_set_indices

(

std::vector< IndexType > &

index_map

)

Assign all elements their disjoint set index.

Each disjoint set index ranges from 0 to k-1, where k is the number of disjoint sets.

Parameters

[out]

index_map

The result buffer to hold the index.

Returns

The number of disjoint sets.

extract_disjoint_set_indices() [2/2]

template<typename IndexType>

size_t extract_disjoint_set_indices

(

span< IndexType >

index_map

)

Assign all elements their disjoint set index.

Each disjoint set index ranges from 0 to k-1, where k is the number of disjoint sets.

Parameters

[out]

index_map

The result buffer to hold the index.

Returns

The number of disjoint sets.

---

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

• lagrange/utils/DisjointSets.h
• utils/DisjointSets.cpp