MLPACK  1.0.10
union_find.hpp
Go to the documentation of this file.
1 
25 #ifndef __MLPACK_METHODS_EMST_UNION_FIND_HPP
26 #define __MLPACK_METHODS_EMST_UNION_FIND_HPP
27 
28 #include <mlpack/core.hpp>
29 
30 namespace mlpack {
31 namespace emst {
32 
40 class UnionFind
41 {
42  private:
43  arma::Col<size_t> parent;
44  arma::ivec rank;
45 
46  public:
48  UnionFind(const size_t size) : parent(size), rank(size)
49  {
50  for (size_t i = 0; i < size; ++i)
51  {
52  parent[i] = i;
53  rank[i] = 0;
54  }
55  }
56 
58  ~UnionFind() { }
59 
66  size_t Find(const size_t x)
67  {
68  if (parent[x] == x)
69  {
70  return x;
71  }
72  else
73  {
74  // This ensures that the tree has a small depth
75  parent[x] = Find(parent[x]);
76  return parent[x];
77  }
78  }
79 
86  void Union(const size_t x, const size_t y)
87  {
88  const size_t xRoot = Find(x);
89  const size_t yRoot = Find(y);
90 
91  if (xRoot == yRoot)
92  {
93  return;
94  }
95  else if (rank[xRoot] == rank[yRoot])
96  {
97  parent[yRoot] = parent[xRoot];
98  rank[xRoot] = rank[xRoot] + 1;
99  }
100  else if (rank[xRoot] > rank[yRoot])
101  {
102  parent[yRoot] = xRoot;
103  }
104  else
105  {
106  parent[xRoot] = yRoot;
107  }
108  }
109 }; // class UnionFind
110 
111 }; // namespace emst
112 }; // namespace mlpack
113 
114 #endif // __MLPACK_METHODS_EMST_UNION_FIND_HPP
UnionFind(const size_t size)
Construct the object with the given size.
Definition: union_find.hpp:48
A Union-Find data structure.
Definition: union_find.hpp:40
arma::Col< size_t > parent
Definition: union_find.hpp:43
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: load.hpp:31
void Union(const size_t x, const size_t y)
Union the components containing x and y.
Definition: union_find.hpp:86
size_t Find(const size_t x)
Returns the component containing an element.
Definition: union_find.hpp:66
~UnionFind()
Destroy the object (nothing to do).
Definition: union_find.hpp:58