Program Listing for File Closeness.hpp¶

/*
 * Closeness.hpp
 *
 *  Created on: 03.10.2014
 *     Authors: nemes,
 *              Eugenio Angriman <angrimae@hu-berlin.de>
 */

#ifndef NETWORKIT_CENTRALITY_CLOSENESS_HPP_
#define NETWORKIT_CENTRALITY_CLOSENESS_HPP_

#include <networkit/auxiliary/VectorComparator.hpp>
#include <networkit/centrality/Centrality.hpp>

#include <tlx/container/d_ary_addressable_int_heap.hpp>

namespace NetworKit {

enum ClosenessVariant {
    STANDARD = 0,
    GENERALIZED = 1,
    standard = STANDARD, // this + following added for backwards compatibility
    generalized = GENERALIZED
};

class Closeness : public Centrality {

public:
    Closeness(const Graph &G, bool normalized,
              ClosenessVariant variant = ClosenessVariant::STANDARD);

    Closeness(const Graph &G, bool normalized = true, bool checkConnectedness = true);

    void run() override;

    /*
     * Returns the maximum possible Closeness a node can have in a graph with
     * the same amount of nodes (=a star)
     */
    double maximum() override {
        return normalized ? 1. : (1. / (static_cast<double>(G.upperNodeIdBound() - 1)));
    }

private:
    ClosenessVariant variant;
    std::vector<std::vector<count>> uDist;
    std::vector<std::vector<double>> dDist;
    std::vector<std::vector<uint8_t>> visited;
    std::vector<uint8_t> ts;

    void checkConnectedComponents() const;
    void bfs();
    void dijkstra();
    void incTS();
    void updateScoreData(node u, count reached, double sum) {
        if (sum > 0) {
            if (variant == ClosenessVariant::STANDARD) {
                scoreData[u] = 1.0 / sum;
            } else {
                scoreData[u] = static_cast<double>(reached - 1) / sum
                               / static_cast<double>(G.numberOfNodes() - 1);
            }
        } else {
            scoreData[u] = 0.;
        }
        if (normalized)
            scoreData[u] *=
                (variant == ClosenessVariant::STANDARD ? G.numberOfNodes() : reached) - 1.;
    }

    std::vector<tlx::d_ary_addressable_int_heap<node, 2, Aux::LessInVector<double>>> heaps;
};

} /* namespace NetworKit */

#endif // NETWORKIT_CENTRALITY_CLOSENESS_HPP_