Program Listing for File SuccessiveShortestPath.hpp¶

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

#ifndef NETWORKIT_FLOW_SUCCESSIVE_SHORTEST_PATH_HPP_
#define NETWORKIT_FLOW_SUCCESSIVE_SHORTEST_PATH_HPP_

#include <span>

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

namespace NetworKit {
class SuccessiveShortestPathMinCostFlow : public Algorithm {
    using cost = edgeweight;

public:
    SuccessiveShortestPathMinCostFlow(const Graph &G, std::string_view capacityName,
                                      std::string_view supplyName);

    void run() override;

    double getTotalCost() const {
        assureFinished();
        return totalCost;
    }

    Graph::EdgeDoubleAttribute getFlow() const {
        assureFinished();
        return flows;
    }

private:
    struct NodeWithCost {
        cost distance;
        node u;
    };
    std::vector<cost> computeNodePotentials(count numberOfNodes) const;
    void dijkstraOnResidualGraph(node start, std::span<const cost> nodePotential,
                                 std::span<cost> distances, std::span<node> parentNode,
                                 std::span<edgeid> parentEdge, std::span<int> parentDirection,
                                 const Graph::EdgeDoubleAttribute &capacities) const;
    const Graph *graph;
    const std::string capacityAttributeName;
    const std::string supplyAttributeName;
    Graph residualGraph;
    static constexpr const char *FLOW = "flow";
    Graph::EdgeDoubleAttribute flows;
    cost totalCost;
    static constexpr cost infiniteCosts = std::numeric_limits<cost>::infinity();
    static constexpr double epsilon = 1e-12;
};

} // namespace NetworKit
#endif // NETWORKIT_FLOW_SUCCESSIVE_SHORTEST_PATH_HPP_