mlpack 3.4.2
union_find.hpp
Go to the documentation of this file.
1
15#ifndef MLPACK_METHODS_EMST_UNION_FIND_HPP
16#define MLPACK_METHODS_EMST_UNION_FIND_HPP
17
18#include <mlpack/prereqs.hpp>
19
20namespace mlpack {
21namespace emst {
22
31{
32 private:
33 arma::Col<size_t> parent;
34 arma::ivec rank;
35
36 public:
38 UnionFind(const size_t size) : parent(size), rank(size)
39 {
40 for (size_t i = 0; i < size; ++i)
41 {
42 parent[i] = i;
43 rank[i] = 0;
44 }
45 }
46
49
56 size_t Find(const size_t x)
57 {
58 if (parent[x] == x)
59 {
60 return x;
61 }
62 else
63 {
64 // This ensures that the tree has a small depth.
65 parent[x] = Find(parent[x]);
66 return parent[x];
67 }
68 }
69
76 void Union(const size_t x, const size_t y)
77 {
78 const size_t xRoot = Find(x);
79 const size_t yRoot = Find(y);
80
81 if (xRoot == yRoot)
82 {
83 return;
84 }
85 else if (rank[xRoot] == rank[yRoot])
86 {
87 parent[yRoot] = parent[xRoot];
88 rank[xRoot] = rank[xRoot] + 1;
89 }
90 else if (rank[xRoot] > rank[yRoot])
91 {
92 parent[yRoot] = xRoot;
93 }
94 else
95 {
96 parent[xRoot] = yRoot;
97 }
98 }
99}; // class UnionFind
100
101} // namespace emst
102} // namespace mlpack
103
104#endif // MLPACK_METHODS_EMST_UNION_FIND_HPP
A Union-Find data structure.
Definition: union_find.hpp:31
size_t Find(const size_t x)
Returns the component containing an element.
Definition: union_find.hpp:56
void Union(const size_t x, const size_t y)
Union the components containing x and y.
Definition: union_find.hpp:76
UnionFind(const size_t size)
Construct the object with the given size.
Definition: union_find.hpp:38
~UnionFind()
Destroy the object (nothing to do).
Definition: union_find.hpp:48
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: cv.hpp:1
The core includes that mlpack expects; standard C++ includes and Armadillo.