Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include "Alg/Flow/MaxFlow.hpp"
       4             : #include "Alg/Graph.hpp"
       5             : #include "Alg/ShortestPath/ShortestPathOneOne.hpp"
       6             : 
       7             : namespace Alg::Flow {
       8             : /**
       9             :  * @brief Maximum flow between two pairs of nodes.
      10             :  *
      11             :  * In these algorithms, the weight of edges is considered to be their capacities.
      12             :  */
      13       93778 : class EdmondsKarp: public MaxFlow {
      14             :     ShortestPath::ShortestPathOneOne &sp;
      15             : 
      16             :     const Graph *originalGraph = nullptr;
      17             : 
      18       93778 :     class EGraph: public Graph {
      19             :         std::vector<std::pair<Graph::Node, size_t>> edges;
      20             : 
      21             :        public:
      22             :         void addEdge(Edge::ID id, Node u, Node v, Edge::Weight c);
      23             : 
      24             :         Graph::Edge &getEdge(Graph::Edge::ID);
      25             :     };
      26             : 
      27             :     // Residual graph
      28             :     EGraph Gf;
      29             : 
      30             :     void buildResidualGraph(const Graph &G);
      31             : 
      32             :    public:
      33             :     EdmondsKarp(ShortestPath::ShortestPathOneOne &sp);
      34             : 
      35             :     virtual Graph::Edge::Weight solve(
      36             :         const Graph &G,
      37             :         Graph::Node  source,
      38             :         Graph::Node  sink
      39             :     );
      40             :     virtual Graph getFlowsGraph() const;
      41             : };
      42             : }  // namespace Alg::Flow