DisjointSets Class Reference

#include <dset.h>

Public Member Functions
	DisjointSets (uint32_t size)
uint32_t	find (uint32_t id) const
bool	same (uint32_t id1, uint32_t id2) const
uint32_t	unite (uint32_t id1, uint32_t id2)
bool	try_lock (uint32_t &id)
void	unlock (uint32_t id)
uint32_t	unite_index_locked (uint32_t id1, uint32_t id2) const
uint32_t	unite_unlock (uint32_t id1, uint32_t id2)
uint32_t	size () const
uint32_t	rank (uint32_t id) const
uint32_t	parent (uint32_t id) const
bool	isRoot (uint32_t id) const

Public Attributes
std::vector< std::atomic< uint64_t > >	mData

Detailed Description

Date

December 2025.

In this file is implemented a concurrent disjoint-set (also called union-find) data structure. It was implemented by Wenzel Jakob and comes from the following repository: https://github.com/wjakob/dset The code was slightly modified. Below can be found the license of the original code.

Related publication
"Wait-free Parallel Algorithms for the Union-Find Problem"
Richard J. Anderson and Heather Woll
STOC 1991. Lock-free parallel disjoint set data structure (aka UNION-FIND) with path compression and union by rank

Supports concurrent find(), same() and unite() calls as described in the paper

"Wait-free Parallel Algorithms for the Union-Find Problem" by Richard J. Anderson and Heather Woll

In addition, this class supports optimistic locking (try_lock/unlock) of disjoint sets and a combined unite+unlock operation.

Author

Wenzel Jakob

Definition at line 57 of file dset.h.

Constructor & Destructor Documentation

DisjointSets()

DisjointSets::DisjointSets ( uint32_t size )

inline

Definition at line 59 of file dset.h.

Member Function Documentation

find()

uint32_t DisjointSets::find ( uint32_t id ) const

inline

Definition at line 64 of file dset.h.

isRoot()

bool DisjointSets::isRoot ( uint32_t id ) const

inline

Definition at line 185 of file dset.h.

parent()

uint32_t DisjointSets::parent ( uint32_t id ) const

inline

Definition at line 181 of file dset.h.

rank()

uint32_t DisjointSets::rank ( uint32_t id ) const

inline

Definition at line 177 of file dset.h.

same()

bool DisjointSets::same ( uint32_t id1, uint32_t id2 ) const

inline

Definition at line 77 of file dset.h.

size()

uint32_t DisjointSets::size ( ) const

inline

Definition at line 173 of file dset.h.

try_lock()

bool DisjointSets::try_lock ( uint32_t & id )

inline

Try to lock the a disjoint union identified by one of its elements (this can occasionally fail when there are concurrent operations). The parameter 'id' will be updated to store the current representative ID of the union

Definition at line 128 of file dset.h.

unite()

uint32_t DisjointSets::unite ( uint32_t id1, uint32_t id2 )

inline

Definition at line 88 of file dset.h.

unite_index_locked()

uint32_t DisjointSets::unite_index_locked ( uint32_t id1, uint32_t id2 ) const

inline

Return the representative index of the set that results from merging locked disjoint sets 'id1' and 'id2'

Definition at line 150 of file dset.h.

unite_unlock()

uint32_t DisjointSets::unite_unlock ( uint32_t id1, uint32_t id2 )

inline

Atomically unite two locked disjoint sets and unlock them. Assumes that here are no other concurrent unite() involving the same sets

Definition at line 159 of file dset.h.

unlock()

void DisjointSets::unlock ( uint32_t id )

inline

Definition at line 141 of file dset.h.

Member Data Documentation

mData

std::vector<std::atomic<uint64_t> > DisjointSets::mData

mutable

Definition at line 189 of file dset.h.

---

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

• /home/julien/Pro/git/github/thomas/ttk-dani/core/base/delaunayRipsPersistenceDiagram/dset.h