Program Listing for File SPSP.hpp¶

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

#ifndef NETWORKIT_DISTANCE_SPSP_HPP_
#define NETWORKIT_DISTANCE_SPSP_HPP_

#include <unordered_map>
#include <vector>

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

namespace NetworKit {

class SPSP final : public Algorithm {

public:
    template <class InputIt>
    explicit SPSP(const Graph &G, InputIt sourcesFirst, InputIt sourcesLast) : G(&G) {
        setSources(sourcesFirst, sourcesLast);
    }

    template <class SourcesInputIt, class TargetsInputIt>
    explicit SPSP(const Graph &G, SourcesInputIt sourcesFirst, SourcesInputIt sourcesLast,
                  TargetsInputIt targetsFirst, TargetsInputIt targetsLast)
        : G(&G) {
        setSources(sourcesFirst, sourcesLast);
        setTargets(targetsFirst, targetsLast);
    }

    template <class InputIt>
    void setSources(InputIt sourcesFirst, InputIt sourcesLast) {
        initSourcesOrTargets(sources, sourcesFirst, sourcesLast, sourceIdx);
    }

    template <class InputIt>
    void setTargets(InputIt targetsFirst, InputIt targetsLast) {
        initSourcesOrTargets(targets, targetsFirst, targetsLast, targetIdx);
    }

    ~SPSP() override = default;

    void run() override;

    const std::vector<std::vector<edgeweight>> &getDistances() const {
        assureFinished();
        return distances;
    }

    edgeweight getDistance(node u, node v) const {
        assureFinished();
        if (targets.empty())
            return distances[sourceIdx.at(u)][v];
        else
            return distances[sourceIdx.at(u)][targetIdx.at(v)];
    }

    const std::unordered_map<node, index> &getSourceIndexMap() const noexcept { return sourceIdx; }

    const std::unordered_map<node, index> &getTargetIndexMap() const noexcept { return targetIdx; }

private:
    const Graph *G;
    std::vector<node> sources, targets;
    std::unordered_map<node, index> sourceIdx, targetIdx;
    std::vector<std::vector<edgeweight>> distances;

    template <class InputIt>
    void initSourcesOrTargets(std::vector<node> &vec, InputIt first, InputIt last,
                              std::unordered_map<node, index> &indices) {
        vec.assign(first, last);
        indices.clear();
        for (index i = 0; i < vec.size(); ++i)
            indices.emplace(vec[i], i);
    }

    void runWithTargets();
    void runWithoutTargets();
};

} // namespace NetworKit

#endif // NETWORKIT_DISTANCE_SPSP_HPP_