Program Listing for File ForestCentrality.hpp¶

/*
 * ForestCentrality.hpp
 *
 *  Created on: 12.02.2020
 *      Author: Eugenio Angriman <angrimae@hu-berlin.de>
 */

#ifndef NETWORKIT_CENTRALITY_FOREST_CENTRALITY_HPP_
#define NETWORKIT_CENTRALITY_FOREST_CENTRALITY_HPP_

#include <cmath>
#include <functional>
#include <omp.h>
#include <random>
#include <vector>

#include <networkit/algebraic/Vector.hpp>
#include <networkit/centrality/Centrality.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

// NOTE: Does not support multiple calls of run()
class ForestCentrality final : public Centrality {

public:
    explicit ForestCentrality(const Graph &G, node root, double epsilon = 0.1, double kappa = 0.3);

    void run() override;

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

    count getNumberOfSamples() const noexcept { return numberOfUSTs; }

private:
    node root;
    const double epsilon, kappa, volG;
    const count numberOfUSTs;

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

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

    // Nodes sorted by decreasing degree
    std::vector<node> decDegree;

    // Non-normalized approx effective resistance, one per thread.
    std::vector<std::vector<count>> approxEffResistanceGlobal;

    // Distributions for selecting random neighbors
    std::vector<std::uniform_int_distribution<count>> uniformDistr;

    // Solution of the linear system
    Vector linearSysSol;

    // Diagonal elements
    std::vector<double> diagonal;

    count computeNumberOfUSTs() const {
        return count{4}
               * static_cast<count>(std::ceil(
                   std::log(2.0 * static_cast<double>(G.numberOfEdges()) * G.numberOfNodes())
                   / (2.0 * epsilon * epsilon)));
    }

    void sampleUSTs();
    void solveLinearSystem();
    void computeDiagonal();
    void computeScores();
};

} // namespace NetworKit

#endif // NETWORKIT_CENTRALITY_FOREST_CENTRALITY_HPP_