Program Listing for File ApproxCloseness.hpp¶

/*
 * ApproxCloseness.hpp
 *
 *  Created on: Dec 8, 2015
 *      Author: Sarah Lutteropp (uwcwa@student.kit.edu) and Michael Wegner
 *      (michael.wegner@student.kit.edu)
 */

#ifndef NETWORKIT_CENTRALITY_APPROX_CLOSENESS_HPP_
#define NETWORKIT_CENTRALITY_APPROX_CLOSENESS_HPP_

#include <limits>
#include <networkit/centrality/Centrality.hpp>

namespace NetworKit {

class ApproxCloseness : public Centrality {

public:
    enum ClosenessType { INBOUND, OUTBOUND, SUM };

    using CLOSENESS_TYPE = ClosenessType; // enum alias for backwards compatibility

    ApproxCloseness(const Graph &G, count nSamples, double epsilon = 0.1, bool normalized = false,
                    CLOSENESS_TYPE type = OUTBOUND);

    void run() override;

    double maximum() override;

    std::vector<double> getSquareErrorEstimates();

private:
    count nSamples;
    double epsilon;

    std::vector<double> LCSum;

    std::vector<count> LCNum;

    std::vector<double> LCSumSQ;

    std::vector<double> HCSum;

    std::vector<double> HCSumSQErr;

    std::vector<double> HSum;

    std::vector<count> HNum;

    std::vector<double> R;

    std::vector<double> SQErrEst;

    // divided by two s.t. infDist + infDist produces no overflow
    const edgeweight infDist = std::floor(std::numeric_limits<edgeweight>::max() / 2.0);

    ClosenessType type = ApproxCloseness::ClosenessType::OUTBOUND;

    void estimateClosenessForUndirectedGraph();
    void estimateClosenessForDirectedGraph(bool outbound);
    inline void computeClosenessForDirectedWeightedGraph(bool outbound);
    inline void computeClosenessForDirectedUnweightedGraph(bool outbound);

    void computeClosestPivot(const std::vector<node> &samples, std::vector<node> &pivot,
                             std::vector<edgeweight> &delta);

    void runOnPivot(index i, const std::vector<node> &pivot, const std::vector<edgeweight> &delta,
                    const std::vector<node> &samples);

    void orderNodesByIncreasingDistance(node pivot, std::vector<node> &order,
                                        std::vector<edgeweight> &pivotDist);
};

} /* namespace NetworKit */

#endif // NETWORKIT_CENTRALITY_APPROX_CLOSENESS_HPP_