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 <limits>
#include <set>

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

namespace NetworKit {

template <class GraphT>
class SingleSourceShortestPaths : public Algorithm {
    using NodeT = typename GraphT::NodeT;
    using EdgeWeightT = typename GraphT::EdgeWeightT;
    static constexpr NodeT nullNodeId = NullNodeId<NodeT>;

public:
    SingleSourceShortestPaths(const GraphT &G, NodeT source, bool storePaths = true,
                              bool storeNodesSortedByDistance = false, NodeT target = nullNodeId);

    ~SingleSourceShortestPaths() override = default;

    void run() override = 0;

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

    EdgeWeightT distance(NodeT t) const { return distances[t]; }

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

    double _numberOfPaths(NodeT t) const;

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

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

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

    /* Returns the number of shortest paths to node t.*/
    bigfloat getNumberOfPaths(NodeT t) const { return npaths[t]; }

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

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

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

    void setTarget(NodeT 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 GraphT *G;
    NodeT source;
    NodeT target;
    double sumDist = std::numeric_limits<double>::max();
    count reachedNodes = 0;
    std::vector<EdgeWeightT> distances;
    std::vector<std::vector<NodeT>> previous; // predecessors on shortest path
    std::vector<bigfloat> npaths;

    std::vector<NodeT> nodesSortedByDistance;

    bool storePaths;
    bool storeNodesSortedByDistance;
};

template <class GraphT>
inline double SingleSourceShortestPaths<GraphT>::_numberOfPaths(NodeT 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;
}

using SSSP = SingleSourceShortestPaths<AdjListGraph<node, edgeweight>>;

} /* namespace NetworKit */

#include <networkit/distance/SSSPImpl.hpp>

#endif // NETWORKIT_DISTANCE_SSSP_HPP_