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 &)=delete
	DisjointSets (int maxNumberOfElements=(1<< 15))
	Creates an empty DisjointSets structure.
	~DisjointSets ()
int	find (int set)
	Returns the id of the largest superset of set and compresses the path according to CompressionOptions.
int	getNumberOfElements ()
	Returns the current number of elements.
int	getNumberOfSets ()
	Returns the current number of disjoint sets.
int	getRepresentative (int set) const
	Returns the id of the largest superset of set.
void	init ()
	Resets the DisjointSets structure to be empty, preserving the previous value of maxNumberOfElements.
void	init (int maxNumberOfElements)
	Resets the DisjointSets structure to be empty, also changing the expected number of elements.
int	link (int set1, int set2)
	Unions set1 and set2.
int	makeSet ()
	Initializes a singleton set.
DisjointSets &	operator= (const DisjointSets &)=delete
bool	quickUnion (int set1, int set2)
	Unions the maximal disjoint sets containing set1 and set2.

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.
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.
int	m_numberOfElements
	Current number of elements.
int	m_numberOfSets
	Current number of disjoint sets.
int *	m_parameters
	Maps set id to rank/size.
int *	m_parents
	Maps set id to parent set id.
int *	m_siblings
	Maps set id to sibling set id.

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 89 of file DisjointSets.h.

Constructor & Destructor Documentation

DisjointSets() [1/2]

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 145 of file DisjointSets.h.

DisjointSets() [2/2]

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

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

delete

~DisjointSets()

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

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

inline

Definition at line 154 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 374 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 365 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 310 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 324 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 336 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 350 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 188 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 283 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 280 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 200 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 167 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 161 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 554 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 602 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 566 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 585 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 255 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 291 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 213 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= ( const DisjointSets< linkOption, compressionOption, interleavingOption > &  )

delete

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 381 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 437 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 467 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 399 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 520 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 269 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 104 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 103 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 102 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 109 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 108 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 110 of file DisjointSets.h.

---

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

• include/ogdf/basic/DisjointSets.h