union_find.hpp
Go to the documentation of this file.00001
00025 #ifndef __MLPACK_METHODS_EMST_UNION_FIND_HPP
00026 #define __MLPACK_METHODS_EMST_UNION_FIND_HPP
00027
00028 #include <mlpack/core.hpp>
00029
00030 namespace mlpack {
00031 namespace emst {
00032
00040 class UnionFind
00041 {
00042 private:
00043 size_t size;
00044 arma::Col<size_t> parent;
00045 arma::ivec rank;
00046
00047 public:
00049 UnionFind(const size_t size) : size(size), parent(size), rank(size)
00050 {
00051 for (size_t i = 0; i < size; ++i)
00052 {
00053 parent[i] = i;
00054 rank[i] = 0;
00055 }
00056 }
00057
00059 ~UnionFind() { }
00060
00067 size_t Find(const size_t x)
00068 {
00069 if (parent[x] == x)
00070 {
00071 return x;
00072 }
00073 else
00074 {
00075
00076 parent[x] = Find(parent[x]);
00077 return parent[x];
00078 }
00079 }
00080
00087 void Union(const size_t x, const size_t y)
00088 {
00089 const size_t xRoot = Find(x);
00090 const size_t yRoot = Find(y);
00091
00092 if (xRoot == yRoot)
00093 {
00094 return;
00095 }
00096 else if (rank[xRoot] == rank[yRoot])
00097 {
00098 parent[yRoot] = parent[xRoot];
00099 rank[xRoot] = rank[xRoot] + 1;
00100 }
00101 else if (rank[xRoot] > rank[yRoot])
00102 {
00103 parent[yRoot] = xRoot;
00104 }
00105 else
00106 {
00107 parent[xRoot] = yRoot;
00108 }
00109 }
00110 };
00111
00112 };
00113 };
00114
00115 #endif // __MLPACK_METHODS_EMST_UNION_FIND_HPP