Program Listing for File DynApproxBetweenness.hpp¶

/*
 * DynApproxBetweenness.hpp
 *
 *  Created on: 31.07.2014
 *      Author: ebergamini
 */

#ifndef NETWORKIT_CENTRALITY_DYN_APPROX_BETWEENNESS_HPP_
#define NETWORKIT_CENTRALITY_DYN_APPROX_BETWEENNESS_HPP_

#include <networkit/base/DynAlgorithm.hpp>
#include <networkit/centrality/Centrality.hpp>
#include <networkit/components/StronglyConnectedComponents.hpp>
#include <networkit/distance/DynSSSP.hpp>
#include <networkit/dynamics/GraphEvent.hpp>

#include <algorithm>
#include <cmath>
#include <memory>
#include <omp.h>

namespace NetworKit {

class DynApproxBetweenness : public Centrality, public DynAlgorithm {

public:
    DynApproxBetweenness(const Graph &G, double epsilon = 0.01, double delta = 0.1,
                         bool storePredecessors = true, double universalConstant = 0.5);

    void run() override;

    void update(GraphEvent e) override;

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

    count getNumberOfSamples() const noexcept;

private:
    void sampleNewPaths(count start, count end);
    double epsilon;
    double delta;
    bool storePreds;
    const double universalConstant;
    count r;
    std::vector<std::unique_ptr<DynSSSP>> sssp;
    std::vector<std::vector<count>> npaths;

    std::vector<node> u;
    std::vector<node> v;
    std::vector<std::vector<node>> sampledPaths;

    static constexpr edgeweight infDist = std::numeric_limits<edgeweight>::max();

    std::vector<node> sortComponentsTopologically(Graph &sccDAG, StronglyConnectedComponents &scc);

    count computeVDdirected();
};

} /* namespace NetworKit */

#endif // NETWORKIT_CENTRALITY_DYN_APPROX_BETWEENNESS_HPP_