ogdf::DisjointSets< linkOption, compressionOption, interleavingOption > Class Template Reference

A Union/Find data structure for maintaining disjoint sets. More...

#include <ogdf/basic/DisjointSets.h>

Public Member Functions
	DisjointSets (const DisjointSets &copy)
	DisjointSets (DisjointSets &&move) noexcept
	DisjointSets (int maxNumberOfElements=(1<< 15))
	Creates an empty DisjointSets structure. More...
	~DisjointSets ()
int	find (int set)
	Returns the id of the largest superset of set and compresses the path according to CompressionOptions. More...
int	getNumberOfElements ()
	Returns the current number of elements. More...
int	getNumberOfSets ()
	Returns the current number of disjoint sets. More...
int	getRepresentative (int set) const
	Returns the id of the largest superset of set. More...
void	init ()
	Resets the DisjointSets structure to be empty, preserving the previous value of maxNumberOfElements. More...
void	init (int maxNumberOfElements)
	Resets the DisjointSets structure to be empty, also changing the expected number of elements. More...
int	link (int set1, int set2)
	Unions set1 and set2. More...
int	makeSet ()
	Initializes a singleton set. More...
DisjointSets &	operator= (DisjointSets copy_by_value) noexcept
	Assign this DisjointSets to be a copy of copy_by_value. More...
bool	quickUnion (int set1, int set2)
	Unions the maximal disjoint sets containing set1 and set2. More...

Private Member Functions
int	find (disjoint_sets::CompressionOption< CompressionOptions::Collapsing >, int set)
int	find (disjoint_sets::CompressionOption< CompressionOptions::Disabled >, int set)
int	find (disjoint_sets::CompressionOption< CompressionOptions::PathCompression >, int set)
int	find (disjoint_sets::CompressionOption< CompressionOptions::PathHalving >, int set)
int	find (disjoint_sets::CompressionOption< CompressionOptions::PathSplitting >, int set)
int	find (disjoint_sets::CompressionOption< CompressionOptions::Type1Reversal >, int set)
int	link (disjoint_sets::LinkOption< LinkOptions::Index >, int set1, int set2)
int	link (disjoint_sets::LinkOption< LinkOptions::Naive >, int set1, int set2)
int	link (disjoint_sets::LinkOption< LinkOptions::Rank >, int set1, int set2)
int	link (disjoint_sets::LinkOption< LinkOptions::Size >, int set1, int set2)
int	linkPure (int set1, int set2)
	Unions set1 and set2 w/o decreasing the numberOfSets. More...
bool	quickUnion (disjoint_sets::AnyOption, disjoint_sets::InterleavingOption< InterleavingOptions::Disabled >, int set1, int set2)
bool	quickUnion (disjoint_sets::LinkOption< LinkOptions::Index >, disjoint_sets::InterleavingOption< InterleavingOptions::Rem >, int set1, int set2)
bool	quickUnion (disjoint_sets::LinkOption< LinkOptions::Index >, disjoint_sets::InterleavingOption< InterleavingOptions::SplittingCompression >, int set1, int set2)
bool	quickUnion (disjoint_sets::LinkOption< LinkOptions::Naive >, disjoint_sets::InterleavingOption< InterleavingOptions::Type0Reversal >, int set1, int set2)
bool	quickUnion (disjoint_sets::LinkOption< LinkOptions::Rank >, disjoint_sets::InterleavingOption< InterleavingOptions::Tarjan >, int set1, int set2)

Private Attributes
int	m_maxNumberOfElements
	Maximum number of elements (array size) adjusted dynamically. More...
int	m_numberOfElements
	Current number of elements. More...
int	m_numberOfSets
	Current number of disjoint sets. More...
int *	m_parameters
	Maps set id to rank/size. More...
int *	m_parents
	Maps set id to parent set id. More...
int *	m_siblings
	Maps set id to sibling set id. More...

Friends
void	swap (DisjointSets &first, DisjointSets &second) noexcept

Detailed Description

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>
class ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >

A Union/Find data structure for maintaining disjoint sets.

Definition at line 90 of file DisjointSets.h.

Constructor & Destructor Documentation

DisjointSets() [1/3]

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::DisjointSets ( int  maxNumberOfElements = (1 << 15) )

inlineexplicit

Creates an empty DisjointSets structure.

Parameters

maxNumberOfElements

Expected number of Elements.

Definition at line 146 of file DisjointSets.h.

~DisjointSets()

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::~DisjointSets ( )

inline

Definition at line 151 of file DisjointSets.h.

DisjointSets() [2/3]

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::DisjointSets ( const DisjointSets< linkOption, compressionOption, interleavingOption > &  copy )

inline

Definition at line 157 of file DisjointSets.h.

DisjointSets() [3/3]

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::DisjointSets ( DisjointSets< linkOption, compressionOption, interleavingOption > &&  move )

inlinenoexcept

Definition at line 180 of file DisjointSets.h.

Member Function Documentation

find() [1/7]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::find ( disjoint_sets::CompressionOption< CompressionOptions::Collapsing >  , int  set  )

private

Definition at line 396 of file DisjointSets.h.

find() [2/7]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::find ( disjoint_sets::CompressionOption< CompressionOptions::Disabled >  , int  set  )

private

Definition at line 387 of file DisjointSets.h.

find() [3/7]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::find ( disjoint_sets::CompressionOption< CompressionOptions::PathCompression >  , int  set  )

private

Definition at line 332 of file DisjointSets.h.

find() [4/7]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::find ( disjoint_sets::CompressionOption< CompressionOptions::PathHalving >  , int  set  )

private

Definition at line 346 of file DisjointSets.h.

find() [5/7]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::find ( disjoint_sets::CompressionOption< CompressionOptions::PathSplitting >  , int  set  )

private

Definition at line 358 of file DisjointSets.h.

find() [6/7]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::find ( disjoint_sets::CompressionOption< CompressionOptions::Type1Reversal >  , int  set  )

private

Definition at line 372 of file DisjointSets.h.

find() [7/7]

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::find ( int  set )

inline

Returns the id of the largest superset of set and compresses the path according to CompressionOptions.

Parameters

set

Set.

Returns

Superset id

Precondition

set is a non negative properly initialized id.

Definition at line 210 of file DisjointSets.h.

getNumberOfElements()

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::getNumberOfElements ( )

inline

Returns the current number of elements.

Definition at line 305 of file DisjointSets.h.

getNumberOfSets()

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::getNumberOfSets ( )

inline

Returns the current number of disjoint sets.

Definition at line 302 of file DisjointSets.h.

getRepresentative()

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::getRepresentative ( int  set ) const

inline

Returns the id of the largest superset of set.

Parameters

set

Set.

Returns

Superset id

Precondition

set is a non negative properly initialized id.

Definition at line 222 of file DisjointSets.h.

init() [1/2]

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

void ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::init ( )

inline

Resets the DisjointSets structure to be empty, preserving the previous value of maxNumberOfElements.

Definition at line 189 of file DisjointSets.h.

init() [2/2]

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

void ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::init ( int  maxNumberOfElements )

inline

Resets the DisjointSets structure to be empty, also changing the expected number of elements.

Definition at line 183 of file DisjointSets.h.

link() [1/5]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::link ( disjoint_sets::LinkOption< LinkOptions::Index >  , int  set1, int  set2  )

private

Definition at line 576 of file DisjointSets.h.

link() [2/5]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::link ( disjoint_sets::LinkOption< LinkOptions::Naive >  , int  set1, int  set2  )

private

Definition at line 624 of file DisjointSets.h.

link() [3/5]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::link ( disjoint_sets::LinkOption< LinkOptions::Rank >  , int  set1, int  set2  )

private

Definition at line 588 of file DisjointSets.h.

link() [4/5]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::link ( disjoint_sets::LinkOption< LinkOptions::Size >  , int  set1, int  set2  )

private

Definition at line 607 of file DisjointSets.h.

link() [5/5]

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::link ( int  set1, int  set2  )

inline

Unions set1 and set2.

Precondition

set1 and set2 are maximal disjoint sets.

Returns

Set id of the union.

Definition at line 277 of file DisjointSets.h.

linkPure()

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::linkPure ( int  set1, int  set2  )

inlineprivate

Unions set1 and set2 w/o decreasing the numberOfSets.

Precondition

set1 and set2 are maximal disjoint sets.

Returns

Set id of the union

Definition at line 313 of file DisjointSets.h.

makeSet()

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::makeSet ( )

inline

Initializes a singleton set.

Returns

Set id of the initialized singleton set.

Definition at line 235 of file DisjointSets.h.

operator=()

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

DisjointSets& ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::operator= ( DisjointSets< linkOption, compressionOption, interleavingOption >  copy_by_value )

inlinenoexcept

Assign this DisjointSets to be a copy of copy_by_value.

Internally, this will use the copy constructor to create a temporary copy of the argument copy_by_value (as it is passed by value) and then swap this object instance with the temporary copy. If the assigned-from object can be moved, the move constructor will be automatically used instead of copying. Note that this method thereby covers both copy-assignment and move-assignment. See https://stackoverflow.com/a/3279550 for more details on this idiom. This method is noexcept as a potentially-throwing copy constructor call is made within the context of the caller (see https://stackoverflow.com/a/7628345) and swap is expected to be noexcept.

Definition at line 180 of file DisjointSets.h.

quickUnion() [1/6]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

bool ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::quickUnion ( disjoint_sets::AnyOption  , disjoint_sets::InterleavingOption< InterleavingOptions::Disabled >  , int  set1, int  set2  )

private

Definition at line 403 of file DisjointSets.h.

quickUnion() [2/6]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

bool ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::quickUnion ( disjoint_sets::LinkOption< LinkOptions::Index >  , disjoint_sets::InterleavingOption< InterleavingOptions::Rem >  , int  set1, int  set2  )

private

Definition at line 459 of file DisjointSets.h.

quickUnion() [3/6]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

bool ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::quickUnion ( disjoint_sets::LinkOption< LinkOptions::Index >  , disjoint_sets::InterleavingOption< InterleavingOptions::SplittingCompression >  , int  set1, int  set2  )

private

Use path splitting to compress the path of set1 and get the root

Redirect all nodes with smaller indices on the path of set2 to the root

Definition at line 489 of file DisjointSets.h.

quickUnion() [4/6]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

bool ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::quickUnion ( disjoint_sets::LinkOption< LinkOptions::Naive >  , disjoint_sets::InterleavingOption< InterleavingOptions::Type0Reversal >  , int  set1, int  set2  )

private

Definition at line 421 of file DisjointSets.h.

quickUnion() [5/6]

template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>

bool ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::quickUnion ( disjoint_sets::LinkOption< LinkOptions::Rank >  , disjoint_sets::InterleavingOption< InterleavingOptions::Tarjan >  , int  set1, int  set2  )

private

Definition at line 542 of file DisjointSets.h.

quickUnion() [6/6]

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

bool ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::quickUnion ( int  set1, int  set2  )

inline

Unions the maximal disjoint sets containing set1 and set2.

Returns

True, if the maximal sets containing set1 and set2 were disjoint und joined correctly. False otherwise.

Definition at line 291 of file DisjointSets.h.

Friends And Related Function Documentation

swap

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

void swap ( DisjointSets< linkOption, compressionOption, interleavingOption > &  first, DisjointSets< linkOption, compressionOption, interleavingOption > &  second  )

friend

Definition at line 171 of file DisjointSets.h.

Member Data Documentation

m_maxNumberOfElements

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::m_maxNumberOfElements

private

Maximum number of elements (array size) adjusted dynamically.

Definition at line 105 of file DisjointSets.h.

m_numberOfElements

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::m_numberOfElements

private

Current number of elements.

Definition at line 104 of file DisjointSets.h.

m_numberOfSets

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::m_numberOfSets

private

Current number of disjoint sets.

Definition at line 92 of file DisjointSets.h.

m_parameters

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int* ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::m_parameters

private

Maps set id to rank/size.

Definition at line 110 of file DisjointSets.h.

m_parents

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int* ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::m_parents

private

Maps set id to parent set id.

Definition at line 109 of file DisjointSets.h.

m_siblings

template<LinkOptions linkOption = LinkOptions::Index, CompressionOptions compressionOption = CompressionOptions::PathSplitting, InterleavingOptions interleavingOption = InterleavingOptions::Disabled>

int* ogdf::DisjointSets< linkOption, compressionOption, interleavingOption >::m_siblings

private

Maps set id to sibling set id.

Definition at line 111 of file DisjointSets.h.

---

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

• include/ogdf/basic/DisjointSets.h