Blender V5.3
BLI_disjoint_set.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#pragma once
6
12
13#include "BLI_array.hh"
14#include "BLI_index_range.hh"
15
16namespace blender {
17
18template<typename T = int64_t> class DisjointSet {
19 private:
20 Array<T> parents_;
21 Array<T> ranks_;
22
23 public:
27 DisjointSet(const int64_t size) : parents_(size), ranks_(size, 0)
28 {
29 BLI_assert(size >= 0);
30 for (const int64_t i : IndexRange(size)) {
31 parents_[i] = T(i);
32 }
33 }
34
39 T join(const T x, const T y)
40 {
41 T root1 = this->find_root(x);
42 T root2 = this->find_root(y);
43
44 /* x and y are in the same set already. */
45 if (root1 == root2) {
46 return root1;
47 }
48
49 /* Implement union by rank heuristic. */
50 if (ranks_[root1] < ranks_[root2]) {
51 std::swap(root1, root2);
52 }
53 parents_[root2] = root1;
54
55 if (ranks_[root1] == ranks_[root2]) {
56 ranks_[root1]++;
57 }
58
59 return root1;
60 }
61
65 bool in_same_set(const T x, const T y)
66 {
67 T root1 = this->find_root(x);
68 T root2 = this->find_root(y);
69 return root1 == root2;
70 }
71
75 T find_root(const T x)
76 {
77 /* Find root by following parents. */
78 T root = x;
79 while (parents_[root] != root) {
80 root = parents_[root];
81 }
82
83 /* Compress path. */
84 T to_root = x;
85 while (parents_[to_root] != root) {
86 const T parent = parents_[to_root];
87 parents_[to_root] = root;
88 to_root = parent;
89 }
90
91 return root;
92 }
93
98 T find_root(const T x) const
99 {
100 /* Find root by following parents. */
101 T root = x;
102 while (parents_[root] != root) {
103 root = parents_[root];
104 }
105
106 return root;
107 }
108};
109
110} // namespace blender
T join(const T x, const T y)
DisjointSet(const int64_t size)
bool in_same_set(const T x, const T y)
T find_root(const T x) const
constexpr IndexRange()=default
#define T
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90