Java Program to Implement Max-Flow Min-Cut Theorem

«
»
This Java program is to Implement Max Flow Min Cut theorem. In optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the minimum capacity that when removed in a specific way from the network causes the situation that no flow can pass from the source to the sink.

Here is the source code of the Java program to implement Max Flow Min Cut theorem. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.util.ArrayList;
  2. import java.util.HashSet;
  3. import java.util.Iterator;
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  6. import java.util.Scanner;
  7. import java.util.Set;
  8.  
  9. public class MaxFlowMinCut
  10. {
  11.     private int[] parent;
  12.     private Queue<Integer> queue;
  13.     private int numberOfVertices;
  14.     private boolean[] visited;
  15.     private Set<Pair> cutSet;
  16.     private ArrayList<Integer> reachable;
  17.     private ArrayList<Integer> unreachable;
  18.  
  19.     public MaxFlowMinCut (int numberOfVertices)
  20.     {
  21.         this.numberOfVertices = numberOfVertices;
  22.         this.queue = new LinkedList<Integer>();
  23.         parent = new int[numberOfVertices + 1];
  24.         visited = new boolean[numberOfVertices + 1];
  25.         cutSet = new HashSet<Pair>();
  26.         reachable = new ArrayList<Integer>();
  27.         unreachable = new ArrayList<Integer>();
  28.     }
  29.  
  30.     public boolean bfs (int source, int goal, int graph[][])
  31.     {
  32.         boolean pathFound = false;
  33.         int destination, element;
  34.         for (int vertex = 1; vertex <= numberOfVertices; vertex++)
  35.         {
  36.             parent[vertex] = -1;
  37.             visited[vertex] = false;
  38.         }
  39.         queue.add(source);
  40.         parent[source] = -1;
  41.         visited[source] = true;
  42.  
  43.         while (!queue.isEmpty())
  44.         {
  45.             element = queue.remove();
  46.             destination = 1;
  47.             while (destination <= numberOfVertices)
  48.             {
  49.                 if (graph[element][destination] > 0 &&  !visited[destination])
  50.                 {
  51.                     parent[destination] = element;
  52.                     queue.add(destination);
  53.                     visited[destination] = true;
  54.                 }
  55.                 destination++;
  56.             }
  57.         }
  58.  
  59.         if (visited[goal])
  60.         {
  61.             pathFound = true;
  62.         }
  63.         return pathFound;
  64.     }
  65.  
  66.     public int  maxFlowMinCut (int graph[][], int source, int destination)
  67.     {
  68.         int u, v;
  69.         int maxFlow = 0;
  70.         int pathFlow;
  71.         int[][] residualGraph = new int[numberOfVertices + 1][numberOfVertices + 1];
  72.  
  73.         for (int sourceVertex = 1; sourceVertex <= numberOfVertices; sourceVertex++)
  74.         {
  75.             for (int destinationVertex = 1; destinationVertex <= numberOfVertices; destinationVertex++)
  76.             {
  77.                 residualGraph[sourceVertex][destinationVertex] = graph[sourceVertex][destinationVertex];
  78.             }
  79.         }
  80.  
  81.         /*max flow*/
  82.         while (bfs(source, destination, residualGraph))
  83.         {
  84.             pathFlow = Integer.MAX_VALUE;
  85.             for (v = destination; v != source; v = parent[v])
  86.             {
  87.                 u = parent[v];
  88.                 pathFlow = Math.min(pathFlow,residualGraph[u][v]);
  89.             }
  90.             for (v = destination; v != source; v = parent[v])
  91.             {
  92.                 u = parent[v];
  93.                 residualGraph[u][v] -= pathFlow;
  94.                 residualGraph[v][u] += pathFlow;
  95.             }
  96.             maxFlow += pathFlow;	
  97.         }
  98.  
  99.         /*calculate the cut set*/		
  100.         for (int vertex = 1; vertex <= numberOfVertices; vertex++)
  101.         {
  102.             if (bfs(source, vertex, residualGraph))
  103.             {
  104.                 reachable.add(vertex);
  105.             }
  106.             else
  107.             {
  108.                 unreachable.add(vertex);
  109.             }
  110.         }
  111.         for (int i = 0; i < reachable.size(); i++)
  112.         {
  113.             for (int j = 0; j < unreachable.size(); j++)
  114.             {
  115.                 if (graph[reachable.get(i)][unreachable.get(j)] > 0)
  116.                 {
  117.                     cutSet.add(new Pair(reachable.get(i), unreachable.get(j)));
  118.                 }
  119.             }
  120.         }
  121.         return maxFlow;
  122.     }
  123.  
  124.     public void printCutSet ()
  125.     {
  126.         Iterator<Pair> iterator = cutSet.iterator();
  127.         while (iterator.hasNext())
  128.         {
  129.             Pair pair = iterator.next();
  130.             System.out.println(pair.source + "-" + pair.destination);
  131.         }
  132.     }
  133.  
  134.     public static void main (String...arg)
  135.     {
  136.         int[][] graph;
  137.         int numberOfNodes;
  138.         int source;
  139.         int sink;
  140.         int maxFlow;
  141.  
  142.         Scanner scanner = new Scanner(System.in);
  143.         System.out.println("Enter the number of nodes");
  144.         numberOfNodes = scanner.nextInt();
  145.         graph = new int[numberOfNodes + 1][numberOfNodes + 1];
  146.  
  147.         System.out.println("Enter the graph matrix");
  148.         for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)
  149.         {
  150.             for (int destinationVertex = 1; destinationVertex <= numberOfNodes ; destinationVertex++)
  151.             {
  152.                 graph[sourceVertex][destinationVertex] = scanner.nextInt();
  153.             }
  154.         }
  155.         System.out.println("Enter the source of the graph");
  156.         source= scanner.nextInt();
  157.  
  158.         System.out.println("Enter the sink of the graph");
  159.         sink = scanner.nextInt();
  160.  
  161.         MaxFlowMinCut maxFlowMinCut = new MaxFlowMinCut(numberOfNodes);
  162.         maxFlow = maxFlowMinCut.maxFlowMinCut(graph, source, sink);
  163.  
  164.         System.out.println("The Max Flow is " + maxFlow);
  165.         System.out.println("The Cut Set is ");
  166.         maxFlowMinCut.printCutSet();
  167.         scanner.close();
  168.     }
  169. }
  170.  
  171. class Pair
  172. {
  173.     public int source;
  174.     public int destination;
  175.  
  176.     public Pair (int source, int destination)
  177.     {
  178.         this.source = source;
  179.         this.destination = destination;
  180.     }
  181.  
  182.     public Pair()
  183.     {
  184.     }
  185. }


$javac MaxFlowMinCut.java
$java MaxFlowMinCut
Enter the number of nodes
6
Enter the graph matrix
0 16 13 0 0 0
0 0  10 12 0 0
0 4 0 0 14 0
0 0 9 0 0 20
0 0 0 7 0 4
0 0 0 0 0 0
Enter the source of the graph
1
Enter the sink of the graph
6
The Max Flow is 23
The Cut Set is 
5-4
5-6
2-4

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.