Program Listing for File ApproxElectricalCloseness.hpp¶

/*
 * ApproxElectricalCloseness.hpp
 *
 *  Created on: 17.10.2019
 *     Authors: Eugenio Angriman <angrimae@hu-berlin.de>
 *              Alexander van der Grinten <avdgrinten@hu-berlin.de>
 */

#ifndef NETWORKIT_CENTRALITY_APPROX_ELECTRICAL_CLOSENESS_HPP_
#define NETWORKIT_CENTRALITY_APPROX_ELECTRICAL_CLOSENESS_HPP_

#include <cmath>
#include <memory>
#include <random>
#include <unordered_map>
#include <vector>

#include <networkit/centrality/Centrality.hpp>
#include <networkit/components/BiconnectedComponents.hpp>
#include <networkit/distance/Diameter.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

class ApproxElectricalCloseness final : public Centrality {

public:
    ApproxElectricalCloseness(const Graph &G, double epsilon = 0.1, double kappa = 0.3);

    ~ApproxElectricalCloseness() override = default;

    void run() override;

    const std::vector<double> &getDiagonal() const {
        assureFinished();
        return diagonal;
    }

    std::vector<double> computeExactDiagonal(double tol = 1e-9) const;

private:
    const double epsilon, delta, kappa;
    node root = 0;
    count rootEcc;

    // #of BFSs used to estimate a vertex with low eccentricity.
    static constexpr uint32_t sweeps = 10;

    enum class NodeStatus : unsigned char {
        NOT_IN_COMPONENT,
        IN_SPANNING_TREE,
        NOT_VISITED,
        VISITED
    };

    // Used to mark the status of each node, one vector per thread
    std::vector<std::vector<NodeStatus>> statusGlobal;

    std::unique_ptr<BiconnectedComponents> bccPtr;

    // Nodes in each biconnected components sorted by their degree.
    std::vector<std::vector<node>> sequences;

    // Pointers to the parent of the UST, one vector per thread
    std::vector<std::vector<node>> parentGlobal;

    // Index of the parent component of the current component (after the topological order has been
    // determined)
    std::vector<index> biParent;
    // Node within the biconnected component that points to the node in the parent component
    std::vector<node> biAnchor;

    // Topological order of the biconnected components
    std::vector<index> topOrder;

    // Non-normalized approx effective resistance, one per thread.
    // Values could be negative, so we use signed integers.
    std::vector<std::vector<int64_t>> approxEffResistanceGlobal;

    // Pseudo-inverse diagonal
    std::vector<double> diagonal;

    // Timestamps for DFS
    std::vector<std::vector<count>> tVisitGlobal, tFinishGlobal;

    // Random number generators
    std::vector<std::mt19937_64> generators;
    std::vector<std::uniform_int_distribution<index>> degDist;

    // Parent pointers of the bfs tree
    std::vector<node> bfsParent;

    // Nodes sequences: Wilson's algorithm runs faster if we start the random walks following a
    // specific sequence of nodes. In this function we compute those sequences.
    void computeNodeSequence();

    // Adjacency list for trees: additional data structure to speed-up the DFS
    std::vector<std::vector<node>> ustChildPtrGlobal;
    std::vector<std::vector<node>> ustSiblingPtrGlobal;

    void computeBFSTree();
    void sampleUST();
    void dfsUST();
    void aggregateUST();

    node approxMinEccNode();

    count computeNumberOfUSTs() const;

#ifdef NETWORKIT_SANITY_CHECKS
    // Debugging methods
    void checkBFSTree() const;
    void checkUST() const;
    void checkTwoNodesSequence(const std::vector<node> &sequence) const;
    void checkTimeStamps() const;
#endif // NETWORKIT_SANITY_CHECKS
};

} // namespace NetworKit

#endif // NETWORKIT_CENTRALITY_APPROX_ELECTRICAL_CLOSENESS_HPP_