TTK
Loading...
Searching...
No Matches
UnionFind.h
Go to the documentation of this file.
1
7
8#pragma once
9
10#include <Debug.h>
11
12#include <algorithm>
13#include <vector>
14
15namespace ttk {
16
17 class UnionFind : virtual public Debug {
18
19 public:
20 // 1) constructors, destructors, operators
21 inline UnionFind();
22
23 inline UnionFind(const UnionFind &other);
24
25 inline bool operator<(const UnionFind &other) const {
26 return rank_ < other.rank_;
27 }
28
29 inline bool operator>(const UnionFind &other) const {
30 return rank_ > other.rank_;
31 }
32
33 // 2) functions
34 inline UnionFind *find();
35
36 inline int getRank() const {
37 return rank_;
38 }
39
40 static inline UnionFind *makeUnion(UnionFind *uf0, UnionFind *uf1) {
41 uf0 = uf0->find();
42 uf1 = uf1->find();
43
44 if(uf0 == uf1) {
45 return uf0;
46 } else if(uf0->getRank() > uf1->getRank()) {
47 uf1->setParent(uf0);
48 return uf0;
49 } else if(uf0->getRank() < uf1->getRank()) {
50 uf0->setParent(uf1);
51 return uf1;
52 } else {
53 uf1->setParent(uf0);
54 uf0->setRank(uf0->getRank() + 1);
55 return uf0;
56 }
57 }
58
59 static inline UnionFind *makeUnion(std::vector<UnionFind *> &sets) {
60 UnionFind *n = nullptr;
61
62 if(!sets.size())
63 return nullptr;
64
65 if(sets.size() == 1)
66 return sets[0];
67
68 for(int i = 0; i < (int)sets.size() - 1; i++)
69 n = makeUnion(sets[i], sets[i + 1]);
70
71 return n;
72 }
73
74 inline void setParent(UnionFind *parent) {
75 parent_ = parent;
76 }
77
78 inline void setRank(const int &rank) {
79 rank_ = rank;
80 }
81
82 protected:
83 int rank_{};
85 };
86
88
89 rank_ = 0;
90 parent_ = this;
91 }
92
93 inline UnionFind::UnionFind(const UnionFind &other) : Debug(other) {
94
95 rank_ = other.rank_;
96 parent_ = this;
97 }
98
100
101 if(parent_ == this)
102 return this;
103 else {
104 parent_ = parent_->find();
105 return parent_;
106 }
107 }
108
109} // namespace ttk
Minimalist debugging class.
Definition Debug.h:88
Union Find implementation for connectivity tracking.
Definition UnionFind.h:17
bool operator<(const UnionFind &other) const
Definition UnionFind.h:25
bool operator>(const UnionFind &other) const
Definition UnionFind.h:29
void setRank(const int &rank)
Definition UnionFind.h:78
UnionFind * parent_
Definition UnionFind.h:84
static UnionFind * makeUnion(UnionFind *uf0, UnionFind *uf1)
Definition UnionFind.h:40
int getRank() const
Definition UnionFind.h:36
UnionFind * find()
Definition UnionFind.h:99
void setParent(UnionFind *parent)
Definition UnionFind.h:74
static UnionFind * makeUnion(std::vector< UnionFind * > &sets)
Definition UnionFind.h:59
The Topology ToolKit.