Program Listing for File DynKatzCentrality.hpp¶

/*
 * DynKatzCentrality.hpp
 *
 *  Created on: April 2018
 *      Author: Alexander van der Grinten
 *      based on code by Elisabetta Bergamini
 */

#ifndef NETWORKIT_CENTRALITY_DYN_KATZ_CENTRALITY_HPP_
#define NETWORKIT_CENTRALITY_DYN_KATZ_CENTRALITY_HPP_

#include <networkit/auxiliary/PrioQueue.hpp>
#include <networkit/base/DynAlgorithm.hpp>
#include <networkit/centrality/Centrality.hpp>
#include <networkit/dynamics/GraphEvent.hpp>

namespace NetworKit {

class DynKatzCentrality : public Centrality, public DynAlgorithm {
protected:
    double alpha; // damping
    count k;
    count maxdeg;
    bool groupOnly;

    // Nodes that have Katz score that only differ by this constant might appear
    // swapped in the ranking.
    double rankTolerance;

public:
    bool useQueue = false;

public:
    DynKatzCentrality(const Graph &G, count k, bool groupOnly = false, double tolerance = 1e-9);

    void run() override;

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

    void update(GraphEvent singleEvent) override {
        std::vector<GraphEvent> events{singleEvent};
        updateBatch(events);
    }

    node top(count n = 0) {
        assert(activeRanking.size() > n);
        return activeRanking[n];
    }

    double bound(node v);

    bool areDistinguished(node u, node v);

private:
    bool areSufficientlyRanked(node high, node low);

    void doIteration();

    bool checkConvergence();

    std::vector<bool> isActive;
    std::vector<node> activeRanking;
    Aux::PrioQueue<double, node> activeQueue;
    bool filledQueue = false;

    std::vector<double> baseData;
    std::vector<double> boundData;

public: // TODO: This is public because tests access it.
    std::vector<std::vector<count>> nPaths;
    count levelReached = 0;
};

} /* namespace NetworKit */
#endif // NETWORKIT_CENTRALITY_DYN_KATZ_CENTRALITY_HPP_