Blender
V5.3
source
blender
blenlib
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
16
namespace
blender
{
17
18
template
<
typename
T =
int
64_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
BLI_array.hh
BLI_index_range.hh
blender::Array
Definition
BLI_array.hh:50
blender::DisjointSet::join
T join(const T x, const T y)
Definition
BLI_disjoint_set.hh:39
blender::DisjointSet::DisjointSet
DisjointSet(const int64_t size)
Definition
BLI_disjoint_set.hh:27
blender::DisjointSet::find_root
T find_root(const T x)
Definition
BLI_disjoint_set.hh:75
blender::DisjointSet::in_same_set
bool in_same_set(const T x, const T y)
Definition
BLI_disjoint_set.hh:65
blender::DisjointSet::find_root
T find_root(const T x) const
Definition
BLI_disjoint_set.hh:98
blender::IndexRange::IndexRange
constexpr IndexRange()=default
y
y
Definition
compositor_morphological_blur_infos.hh:32
T
#define T
Definition
mball_tessellate.cc:277
blender
BMesh Iterators.
Definition
ANIM_action.hh:30
blender::BLI_assert
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
blender::int64_t
__int64 int64_t
Definition
BKE_text.h:90
blender::x
x
Definition
BLI_expr_pylike_eval_test.cc:347
Generated on
for Blender by
doxygen
1.18.0