Program Listing for File STSP.hpp¶

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

#ifndef NETWORKIT_DISTANCE_STSP_HPP_
#define NETWORKIT_DISTANCE_STSP_HPP_

#include <algorithm>
#include <ranges>
#include <unordered_map>
#include <vector>

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

namespace NetworKit {

class STSP : public Algorithm {

public:
    STSP(const Graph &G, node source, node target, bool storePred = true)
        : G(&G), source(source), target(target), storePred(storePred) {
        if (!G.hasNode(source))
            throw std::runtime_error("Error: source node not in the graph!");
        if (!G.hasNode(target))
            throw std::runtime_error("Error: target node not in the graph!");
        if (source == target)
            WARN("Source and target nodes are equal!");
    }

    template <class InputIt>
    STSP(const Graph &G, node source, InputIt targetsFirst, InputIt targetsLast)
        : G(&G), source(source), targets(targetsFirst, targetsLast), storePred(false) {
        if (!G.hasNode(source))
            throw std::runtime_error("Error: source node not in the graph!");
        if (!std::all_of(targetsFirst, targetsLast, [&G](node u) { return G.hasNode(u); }))
            throw std::runtime_error("Error: target node not in the graph!");
    }

    virtual std::vector<node> getPath() const {
        checkStorePredecessors();
        assureFinished();
        return path;
    }

    const std::vector<node> &getPredecessors() const {
        checkStorePredecessors();
        assureFinished();
        return pred;
    }

    edgeweight getDistance() const {
        assureFinished();
        return distance;
    }

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

    void setSource(node newSource) {
        assert(G->hasNode(newSource));
        source = newSource;
    }

    void setTarget(node newTarget) {
        assert(G->hasNode(newTarget));
        target = newTarget;
        targets.clear();
    }

    template <class InputIt>
    void setTargets(InputIt targetsFirst, InputIt targetsLast) {
        assert(std::all_of(targetsFirst, targetsLast, [&](auto u) { return G->hasNode(u); }));
        targets.assign(targetsFirst, targetsLast);
    }

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

protected:
    const Graph *G;
    node source = none, target = none;
    std::vector<node> targets;
    const bool storePred;
    std::vector<node> pred, path;

    edgeweight distance;
    std::vector<edgeweight> distances;
    std::unordered_map<node, index> targetIdx;

    // Builds a source-target shortest path using the predecessors
    void buildPath();

    void checkStorePredecessors() const {
        if (!storePred)
            WARN("Predecessors not stored.");
    }

    void init() {
        hasRun = false;
        if (storePred)
            pred.resize(G->upperNodeIdBound());
    }
};

inline void STSP::buildPath() {
    path.clear();
    node t = target;
    while (pred[t] != source) {
        path.push_back(pred[t]);
        t = pred[t];
    }
    std::ranges::reverse(path);
}

} // namespace NetworKit

#endif // NETWORKIT_DISTANCE_STSP_HPP_