Program Listing for File GenericPartition.hpp¶

/*
 * GenericPartition.hpp
 *
 *  Created on: 03.10.2013
 *      Author: cls
 */

#ifndef NETWORKIT_STRUCTURES_GENERIC_PARTITION_HPP_
#define NETWORKIT_STRUCTURES_GENERIC_PARTITION_HPP_

#include <cassert>
#include <concepts>
#include <limits>
#include <map>
#include <set>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

#include <networkit/Globals.hpp>

namespace NetworKit {

template <typename T>
concept IntegralValue = std::integral<T> && !std::same_as<std::remove_cvref_t<T>, bool>;

template <IntegralValue IndexType>
class GenericPartition final {

public:
    static constexpr IndexType noneIndex = std::numeric_limits<IndexType>::max();

    GenericPartition();

    GenericPartition(IndexType z);

    GenericPartition(IndexType z, IndexType defaultValue);

    GenericPartition(const std::vector<IndexType> &data);

    void reset(IndexType newZ, IndexType defaultValue) {
        data.clear();
        data.resize(newZ, defaultValue);
        z = newZ;
        omega = 0;
    }

    inline IndexType &operator[](IndexType e) { return this->data[e]; }

    inline const IndexType &operator[](IndexType e) const { return this->data[e]; }

    inline IndexType subsetOf(IndexType e) const {
        assert(e < this->numberOfElements());
        return this->data[e];
    }

    inline IndexType extend() {
        data.push_back(noneIndex);
        z++;
        assert(z == data.size()); //(data.size() - 1)
        return z - 1;
    }

    inline void remove(IndexType e) {
        assert(e < z);
        data[e] = noneIndex;
    }

    inline void addToSubset(IndexType s, IndexType e) {
        assert(data[e] == noneIndex); // guarantee that element was unassigned
        assert(s <= omega);           // do not create new subset ids
        data[e] = s;
    }

    inline void moveToSubset(IndexType s, IndexType e) {
        assert(this->contains(e));
        assert(s <= omega); // do not create new subset ids
        data[e] = s;
    }

    inline void toSingleton(IndexType e) { data[e] = newSubsetId(); }

    void allToSingletons();

    void allToOnePartition();

    IndexType mergeSubsets(IndexType s, IndexType t);

    inline void setUpperBound(IndexType upper) {
        // omega should never be < 0
        const IndexType newOmega = (upper == 0) ? 0 : upper - 1;

        if (newOmega < this->omega) {
            // trying to shrink omega, must ensure we do not shrink it too much
            for (IndexType e = 0; e < this->z; ++e) {
                if (data[e] != noneIndex && data[e] > newOmega) {
                    throw std::invalid_argument(
                        "Shrinking upper bound this much would result in "
                        "elements being mapped to invalid subset ids. Try "
                        "larger number for upper or using compact() first.");
                }
            }
        }
        this->omega = newOmega;
    }

    inline IndexType upperBound() const { return omega + 1; }

    inline IndexType lowerBound() const { return 0; }

    void compact(bool useTurbo = false);

    inline bool contains(IndexType e) const {
        // e is in the element index range and the entry is not empty
        return (e < z) && (data[e] != noneIndex);
    }

    inline bool inSameSubset(IndexType e1, IndexType e2) const {
        assert(data[e1] != noneIndex);
        assert(data[e2] != noneIndex);
        return data[e1] == data[e2];
    }

    std::vector<count> subsetSizes() const;

    std::map<IndexType, count> subsetSizeMap() const;

    std::set<IndexType> getMembers(IndexType s) const;

    inline IndexType numberOfElements() const {
        return z; // z is the maximum element id
    }

    count numberOfSubsets() const;

    const std::vector<IndexType> &getVector() const;

    std::set<std::set<IndexType>> getSubsets() const;

    std::set<IndexType> getSubsetIds() const;

    inline void setName(std::string name) { this->name = std::move(name); }

    inline std::string getName() const { return this->name; }

    template <typename Callback>
    void forEntries(Callback func) const;

    template <typename Callback>
    void parallelForEntries(Callback handle) const;

private:
    IndexType z;
    IndexType omega;
    std::vector<IndexType>
        data;
    std::string name;

    inline IndexType newSubsetId() {
        IndexType s = ++omega;
        return s;
    }
};

template <IntegralValue IndexType>
template <typename Callback>
inline void GenericPartition<IndexType>::forEntries(Callback handle) const {
    for (IndexType e = 0; e < this->z; e++) {
        handle(e, data[e]);
    }
}

template <IntegralValue IndexType>
template <typename Callback>
inline void GenericPartition<IndexType>::parallelForEntries(Callback handle) const {
#pragma omp parallel for
    for (omp_index e = 0; e < static_cast<omp_index>(this->z); e++) {
        handle(static_cast<IndexType>(e), this->data[static_cast<IndexType>(e)]);
    }
}

using Partition = GenericPartition<index>;

} /* namespace NetworKit */

#include <networkit/structures/GenericPartitionImpl.hpp>

#endif // NETWORKIT_STRUCTURES_GENERIC_PARTITION_HPP_