Program Listing for File DynTopHarmonicCloseness.hpp¶

/*
 * DynTopHarmonicCloseness.hpp
 *
 *  Created on: 28.02.2018
 *      Author: nemes, Eugenio Angriman
 */

#ifndef NETWORKIT_CENTRALITY_DYN_TOP_HARMONIC_CLOSENESS_HPP_
#define NETWORKIT_CENTRALITY_DYN_TOP_HARMONIC_CLOSENESS_HPP_

#include <networkit/base/Algorithm.hpp>
#include <networkit/base/DynAlgorithm.hpp>
#include <networkit/components/DynConnectedComponents.hpp>
#include <networkit/components/DynWeaklyConnectedComponents.hpp>
#include <networkit/graph/Graph.hpp>
#include <networkit/structures/Partition.hpp>

namespace NetworKit {

class DynTopHarmonicCloseness : public Algorithm, public DynAlgorithm {
public:
    DynTopHarmonicCloseness(const Graph &G, count k = 1, bool useBFSbound = false);

    ~DynTopHarmonicCloseness() override;

    void run() override;

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

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

    std::vector<std::pair<node, edgeweight>> ranking(bool includeTrail = false);

    void reset();

    void update(GraphEvent event) override;

    void updateBatch(const std::vector<GraphEvent> &batch) override;

protected:
    std::pair<edgeweight, bool> BFScut(node v, edgeweight x, count n, count r,
                                       std::vector<uint8_t> &visited, std::vector<count> &distances,
                                       std::vector<node> &pred, count &visitedEdges);

    void BFSbound(node x, std::vector<double> &S2, count *visEdges);

    void addEdge(const GraphEvent &event);

    void removeEdge(const GraphEvent &event);

    void computeReachableNodes();
    void computeReachableNodesDirected();
    void computeReachableNodesUndirected();

    void updateReachableNodesAfterInsertion(node u, node v);

    void updateReachableNodesAfterDeletion(const GraphEvent &event);

    void init();

    const Graph &G;
    count n;
    count k;
    bool useBFSbound;
    count trail;
    double minCloseness;
    count nMinCloseness;
    std::vector<node> topk;
    std::vector<edgeweight> topkScores;
    std::vector<edgeweight> allScores;
    std::vector<uint8_t> isExact;
    std::vector<uint8_t> isValid;
    std::vector<edgeweight> cutOff;
    std::vector<uint8_t> exactCutOff;
    DynConnectedComponents *comps;
    bool hasComps = false;
    Partition component;
    DynWeaklyConnectedComponents *wComps;
    bool hasWComps = false;
    std::vector<count> r;
    std::vector<count> rOld;
    std::vector<count> reachL;
};

inline std::vector<node> DynTopHarmonicCloseness::topkNodesList(bool includeTrail) {
    assureFinished();
    if (!includeTrail) {
        auto begin = topk.begin();
        std::vector<node> topkNoTrail(begin, begin + k);
        return topkNoTrail;
    }
    return topk;
}

inline std::vector<edgeweight> DynTopHarmonicCloseness::topkScoresList(bool includeTrail) {
    assureFinished();
    if (!includeTrail) {
        auto begin = topkScores.begin();
        std::vector<edgeweight> topkScoresNoTrail(begin, begin + k);
        return topkScoresNoTrail;
    }
    return topkScores;
}

} /* namespace NetworKit */
#endif // NETWORKIT_CENTRALITY_DYN_TOP_HARMONIC_CLOSENESS_HPP_