DisjointSets< IndexType > Class Template Reference

Disjoint sets computation. More...

#include <lagrange/utils/DisjointSets.h>

Inherited by DisjointSetsWithSize< IndexType >.

Public Member Functions
	DisjointSets ()=default
	Initialize an empty disjoint sets.
	DisjointSets (size_t n)
	Initialize disjoint sets that contains n entries. More...
void	init (size_t n)
	Initialize disjoint sets that contains n entries. More...
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. More...
IndexType	merge (IndexType i, IndexType j)
	Merge the disjoint set containing entry i and the disjoint set containing entry j. More...
std::vector< std::vector< IndexType > >	extract_disjoint_sets ()
	Extract disjoint sets. More...
size_t	extract_disjoint_set_indices (std::vector< IndexType > &index_map)
	Assign all elements their disjoint set index. More...
size_t	extract_disjoint_set_indices (span< IndexType > index_map)
	Assign all elements their disjoint set index. More...

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()

DisjointSets ( size_t  n )

inlineexplicit

Initialize disjoint sets that contains n entries.

Parameters

[in]

n

The number of entries.

Member Function Documentation

init()

void init

(

size_t

n

)

Initialize disjoint sets that contains n entries.

Parameters

[in]

n

The number of entries.

find()

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()

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()

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]

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]

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