Program Listing for File Dinic.hpp¶

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

#ifndef NETWORKIT_FLOW_DINIC_HPP_
#define NETWORKIT_FLOW_DINIC_HPP_
#include <vector>
#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {
class Dinic final : public Algorithm {

public:
    Dinic(const Graph &G, node src, node dst);

    void run() override;

    edgeweight getMaxFlow() const;

private:
    void initializeResidualGraph();
    bool canReachTargetInLevelGraph();
    edgeweight computeBlockingPath();
    const Graph *graph;
    node source;
    node target;
    edgeweight maxFlow{};
    Graph residualGraph;
    std::vector<std::deque<node>> parents;
    static constexpr double RELATIVE_TOLERANCE = 1e-12;
    static constexpr double ABSOLUTE_TOLERANCE = 1e-15;
    edgeweight tolerance{};
};
} // namespace NetworKit
#endif // NETWORKIT_FLOW_DINIC_HPP_