mlpack  2.0.1
union_find.hpp
Go to the documentation of this file.
1 
17 #ifndef __MLPACK_METHODS_EMST_UNION_FIND_HPP
18 #define __MLPACK_METHODS_EMST_UNION_FIND_HPP
19 
20 #include <mlpack/core.hpp>
21 
22 namespace mlpack {
23 namespace emst {
24 
32 class UnionFind
33 {
34  private:
35  arma::Col<size_t> parent;
36  arma::ivec rank;
37 
38  public:
40  UnionFind(const size_t size) : parent(size), rank(size)
41  {
42  for (size_t i = 0; i < size; ++i)
43  {
44  parent[i] = i;
45  rank[i] = 0;
46  }
47  }
48 
50  ~UnionFind() { }
51 
58  size_t Find(const size_t x)
59  {
60  if (parent[x] == x)
61  {
62  return x;
63  }
64  else
65  {
66  // This ensures that the tree has a small depth
67  parent[x] = Find(parent[x]);
68  return parent[x];
69  }
70  }
71 
78  void Union(const size_t x, const size_t y)
79  {
80  const size_t xRoot = Find(x);
81  const size_t yRoot = Find(y);
82 
83  if (xRoot == yRoot)
84  {
85  return;
86  }
87  else if (rank[xRoot] == rank[yRoot])
88  {
89  parent[yRoot] = parent[xRoot];
90  rank[xRoot] = rank[xRoot] + 1;
91  }
92  else if (rank[xRoot] > rank[yRoot])
93  {
94  parent[yRoot] = xRoot;
95  }
96  else
97  {
98  parent[xRoot] = yRoot;
99  }
100  }
101 }; // class UnionFind
102 
103 } // namespace emst
104 } // namespace mlpack
105 
106 #endif // __MLPACK_METHODS_EMST_UNION_FIND_HPP
UnionFind(const size_t size)
Construct the object with the given size.
Definition: union_find.hpp:40
A Union-Find data structure.
Definition: union_find.hpp:32
arma::Col< size_t > parent
Definition: union_find.hpp:35
Linear algebra utility functions, generally performed on matrices or vectors.
void Union(const size_t x, const size_t y)
Union the components containing x and y.
Definition: union_find.hpp:78
size_t Find(const size_t x)
Returns the component containing an element.
Definition: union_find.hpp:58
Include all of the base components required to write MLPACK methods, and the main MLPACK Doxygen docu...
~UnionFind()
Destroy the object (nothing to do).
Definition: union_find.hpp:50