Program Listing for File TopHarmonicCloseness.hpp¶

/*
 * TopHarmonicCloseness.hpp
 *
 * Created on: 25.02.2018
 *      Authors: nemes, Eugenio Angriman
 */

#ifndef NETWORKIT_CENTRALITY_TOP_HARMONIC_CLOSENESS_HPP_
#define NETWORKIT_CENTRALITY_TOP_HARMONIC_CLOSENESS_HPP_

#include <memory>

#include <networkit/auxiliary/VectorComparator.hpp>
#include <networkit/base/Algorithm.hpp>
#include <networkit/components/WeaklyConnectedComponents.hpp>
#include <networkit/graph/Graph.hpp>

#include <tlx/container/d_ary_addressable_int_heap.hpp>

namespace NetworKit {

class TopHarmonicCloseness final : public Algorithm {
public:
    explicit TopHarmonicCloseness(const Graph &G, count k = 1, bool useNBbound = false);

    ~TopHarmonicCloseness() override;

    void run() override;

    std::vector<node> topkNodesList(bool includeTrail = false);

    std::vector<edgeweight> topkScoresList(bool includeTrail = false);

    void restrictTopKComputationToNodes(const std::vector<node> &nodeList) {
        nodeListPtr = &nodeList;
    };

private:
    const Graph *G;
    const count k;
    const bool useNBbound;

    std::vector<double> hCloseness;
    std::vector<count> reachableNodes;
    std::vector<std::vector<uint8_t>> visitedGlobal;
    std::vector<uint8_t> tsGlobal;

    std::vector<node> topKNodes;
    std::vector<double> topKScores;
    const std::vector<node> *nodeListPtr;

    // For NBbound
    std::vector<count> reachU, reachL;
    std::vector<std::vector<count>> numberOfNodesAtLevelGlobal;
    std::vector<std::vector<node>> nodesAtCurrentLevelGlobal;
    std::vector<std::vector<std::vector<node>>> nodesAtLevelGlobal;
    std::vector<double> levelImprovement;
    std::unique_ptr<WeaklyConnectedComponents> wccPtr;
    void updateTimestamp() {
        auto &visited = visitedGlobal[omp_get_thread_num()];
        auto &ts = tsGlobal[omp_get_thread_num()];
        if (ts++ == std::numeric_limits<uint8_t>::max()) {
            ts = 1;
            std::fill(visited.begin(), visited.end(), 0);
        }
    }

    tlx::d_ary_addressable_int_heap<node, 2, Aux::LessInVector<double>> topKNodesPQ;
    tlx::d_ary_addressable_int_heap<node, 2, Aux::GreaterInVector<double>> prioQ;
    std::vector<node> trail;

    // For weighted graphs
    std::vector<tlx::d_ary_addressable_int_heap<node, 2, Aux::LessInVector<edgeweight>>>
        dijkstraHeaps;
    std::vector<std::vector<edgeweight>> distanceGlobal;
    edgeweight minEdgeWeight;

    omp_lock_t lock;

    void init();
    void runNBcut();
    void runNBbound();
    bool bfscutUnweighted(node source, double kthCloseness);
    bool bfscutWeighted(node source, double kthCloseness);
    void bfsbound(node source);
    void computeReachableNodes();
    void computeReachableNodesBounds();
    void computeNeighborhoodBasedBound();
    void updateTopkPQ(node u);

    double initialBoundNBcutUnweighted(node u) const noexcept;
    double initialBoundNBcutWeighted(node u) const noexcept;

    template <class Type>
    std::vector<Type> resizedCopy(const std::vector<Type> &vec) const noexcept;
};

} // namespace NetworKit
#endif // NETWORKIT_CENTRALITY_TOP_HARMONIC_CLOSENESS_HPP_