Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
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.
 
DisjointSetsoperator= (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.
 
intm_parameters
 Maps set id to rank/size.
 
intm_parents
 Maps set id to parent set id.
 
intm_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
maxNumberOfElementsExpected 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]

Definition at line 374 of file DisjointSets.h.

◆ find() [2/7]

Definition at line 365 of file DisjointSets.h.

◆ find() [3/7]

Definition at line 310 of file DisjointSets.h.

◆ find() [4/7]

Definition at line 324 of file DisjointSets.h.

◆ find() [5/7]

Definition at line 336 of file DisjointSets.h.

◆ find() [6/7]

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
setSet.
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
setSet.
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]

Definition at line 381 of file DisjointSets.h.

◆ quickUnion() [2/6]

Definition at line 437 of file DisjointSets.h.

◆ quickUnion() [3/6]

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]

◆ quickUnion() [5/6]

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: