Program Listing for File Partition.hpp¶

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

#ifndef NETWORKIT_STRUCTURES_PARTITION_HPP_
#define NETWORKIT_STRUCTURES_PARTITION_HPP_

#include <cassert>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include <networkit/Globals.hpp>

namespace NetworKit {

class Partition final {

public:
    Partition();

    Partition(index z);

    Partition(index z, index defaultValue);

    Partition(const std::vector<index> &data);

    /* Updates the maximum index of the partition to @a newZ and sets all its
     * values to @a defaultValue.
     *
     * @param[in] newZ New maximum index of the partition. @param[in]
     * defaultValue Default value of all the elements in the partition.
     */
    void reset(index newZ, index defaultValue) {
        data.clear();
        data.resize(newZ, defaultValue);
        z = newZ;
        omega = 0;
    }

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

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

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

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

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

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

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

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

    void allToSingletons();

    void allToOnePartition();

    index mergeSubsets(index s, index t);

    inline void setUpperBound(index upper) { this->omega = upper - 1; }

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

    inline index lowerBound() const { return 0; }

    void compact(bool useTurbo = false);

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

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

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

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

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

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

    count numberOfSubsets() const;

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

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

    std::set<index> 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:
    index z;
    index omega;
    std::vector<index> data;
    std::string name;

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

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

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

} /* namespace NetworKit */

#endif // NETWORKIT_STRUCTURES_PARTITION_HPP_