Program Listing for File GroupClosenessLocalSwaps.hpp¶

/*
 *  GroupClosenessLocalSwaps.hpp
 *
 *  Created on: 19.12.2019
 *      Author: Eugenio Angriman <angrimae@hu-berlin.de>
 */

#ifndef NETWORKIT_CENTRALITY_GROUP_CLOSENESS_LOCAL_SWAPS_HPP_
#define NETWORKIT_CENTRALITY_GROUP_CLOSENESS_LOCAL_SWAPS_HPP_

#ifdef __AVX2__
#include <immintrin.h>
#include <networkit/auxiliary/AlignedAllocator.hpp>
#endif // __AVX2__

#include <limits>
#include <stdexcept>
#include <unordered_map>
#include <vector>

#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

class GroupClosenessLocalSwaps final : public Algorithm {

    static constexpr float maxInt16 = static_cast<float>(std::numeric_limits<uint16_t>::max());
    // Number of random numbers generated at once
    static constexpr count K = 16;

public:
    GroupClosenessLocalSwaps(const Graph &G, const std::vector<node> &group, count maxSwaps = 100);

    template <class InputIt>
    GroupClosenessLocalSwaps(const Graph &graph, InputIt first, InputIt last, count maxSwaps = 100)
        : G(&graph), group(first, last), maxSwaps(maxSwaps) {

        if (G->isDirected())
            throw std::runtime_error("Error, this algorithm does not support directed graphs.");

        if (group.empty())
            throw std::runtime_error("Error, empty group.");

        if (G->isWeighted())
            WARN("This algorithm does not support edge Weights, they will be ignored.");
    }

    void run() override;

    std::vector<node> groupMaxCloseness() const;

    count numberOfSwaps() const;

private:
    const Graph *G;
    std::vector<node> group, stack;
    std::vector<uint32_t> distance, sumOfMins;
    std::vector<bool> gamma, visited;
    std::unordered_map<node, index> idxMap;
    std::vector<int64_t> farness, farnessDecrease;

    count maxSwaps, totalSwaps, stackSize;

    void init();
    void bfsFromGroup();
    bool findAndSwap();
    node estimateHighestDecrease();
    void initRandomVector();
    int64_t computeFarnessDecrease(node u);
    void resetGamma(node x, index idx);

#ifdef __AVX2__
    union RandItem {
        uint16_t items[K];
        __m256i vec;
    };
    std::vector<RandItem, AlignedAllocator<RandItem, sizeof(RandItem)>> randVec;
#else
    std::vector<uint16_t> randVec;
#endif // __AVX2__

    std::vector<std::uniform_int_distribution<uint32_t>> intDistributions;
};
} // namespace NetworKit

#endif // NETWORKIT_CENTRALITY_GROUP_CLOSENESS_LOCAL_SWAPS_HPP_