KI_UNION_FIND Class Reference

Lock-free disjoint-set over a dense range of indices. More...

#include <union_find.h>

Public Member Functions
	KI_UNION_FIND (size_t aCount)
	KI_UNION_FIND (const KI_UNION_FIND &)=delete
KI_UNION_FIND &	operator= (const KI_UNION_FIND &)=delete
	Discard all unions and resize the set to aCount single-element components.
void	Reset (size_t aCount)
size_t	Size () const
size_t	ComponentCount () const
bool	Unite (size_t aA, size_t aB)
	Merge the components that hold aA and aB.
size_t	Find (size_t aX) const
size_t	FindCompress (size_t aX)
	Shorten the path from aX to its root so that later queries walk less of it.
bool	Connected (size_t aA, size_t aB) const

Private Attributes
std::vector< std::atomic< uint32_t > >	m_parent
std::atomic< size_t >	m_components { 0 }

Detailed Description

Lock-free disjoint-set over a dense range of indices.

Each tree is rooted at the smallest index it contains. Parent indices decrease along the path to a root. Unite() climbs both paths and advances the side with the larger parent, so the set needs no rank array and no lock.

Call Unite() from any number of threads. Find() and Connected() are safe against each other but not against Unite(), so complete all unions for a phase before you query.

Dhulipala, L., Hong, C., & Shun, J. (2021). ConnectIt: A framework for static and incremental parallel graph connectivity algorithms. Proceedings of the VLDB Endowment, 14(4), 653-667. https://doi.org/10.14778/3436905.3436923

Dijkstra, E. W. (1976). A Discipline of Programming. Prentice-Hall, Ch. 23.

Definition at line 47 of file union_find.h.

Constructor & Destructor Documentation

KI_UNION_FIND() [1/2]

KI_UNION_FIND::KI_UNION_FIND ( size_t aCount )

inlineexplicit

Definition at line 50 of file union_find.h.

References Reset().

Referenced by KI_UNION_FIND(), and operator=().

KI_UNION_FIND() [2/2]

KI_UNION_FIND::KI_UNION_FIND ( const KI_UNION_FIND & )

delete

References KI_UNION_FIND().

Member Function Documentation

ComponentCount()

size_t KI_UNION_FIND::ComponentCount ( ) const

inline

Definition at line 75 of file union_find.h.

References m_components.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and KI_MST::FilterKruskal().

Connected()

bool KI_UNION_FIND::Connected ( size_t aA, size_t aB ) const

inline

Definition at line 167 of file union_find.h.

References Find().

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and BOOST_AUTO_TEST_CASE().

Find()

size_t KI_UNION_FIND::Find ( size_t aX ) const

inline

Definition at line 130 of file union_find.h.

References m_parent.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), and Connected().

FindCompress()

size_t KI_UNION_FIND::FindCompress ( size_t aX )

inline

Shorten the path from aX to its root so that later queries walk less of it.

Do not call this while another thread is inside Unite().

Returns

the representative of the component that holds aX.

Definition at line 150 of file union_find.h.

References m_parent.

Referenced by BOOST_AUTO_TEST_CASE(), and CN_CONNECTIVITY_ALGO::SearchClusters().

operator=()

KI_UNION_FIND & KI_UNION_FIND::operator= ( const KI_UNION_FIND & )

delete

Discard all unions and resize the set to aCount single-element components.

References KI_UNION_FIND().

Reset()

void KI_UNION_FIND::Reset ( size_t aCount )

inline

Definition at line 56 of file union_find.h.

References m_components, and m_parent.

Referenced by BOOST_AUTO_TEST_CASE().

Size()

size_t KI_UNION_FIND::Size ( ) const

inline

Returns

the number of components that remain.

Definition at line 72 of file union_find.h.

References m_parent.

Referenced by BOOST_AUTO_TEST_CASE().

Unite()

bool KI_UNION_FIND::Unite ( size_t aA, size_t aB )

inline

Merge the components that hold aA and aB.

Returns

true if this call made the link. Exactly one caller sees true for each merge.

the representative of the component that holds aX.

Definition at line 82 of file union_find.h.

References expected, m_components, and m_parent.

Referenced by BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), BOOST_AUTO_TEST_CASE(), KI_MST::FilterKruskal(), RN_NET::kruskalMST(), and CN_CONNECTIVITY_ALGO::SearchClusters().

Member Data Documentation

m_components

std::atomic<size_t> KI_UNION_FIND::m_components { 0 }

private

Definition at line 171 of file union_find.h.

Referenced by ComponentCount(), Reset(), and Unite().

m_parent

std::vector<std::atomic<uint32_t> > KI_UNION_FIND::m_parent

private

Definition at line 170 of file union_find.h.

Referenced by Find(), FindCompress(), Reset(), Size(), and Unite().

---

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

• union_find.h