package DynamicProgramming;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;

public class FordFulkerson {
 final static int INF = 987654321;
 // edges
 static int V;
 static int[][] capacity, flow;

 public static void main(String[] args) {
 System.out.println("V : 6");
 V = 6;
 capacity = new int[V][V];

 capacity[0][1] = 12;
 capacity[0][3] = 13;
 capacity[1][2] = 10;
 capacity[2][3] = 13;
 capacity[2][4] = 3;
 capacity[2][5] = 15;
 capacity[3][2] = 7;
 capacity[3][4] = 15;
 capacity[4][5] = 17;

 System.out.println("Max capacity in networkFlow : " + networkFlow(0, 5));
 }

 private static int networkFlow(int source, int sink) {
 flow = new int[V][V];
 int totalFlow = 0;
 while (true) {
 Vector<Integer> parent = new Vector<>(V);
 for (int i = 0; i < V; i++)
 parent.add(-1);
 Queue<Integer> q = new LinkedList<>();
 parent.set(source, source);
 q.add(source);
 while (!q.isEmpty() && parent.get(sink) == -1) {
 int here = q.peek();
 q.poll();
 for (int there = 0; there < V; ++there)
 if (capacity[here][there] - flow[here][there] > 0 && parent.get(there) == -1) {
 q.add(there);
 parent.set(there, here);
 }
 }
 if (parent.get(sink) == -1)
 break;

 int amount = INF;
 String printer = "path : ";
 StringBuilder sb = new StringBuilder();
 for (int p = sink; p != source; p = parent.get(p)) {
 amount = Math.min(capacity[parent.get(p)][p] - flow[parent.get(p)][p], amount);
 sb.append(p + "-");
 }
 sb.append(source);
 for (int p = sink; p != source; p = parent.get(p)) {
 flow[parent.get(p)][p] += amount;
 flow[p][parent.get(p)] -= amount;
 }
 totalFlow += amount;
 printer += sb.reverse() + " / max flow : " + totalFlow;
 System.out.println(printer);
 }

 return totalFlow;
 }
}