All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
NetworKit::UnionFind Class Reference

Implements the Union Find data structure to maintain disjoint sets efficiently. More...

#include <UnionFind.h>

Public Member Functions

 UnionFind (index max_element)
 Create a new set representation with not more the elements. More...
 
void allToSingletons ()
 Assigns every element to a singleton set. More...
 
index find (index u)
 Find the representative to element . More...
 
void merge (index u, index v)
 Merge the two sets contain and . More...
 
Partition toPartition ()
 Convert the Union Find data structure to a Partition. More...
 

Detailed Description

Implements the Union Find data structure to maintain disjoint sets efficiently.

Uses path compression and union by rank to achieve running time linear in the number of elements times the inverse Ackermann function.

Constructor & Destructor Documentation

NetworKit::UnionFind::UnionFind ( index  max_element)
inline

Create a new set representation with not more the elements.

Initially every element is in its own set.

Parameters
max_elementmaximum number of elements

Member Function Documentation

void NetworKit::UnionFind::allToSingletons ( )

Assigns every element to a singleton set.

Set id is equal to element id.

index NetworKit::UnionFind::find ( index  u)

Find the representative to element .

Parameters
uelement
Returns
representative of set containing
void NetworKit::UnionFind::merge ( index  u,
index  v 
)

Merge the two sets contain and .

Parameters
uelement u
velement v
Partition NetworKit::UnionFind::toPartition ( )

Convert the Union Find data structure to a Partition.

Returns
Partition equivalent to the union find data structure

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