Program Listing for File PrunedLandmarkLabeling.hpp¶

#ifndef NETWORKIT_DISTANCE_PRUNED_LANDMARK_LABELING_HPP_
#define NETWORKIT_DISTANCE_PRUNED_LANDMARK_LABELING_HPP_

#include <utility>
#include <vector>

#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

class PrunedLandmarkLabeling : public Algorithm {

public:
    PrunedLandmarkLabeling(const Graph &G);

    void run() override;

    count query(node u, node v) const;

protected:
    count queryImpl(node u, node v, node upperBound = none) const;

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

    struct Label {
        Label() : node_(none), distance_(infDist) {}
        Label(node node_, count distance_) : node_(node_), distance_(distance_) {}
        node node_;
        count distance_;
    };

    const Graph *G;
    std::vector<node> nodesSortedByDegreeDesc;
    std::vector<bool> visited;
    std::vector<std::vector<Label>> labelsOut, labelsIn;
    std::vector<Label> labelsUCopy, labelsVCopy;

    template <bool Reverse = false>
    void prunedBFS(node root, node rankOfRootNode);

    auto getSourceLabelsIterators(node u, bool reverse = false) const {
        if (reverse)
            return std::make_pair(labelsIn[u].begin(), labelsIn[u].end());
        else
            return std::make_pair(labelsOut[u].begin(), labelsOut[u].end());
    }

    auto getTargetLabelsIterators(node u) const {
        return std::make_pair(labelsOut[u].begin(), labelsOut[u].end());
    }
};

} // namespace NetworKit

#endif // NETWORKIT_DISTANCE_PRUNED_LANDMARK_LABELING_HPP_