Program Listing for File DynBetweennessOneNode.hpp¶

/*
 * DYNBETNODE.hpp
 *
 *  Created on: 10.03.2016
 *      Author: Elisabetta Bergamini
 */

#ifndef NETWORKIT_CENTRALITY_DYN_BETWEENNESS_ONE_NODE_HPP_
#define NETWORKIT_CENTRALITY_DYN_BETWEENNESS_ONE_NODE_HPP_

#include <networkit/base/Algorithm.hpp>
#include <networkit/base/DynAlgorithm.hpp>
#include <networkit/dynamics/GraphEvent.hpp>

namespace NetworKit {

class DynBetweennessOneNode : public Algorithm, public DynAlgorithm {

public:
    DynBetweennessOneNode(Graph &G, node x);

    void run() override;

    /* Computes the betweenness centrality of x by running BFS for each node */
    void runUnweighted();

    /* Computes the betweenness centrality of x by running Dijkstra for each node */
    void runWeighted();

    void update(GraphEvent event) override;

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

    edgeweight computeScore(GraphEvent event);

    edgeweight getDistance(node u, node v);
    edgeweight getSigma(node u, node v);
    edgeweight getSigmax(node u, node v);
    edgeweight getbcx();

private:
    Graph &G;
    node x;
    // betweenness centrality of node x
    edgeweight bcx = 0;
    const edgeweight infDist = std::numeric_limits<edgeweight>::max();
    const edgeweight epsilon =
        0.0000000001; // make sure that no legitimate edge weight is below that.

    std::vector<std::vector<edgeweight>> distances;
    std::vector<std::vector<edgeweight>> distancesOld;
    // total number of shortest paths between two nodes
    std::vector<std::vector<edgeweight>> sigma;
    // number of shortest paths between two nodes that go through node x
    std::vector<std::vector<edgeweight>> sigmax;
    std::vector<std::vector<edgeweight>> sigmaxOld;

    std::vector<node> Pred;
};

} /* namespace NetworKit */

#endif // NETWORKIT_CENTRALITY_DYN_BETWEENNESS_ONE_NODE_HPP_