Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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. 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...
 
DisjointSetsoperator= (const DisjointSets &)=delete
 
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...
 

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 81 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
maxNumberOfElementsExpected number of Elements.

Definition at line 124 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 134 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 358 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 351 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 291 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 307 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 320 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 335 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
setSet.
Returns
Superset id
Precondition
set is a non negative properly initialized id.

Definition at line 169 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 260 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 257 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
setSet.
Returns
Superset id
Precondition
set is a non negative properly initialized id.

Definition at line 182 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 149 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 142 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 562 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 621 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 577 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 601 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 235 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 268 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 194 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 367 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 425 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 462 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 386 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 519 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 248 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 90 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 89 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 83 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 95 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 94 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 96 of file DisjointSets.h.


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