UnionFind.h
Go to the documentation of this file.
00001 // this is for emacs file handling -*- mode: c++; indent-tabs-mode: nil -*-
00002 
00003 // -- BEGIN LICENSE BLOCK ----------------------------------------------
00004 // This file is part of FZIs ic_workspace.
00005 //
00006 // This program is free software licensed under the LGPL
00007 // (GNU LESSER GENERAL PUBLIC LICENSE Version 3).
00008 // You can find a copy of this license in LICENSE folder in the top
00009 // directory of the source code.
00010 //
00011 // © Copyright 2016 FZI Forschungszentrum Informatik, Karlsruhe, Germany
00012 //
00013 // -- END LICENSE BLOCK ------------------------------------------------
00014 
00015 //----------------------------------------------------------------------
00022 //----------------------------------------------------------------------
00023 #ifndef ICL_CORE_UNION_FIND_H_INCLUDED
00024 #define ICL_CORE_UNION_FIND_H_INCLUDED
00025 
00026 #include <vector>
00027 #include <stdexcept>
00028 
00029 namespace icl_core {
00030 
00034 class UnionFind
00035 {
00036 public:
00037   UnionFind(const std::size_t n)
00038     : m_parent(n), m_rank(n, 0)
00039   {
00040     for (std::size_t i = 0; i < n; ++i)
00041     {
00042       m_parent[i] = i;
00043     }
00044   }
00045 
00047   void grow(const std::size_t n = 1)
00048   {
00049     std::size_t old_size = m_parent.size();
00050     m_parent.resize(m_parent.size()+n);
00051     m_rank.resize(m_rank.size()+n, 0);
00052     for (std::size_t i = old_size; i < m_parent.size(); ++i)
00053     {
00054       m_parent[i] = i;
00055     }
00056   }
00057 
00061   void merge(std::size_t x, std::size_t y)
00062   {
00063     if (x >= m_parent.size() || y >= m_parent.size())
00064     {
00065       throw std::out_of_range("index out of range");
00066     }
00067     x = find(x);
00068     y = find(y);
00069     if (x == y)
00070     {
00071       return;
00072     }
00073     if (m_rank[x] < m_rank[y])
00074     {
00075       m_parent[x] = y;
00076     }
00077     else if (m_rank[x] > m_rank[y])
00078     {
00079       m_parent[y] = x;
00080     }
00081     else
00082     {
00083       m_parent[y] = x;
00084       ++m_rank[x];
00085     }
00086   }
00087 
00088   std::size_t find(std::size_t x)
00089   {
00090     if (x >= m_parent.size())
00091     {
00092       throw std::out_of_range("index out of range");
00093     }
00094     if (m_parent[x] != x)
00095     {
00096       m_parent[x] = find(m_parent[x]);
00097     }
00098     return m_parent[x];
00099   }
00100 
00101   std::size_t size() const { return m_parent.size(); }
00102 
00103 private:
00104   std::vector<std::size_t> m_parent;
00105   std::vector<std::size_t> m_rank;
00106 };
00107 
00108 }
00109 
00110 #endif


fzi_icl_core
Author(s):
autogenerated on Tue Aug 8 2017 02:28:04