UnionFind.h

Go to the documentation of this file.

/*
 * This file is part of ArmarX.
 *
 * ArmarX is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 *
 * ArmarX is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 *
 * @author     Tobias Gröger ( tobias dot groeger at student dot kit dot edu )
 * @author     Corvin Navarro ( corvin dot ecker at student dot kit dot edu )
 * @date       2021
 * @copyright  http://www.gnu.org/licenses/gpl-2.0.txt
 *             GNU General Public License
 */
 
#pragma once
 
#include <cstddef>
#include <cstdint>
#include <vector>
 
namespace armarx::navigation::components::laser_scanner_feature_extraction
{
 
    // The implementation of this class is taken (and modified) from
    // https://www.geeksforgeeks.org/disjoint-set-data-structures/
 
    /*! \brief A simple union find data structure
     *
     *  The data structure supports a fixed size of n elements which must be the
     *  integers from [0, n).
     */
    class UnionFind
    {
    public:
        /*! \brief Construct a new union find data structure with n elements
         *  \param n the number of elements
         *
         *  After construction each element will be in its own individual set.
         */
        UnionFind(std::size_t n);
 
        /*! \brief find the representative of x
         *  \return the representative of x
         */
        std::size_t find(std::size_t x);
 
        /*! \brief unite the sets of the elements a and b
         *  \param a
         *  \param b
         */
        void unite(std::size_t a, std::size_t b);
 
    private:
        std::vector<std::size_t> rank;
        std::vector<std::size_t> parent;
    };
 
} // namespace armarx::navigation::components::laser_scanner_feature_extraction