Program Listing for File FloydWarshall.hpp¶

/*  FloydWarshall.hpp
 *
 *  Created on: 15.02.2025
 *  Authors: Andreas Scharf (andreas.b.scharf@gmail.com)
 *
 */

#ifndef NETWORKIT_DISTANCE_FLOYD_WARSHALL_HPP_
#define NETWORKIT_DISTANCE_FLOYD_WARSHALL_HPP_

#include <limits>
#include <vector>

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

namespace NetworKit {

template <typename GraphT>
class GenericFloydWarshall : public Algorithm {
public:
    using NodeT = typename GraphT::NodeT;
    using EdgeWeightT = typename GraphT::EdgeWeightT;
    using DistanceT = edgeweight;

    GenericFloydWarshall(const GraphT &G);
    void run() override;

    DistanceT getDistance(NodeT source, NodeT target) const;
    bool isNodeInNegativeCycle(NodeT u) const;

    std::vector<NodeT> getNodesOnShortestPath(NodeT source, NodeT target) const;

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

private:
    const GraphT *graph;
    static constexpr DistanceT infiniteDistance = std::numeric_limits<DistanceT>::max();
    std::vector<std::vector<DistanceT>> distances;
    std::vector<bool> nodesInNegativeCycle;
    std::vector<std::vector<NodeT>> pathMatrix;
    std::vector<std::vector<count>> hops;
    void tagNegativeCycles();
};

using FloydWarshall = GenericFloydWarshall<Graph>;

} // namespace NetworKit

#include <networkit/distance/FloydWarshallImpl.hpp>

#endif // NETWORKIT_DISTANCE_FLOYD_WARSHALL_HPP_