MLPACK
1.0.4
|
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 // This ensures that the tree has a small depth 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 }; // class UnionFind 00111 00112 }; // namespace emst 00113 }; // namespace mlpack 00114 00115 #endif // __MLPACK_METHODS_EMST_UNION_FIND_HPP