MLPACK  1.0.8
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  size_t size;
44  arma::Col<size_t> parent;
45  arma::ivec rank;
46 
47  public:
49  UnionFind(const size_t size) : size(size), parent(size), rank(size)
50  {
51  for (size_t i = 0; i < size; ++i)
52  {
53  parent[i] = i;
54  rank[i] = 0;
55  }
56  }
57 
59  ~UnionFind() { }
60 
67  size_t Find(const size_t x)
68  {
69  if (parent[x] == x)
70  {
71  return x;
72  }
73  else
74  {
75  // This ensures that the tree has a small depth
76  parent[x] = Find(parent[x]);
77  return parent[x];
78  }
79  }
80 
87  void Union(const size_t x, const size_t y)
88  {
89  const size_t xRoot = Find(x);
90  const size_t yRoot = Find(y);
91 
92  if (xRoot == yRoot)
93  {
94  return;
95  }
96  else if (rank[xRoot] == rank[yRoot])
97  {
98  parent[yRoot] = parent[xRoot];
99  rank[xRoot] = rank[xRoot] + 1;
100  }
101  else if (rank[xRoot] > rank[yRoot])
102  {
103  parent[yRoot] = xRoot;
104  }
105  else
106  {
107  parent[xRoot] = yRoot;
108  }
109  }
110 }; // class UnionFind
111 
112 }; // namespace emst
113 }; // namespace mlpack
114 
115 #endif // __MLPACK_METHODS_EMST_UNION_FIND_HPP