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       // 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

Generated on 29 Sep 2016 for MLPACK by  doxygen 1.6.1