// DGMaxFlow.java
// Ilya Razenshteyn and Contributors, 2021
// Modified by Andrew Davison, ad@coe.psu.ac.th, Jan. 2023

/* Utilize the Edmonds-Karp algorithm to find the 
   maximum flow through a directed graph, where the maximum flow 
   permitted along an edge is given by a positive weight.

   The flow begins at a node called the source (s) and flows to a 
   node designated as the sink (t).

   For more info, see:
     * https://en.wikipedia.org/wiki/Maximum_flow_problem
     * https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

  Usage:
    > compile DGMaxFlow.java
    > run DGMaxFlow
*/

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.graph.*;

import org.jgrapht.alg.flow.*;
import org.jgrapht.alg.interfaces.*;


public class DGMaxFlow
{

  public static void main(String args[])
  {
    Graph<String, WeightedEdge> g =
                 new SimpleDirectedWeightedGraph<>(WeightedEdge.class);
    Graphs.addAllVertices(g, Arrays.asList(
                          "s", "v1", "v2", "v3", "v4", "t"));
                          // s is the source; t is the sink
    Graphs.addEdge(g, "s", "v1", 16);
    Graphs.addEdge(g, "s", "v2", 13);   // weights == max flow
    Graphs.addEdge(g, "v1", "v3", 12);
    Graphs.addEdge(g, "v2", "v1", 4);
    Graphs.addEdge(g, "v2", "v4", 14);
    Graphs.addEdge(g, "v3", "v2", 9);
    Graphs.addEdge(g, "v4", "v3", 7);
    Graphs.addEdge(g, "v3", "t", 20);
    Graphs.addEdge(g, "v4", "t", 4);

    JGTUtils.displayAsDOT(g);

    MaximumFlowAlgorithm<String, WeightedEdge> mfa =
                                    new EdmondsKarpMFImpl<>(g);
   
    System.out.println("\nMax flow s to t: " + 
                             mfa.getMaximumFlowValue("s", "t"));

    Map<WeightedEdge, Double> mapFlow = 
                             mfa.getMaximumFlow("s", "t").getFlowMap();
    System.out.println("Map of edges to flows:");
    for (WeightedEdge e : mapFlow.keySet()) {
      System.out.println(" " + g.getEdgeSource(e) + " -> " + 
                               g.getEdgeTarget(e) + 
                        ": flow/weight: " + mapFlow.get(e) +
                                      "/" + g.getEdgeWeight(e));
    }
  } /* main */


}  // end of DGMaxFlow class