Program Listing for File GenericUnionFind.hpp¶

/*
 * GenericUnionFind.hpp
 *
 *  Created on: 11.08.2014
 *      Author: Marcel Radermacher
 *      Changed a bit by Henning Meyerhenke to reflect union by rank and path compression
 *        as taught in "Algorithms 1"
 */

#ifndef NETWORKIT_STRUCTURES_GENERIC_UNION_FIND_HPP_
#define NETWORKIT_STRUCTURES_GENERIC_UNION_FIND_HPP_

#include <cstddef>
#include <numeric>
#include <vector>

#include <networkit/Globals.hpp>
#include <networkit/structures/GenericPartition.hpp>

namespace NetworKit {

template <IntegralValue IndexType>
class GenericUnionFind final {
    std::vector<IndexType> parent;
    std::vector<unsigned char> rank;

public:
    GenericUnionFind(IndexType max_element)
        : parent(static_cast<std::size_t>(max_element)),
          rank(static_cast<std::size_t>(max_element), 0) {
        allToSingletons();
    }

    void allToSingletons() { std::iota(parent.begin(), parent.end(), IndexType{0}); }

    IndexType find(IndexType u) {
        const auto uIndex = static_cast<std::size_t>(u);
        if (parent[uIndex] == u) {
            return u;
        }

        // recursion and path compression
        parent[uIndex] = find(parent[uIndex]);
        return parent[uIndex];
    }

    void merge(IndexType u, IndexType v) {
        const IndexType setU = find(u);
        const IndexType setV = find(v);
        if (setU == setV) {
            return;
        }

        const auto setUIndex = static_cast<std::size_t>(setU);
        const auto setVIndex = static_cast<std::size_t>(setV);
        if (rank[setUIndex] < rank[setVIndex]) {
            parent[setUIndex] = setV;
        } else {
            parent[setVIndex] = setU;
            if (rank[setUIndex] == rank[setVIndex]) {
                ++rank[setUIndex];
            }
        }
    }

    GenericPartition<IndexType> toPartition() {
        GenericPartition<IndexType> partition(static_cast<IndexType>(parent.size()));
        partition.setUpperBound(static_cast<IndexType>(parent.size()));
        for (std::size_t e = 0; e < parent.size(); ++e) {
            const auto element = static_cast<IndexType>(e);
            partition.addToSubset(find(element), element);
        }
        return partition;
    }
};

using UnionFind = GenericUnionFind<index>;

} /* namespace NetworKit */

#endif // NETWORKIT_STRUCTURES_GENERIC_UNION_FIND_HPP_