Program Listing for File LocalCommunity.hpp¶

#ifndef NETWORKIT_STRUCTURES_LOCAL_COMMUNITY_HPP_
#define NETWORKIT_STRUCTURES_LOCAL_COMMUNITY_HPP_

#include <set>
#include <unordered_map>
#include <unordered_set>

#include <networkit/graph/Graph.hpp>

namespace NetworKit {

template <bool ShellMaintainsExtDeg, bool MaintainBoundary = false, bool AllowRemoval = false>
class LocalCommunity {
    static_assert(!MaintainBoundary || ShellMaintainsExtDeg,
                  "boundary cannot be maintained without maintaining the external degree");

public:
    template <typename ValueType, bool used>
    struct OptionalValue {
        ValueType &get() { throw std::runtime_error("Getting value that is missing"); }

        const ValueType &get() const { throw std::runtime_error("Getting value that is missing"); }

        ValueType &operator*() { throw std::runtime_error("Getting value that is missing"); }

        const ValueType &operator*() const {
            throw std::runtime_error("Getting value that is missing");
        }

        ValueType *operator->() { throw std::runtime_error("Getting value that is missing"); }

        const ValueType *operator->() const {
            throw std::runtime_error("Getting value that is missing");
        }

        void set(ValueType) { throw std::runtime_error("Setting value that is missing"); }

        OptionalValue &operator+=(ValueType) {
            throw std::runtime_error("Increasing value that is missing");
        }

        OptionalValue &operator-=(ValueType) {
            throw std::runtime_error("Decreasing value that is missing");
        }

        OptionalValue(const ValueType &){};

        OptionalValue(){};
    };

    template <typename ValueType>
    struct OptionalValue<ValueType, true> {
        ValueType &get() { return value; }

        const ValueType &get() const { return value; }

        ValueType &operator*() { return value; }

        const ValueType &operator*() const { return value; }

        ValueType *operator->() { return &value; }

        const ValueType *operator->() const { return &value; }

        void set(ValueType v) { value = v; }

        template <typename SecondValue,
                  typename std::enable_if<std::is_scalar<SecondValue>::value, int>::type = 0>
        OptionalValue &operator+=(SecondValue v) {
            value += v;
            return *this;
        }

        template <typename SecondValue,
                  typename std::enable_if<std::is_scalar<SecondValue>::value, int>::type = 0>
        OptionalValue &operator-=(SecondValue v) {
            value -= v;
            return *this;
        }

        OptionalValue(const ValueType &v) : value(v){};

        OptionalValue() : value(){};

        ValueType value;
    };

    struct ShellInfo {
        OptionalValue<double, true> intDeg;

        OptionalValue<double, ShellMaintainsExtDeg> extDeg;

        OptionalValue<count, MaintainBoundary> numExclusiveBoundaryMembers;

        int64_t boundaryChange() const {
            int64_t boundary_diff = -1 * numExclusiveBoundaryMembers.get();

            if (extDeg.get() > 0) {
                boundary_diff += 1;
            }

            return boundary_diff;
        }

        ShellInfo() : intDeg(0), extDeg(0), numExclusiveBoundaryMembers(0) {}
    };

    struct CommunityInfo {
        OptionalValue<double, AllowRemoval> intDeg;

        OptionalValue<double, ShellMaintainsExtDeg && AllowRemoval> extDeg;

        OptionalValue<node, MaintainBoundary && AllowRemoval> exclusiveOutsideNeighbor;

        OptionalValue<count, MaintainBoundary && AllowRemoval> numFullyInternalNeighbors;

        int64_t boundaryChange() const {
            int64_t boundary_diff = numFullyInternalNeighbors.get();

            if (extDeg.get() > 0) {
                boundary_diff -= 1;
            }

            return boundary_diff;
        }

        CommunityInfo()
            : intDeg(0), extDeg(0), exclusiveOutsideNeighbor(none), numFullyInternalNeighbors(0) {}
    };

    LocalCommunity(const Graph &G);

    void addNode(node u);

    void removeNode(node u);

    bool contains(node u) const;

    std::set<node> toSet() const;

    template <typename F>
    void forShellNodes(F callback) {
        for (const auto &it : shell) {

#ifdef NETWORKIT_SANITY_CHECKS
#ifndef NDEBUG
            auto intExtDeg = calculateIntExtDeg(it.first);
            assert(*it.second.intDeg == intExtDeg.first);
            if (ShellMaintainsExtDeg) {
                assert(*it.second.extDeg == intExtDeg.second);
            }

            if (MaintainBoundary) {
                int64_t boundary_diff_debug = 0;
                bool v_in_boundary = false;
                G->forNeighborsOf(it.first, [&](node x) {
                    auto it = currentBoundary->find(x);
                    if (it != currentBoundary->end()) {
                        if (it->second == 1) {
                            boundary_diff_debug -= 1;
                        }
                    } else if (!v_in_boundary) {
                        boundary_diff_debug += 1;
                        v_in_boundary = true;
                    }
                });

                assert(it.second.boundaryChange() == boundary_diff_debug);
            }
#endif // NDEBUG
#endif // NETWORKIT_SANITY_CHECKS

            callback(it.first, it.second);
        }
    }

    template <typename F>
    void forCommunityNodes(F callback) {
        for (auto it = community.cbegin(); it != community.cend();) {
            // advance the iterator so the current element may be deleted
            const auto cit = it++;
#ifdef NETWORKIT_SANITY_CHECKS
#ifndef NDEBUG
            if (AllowRemoval) {
                auto intExtDeg = calculateIntExtDeg(cit->first);
                assert(*cit->second.intDeg == intExtDeg.first);
                if (ShellMaintainsExtDeg) {
                    assert(*cit->second.extDeg == intExtDeg.second);
                }

                if (MaintainBoundary) {
                    int64_t boundary_diff_debug = 0;
                    bool v_in_boundary = false;
                    G->forNeighborsOf(cit->first, [&](node x) {
                        if (community.find(x) == community.end()) {
                            if (!v_in_boundary) {
                                boundary_diff_debug -= 1;
                                v_in_boundary = true;
                            }
                        } else if (currentBoundary->find(x) == currentBoundary->end()) {
                            boundary_diff_debug += 1;
                        }
                    });

                    assert(cit->second.boundaryChange() == boundary_diff_debug);
                }
            }
#endif // NDEBUG
#endif // NETWORKIT_SANITY_CHECKS

            callback(cit->first, cit->second);
        }
    }

    size_t size() const { return community.size(); }

    double internalEdgeWeight() const { return intWeight; }

    double cut() const { return extWeight; }

    count boundarySize() const { return currentBoundary->size(); }

private:
    const Graph *G;
    std::unordered_map<node, CommunityInfo> community;
    std::unordered_map<node, ShellInfo> shell;
    double intWeight;
    double extWeight;
    OptionalValue<std::unordered_map<node, count>, MaintainBoundary> currentBoundary;

    // The boundary is defined as all nodes of C that have a neighbor not in C
    std::unordered_set<node> calculateBoundary();

    std::pair<double, double> calculateIntExtDeg(node v);

    std::pair<double, double> calculateVolumeCut();
};

} // namespace NetworKit

#endif // NETWORKIT_STRUCTURES_LOCAL_COMMUNITY_HPP_