UnionFind.cpp

Go to the documentation of this file.

#include "UnionFind.h"
 
#include <cstddef>
 
namespace armarx::navigation::components::laser_scanner_feature_extraction
{
    UnionFind::UnionFind(std::size_t n)
    {
        rank.reserve(n);
        parent.reserve(n);
        for (std::size_t i = 0; i < n; i++)
        {
            rank.push_back(0);
            parent.push_back(i);
        }
    }
 
    std::size_t
    UnionFind::find(std::size_t x)
    {
        // Finds the representative of the set
        // that x is an element of
        if (parent[x] != x)
        {
 
            // if x is not the parent of itself
            // Then x is not the representative of
            // his set,
            parent[x] = find(parent[x]);
 
            // so we recursively call Find on its parent
            // and move i's node directly under the
            // representative of this set
        }
 
        return parent[x];
    }
 
    void
    UnionFind::unite(std::size_t a, std::size_t b)
    {
        // Find current sets of x and y
        std::size_t xset = find(a);
        std::size_t yset = find(b);
 
        // If they are already in same set
        if (xset == yset)
            return;
 
        // Put smaller ranked item under
        // bigger ranked item if ranks are
        // different
        if (rank[xset] < rank[yset])
        {
            parent[xset] = yset;
        }
        else if (rank[xset] > rank[yset])
        {
            parent[yset] = xset;
        }
 
        // If ranks are same, then increment
        // rank.
        else
        {
            parent[yset] = xset;
            rank[xset] = rank[xset] + 1;
        }
    }
 
 
} // namespace armarx::navigation::components::laser_scanner_feature_extraction