Program Listing for File SSSP.hpp¶

/*
 * SSSP.hpp
 *
 *  Created on: 15.04.2014
 *      Author: cls
 */

#ifndef NETWORKIT_DISTANCE_SSSP_HPP_
#define NETWORKIT_DISTANCE_SSSP_HPP_

#include <set>
#include <stack>

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

namespace NetworKit {

class SSSP : public Algorithm {

public:
    SSSP(const Graph &G, node source, bool storePaths = true,
         bool storeNodesSortedByDistance = false, node target = none);

    ~SSSP() override = default;

    void run() override = 0;

    const std::vector<edgeweight> &getDistances();

    edgeweight distance(node t) const;

    bigfloat numberOfPaths(node t) const;

    double _numberOfPaths(node t) const;

    const std::vector<node> &getPredecessors(node t) const;

    std::vector<node> getPath(node t, bool forward = true) const;

    std::set<std::vector<node>> getPaths(node t, bool forward = true) const;

    /* Returns the number of shortest paths to node t.*/
    bigfloat getNumberOfPaths(node t) const;

    const std::vector<node> &getNodesSortedByDistance() const;

    count getReachableNodes() const {
        assureFinished();
        return reachedNodes;
    }

    void setSource(node newSource) {
        if (!G->hasNode(newSource))
            throw std::runtime_error("Error: node not in the graph.");
        source = newSource;
    }

    void setTarget(node newTarget) {
        if (!G->hasNode(newTarget))
            throw std::runtime_error("Error: node not in the graph.");
        target = newTarget;
    }

    double getSumOfDistances() const {
        assureFinished();
        return sumDist;
    }

protected:
    const Graph *G;
    node source;
    node target;
    double sumDist;
    count reachedNodes;
    std::vector<edgeweight> distances;
    std::vector<std::vector<node>> previous; // predecessors on shortest path
    std::vector<bigfloat> npaths;

    std::vector<node> nodesSortedByDistance;

    bool storePaths;
    bool storeNodesSortedByDistance;
};

inline edgeweight SSSP::distance(node t) const {
    return distances[t];
}

inline bigfloat SSSP::numberOfPaths(node t) const {
    if (!storePaths) {
        throw std::runtime_error("number of paths have not been stored");
    }
    return npaths[t];
}

inline double SSSP::_numberOfPaths(node t) const {
    if (!storePaths) {
        throw std::runtime_error("number of paths have not been stored");
    }
    bigfloat limit = std::numeric_limits<double>::max();
    if (npaths[t] > limit) {
        throw std::overflow_error("number of paths do not fit into a double");
    }
    double res;
    npaths[t].ToDouble(res);
    return res;
}

inline const std::vector<node> &SSSP::getPredecessors(node t) const {
    if (!storePaths) {
        throw std::runtime_error("predecessors have not been stored");
    }
    return previous[t];
}

inline bigfloat SSSP::getNumberOfPaths(node t) const {
    return npaths[t];
}

} /* namespace NetworKit */

#endif // NETWORKIT_DISTANCE_SSSP_HPP_