Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include "Alg/Graph.hpp"
       4             : 
       5             : namespace Alg::Flow {
       6             : /**
       7             :  * @brief Maximum flow between two pairs of nodes.
       8             :  *
       9             :  * In these algorithms, the weight of edges is considered to be their capacities.
      10             :  */
      11       93778 : class MaxFlow {
      12             :    public:
      13             :     virtual ~MaxFlow();
      14             : 
      15             :     /**
      16             :      * @brief Execute the algorithm
      17             :      *
      18             :      * @param G Graph
      19             :      * @param source Source node
      20             :      * @param sink Sink node
      21             :      * @return Graph::Edge::Weight Maximum flow between source and sink
      22             :      */
      23             :     virtual Graph::Edge::Weight solve(const Graph &G, Graph::Node source, Graph::Node sink) = 0;
      24             : 
      25             :     /**
      26             :      * @brief Retrieves the flows graph.
      27             :      *
      28             :      * The flows graph is a copy of the original graph, but where edges' weights
      29             :      * represent the flow that traverses them.
      30             :      *
      31             :      * @return  Graph::Edge Edge traversed before getting to d
      32             :      */
      33             :     virtual Graph getFlowsGraph() const = 0;
      34             : };
      35             : }  // namespace Alg::Flow