All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UnionFind.h
Go to the documentation of this file.
1 /*
2  * UnionFind.h
3  *
4  * Created on: 11.08.2014
5  * Author: Marcel Radermacher
6  * Changed a bit by Henning Meyerhenke to reflect union by rank and path compression
7  * as taught in "Algorithms 1"
8  */
9 
10 #ifndef UNIONFIND_H_
11 #define UNIONFIND_H_
12 
13 #include <vector>
14 #include "../Globals.h"
15 #include "../structures/Partition.h"
16 
17 namespace NetworKit {
18 
25 class UnionFind {
26 private:
27  std::vector<index> parent;
28  std::vector<unsigned char> rank;
29 public:
30 
36  UnionFind(index max_element) : parent(max_element), rank(max_element, 0) {
38  }
39 
45  void allToSingletons();
46 
52  index find(index u);
53 
59  void merge(index u, index v);
60 
66 };
67 }
68 #endif
index find(index u)
Find the representative to element .
Definition: UnionFind.cpp:21
uint64_t index
Typedefs.
Definition: Globals.h:20
void allToSingletons()
Assigns every element to a singleton set.
Definition: UnionFind.cpp:15
UnionFind(index max_element)
Create a new set representation with not more the elements.
Definition: UnionFind.h:36
Implements a partition of a set, i.e.
Definition: Partition.h:31
void merge(index u, index v)
Merge the two sets contain and .
Definition: UnionFind.cpp:32
Implements the Union Find data structure to maintain disjoint sets efficiently.
Definition: UnionFind.h:25
Partition toPartition()
Convert the Union Find data structure to a Partition.
Definition: UnionFind.cpp:48