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.
import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Set; public class MaxFlowMinCut { private int[] parent; private Queue<Integer> queue; private int numberOfVertices; private boolean[] visited; private Set<Pair> cutSet; private ArrayList<Integer> reachable; private ArrayList<Integer> unreachable; public MaxFlowMinCut (int numberOfVertices) { this.numberOfVertices = numberOfVertices; this.queue = new LinkedList<Integer>(); parent = new int[numberOfVertices + 1]; visited = new boolean[numberOfVertices + 1]; cutSet = new HashSet<Pair>(); reachable = new ArrayList<Integer>(); unreachable = new ArrayList<Integer>(); } public boolean bfs (int source, int goal, int graph[][]) { boolean pathFound = false; int destination, element; for (int vertex = 1; vertex <= numberOfVertices; vertex++) { parent[vertex] = -1; visited[vertex] = false; } queue.add(source); parent = -1; visited = true; while (!queue.isEmpty()) { element = queue.remove(); destination = 1; while (destination <= numberOfVertices) { if (graph[element][destination] > 0 && !visited[destination]) { parent[destination] = element; queue.add(destination); visited[destination] = true; } destination++; } } if (visited[goal]) { pathFound = true; } return pathFound; } public int maxFlowMinCut (int graph[][], int source, int destination) { int u, v; int maxFlow = 0; int pathFlow; int[][] residualGraph = new int[numberOfVertices + 1][numberOfVertices + 1]; for (int sourceVertex = 1; sourceVertex <= numberOfVertices; sourceVertex++) { for (int destinationVertex = 1; destinationVertex <= numberOfVertices; destinationVertex++) { residualGraph[sourceVertex][destinationVertex] = graph[sourceVertex][destinationVertex]; } } /*max flow*/ while (bfs(source, destination, residualGraph)) { pathFlow = Integer.MAX_VALUE; for (v = destination; v != source; v = parent[v]) { u = parent[v]; pathFlow = Math.min(pathFlow,residualGraph[u][v]); } for (v = destination; v != source; v = parent[v]) { u = parent[v]; residualGraph[u][v] -= pathFlow; residualGraph[v][u] += pathFlow; } maxFlow += pathFlow; } /*calculate the cut set*/ for (int vertex = 1; vertex <= numberOfVertices; vertex++) { if (bfs(source, vertex, residualGraph)) { reachable.add(vertex); } else { unreachable.add(vertex); } } for (int i = 0; i < reachable.size(); i++) { for (int j = 0; j < unreachable.size(); j++) { if (graph[reachable.get(i)][unreachable.get(j)] > 0) { cutSet.add(new Pair(reachable.get(i), unreachable.get(j))); } } } return maxFlow; } public void printCutSet () { Iterator<Pair> iterator = cutSet.iterator(); while (iterator.hasNext()) { Pair pair = iterator.next(); System.out.println(pair.source + "-" + pair.destination); } } public static void main (String...arg) { int[][] graph; int numberOfNodes; int source; int sink; int maxFlow; Scanner scanner = new Scanner(System.in); System.out.println("Enter the number of nodes"); numberOfNodes = scanner.nextInt(); graph = new int[numberOfNodes + 1][numberOfNodes + 1]; System.out.println("Enter the graph matrix"); for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++) { for (int destinationVertex = 1; destinationVertex <= numberOfNodes ; destinationVertex++) { graph[sourceVertex][destinationVertex] = scanner.nextInt(); } } System.out.println("Enter the source of the graph"); source= scanner.nextInt(); System.out.println("Enter the sink of the graph"); sink = scanner.nextInt(); MaxFlowMinCut maxFlowMinCut = new MaxFlowMinCut(numberOfNodes); maxFlow = maxFlowMinCut.maxFlowMinCut(graph, source, sink); System.out.println("The Max Flow is " + maxFlow); System.out.println("The Cut Set is "); maxFlowMinCut.printCutSet(); scanner.close(); } } class Pair { public int source; public int destination; public Pair (int source, int destination) { this.source = source; this.destination = destination; } public Pair() { } }
$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
Related posts:
Java Program to Implement Self organizing List
Java Program to Implement Levenshtein Distance Computing Algorithm
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Một số ký tự đặc biệt trong Java
Java Program to Implement Network Flow Problem
Java Program to Implement Sorted Singly Linked List
A Guide to Iterator in Java
Java Program to Implement the RSA Algorithm
Apache Commons Collections MapUtils
Java – String to Reader
Java Program to Find Second Smallest of n Elements with Given Complexity Constraint
The DAO with Spring and Hibernate
How to Kill a Java Thread
Java Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Conne...
A Guide to @RepeatedTest in Junit 5
MyBatis with Spring
Java Program to Implement Interpolation Search Algorithm
Chương trình Java đầu tiên
How to Read a File in Java
Prevent Brute Force Authentication Attempts with Spring Security
Java Program to Implement Cartesian Tree
Java Program to Find the Nearest Neighbor Using K-D Tree Search
Testing in Spring Boot
Returning Image/Media Data with Spring MVC
Hướng dẫn Java Design Pattern – Proxy
Java equals() and hashCode() Contracts
Java Program to Implement Range Tree
Lập trình đa luồng với CompletableFuture trong Java 8
Guide to java.util.concurrent.Locks
Guide to the Java TransferQueue
Assert an Exception is Thrown in JUnit 4 and 5
Java Program to Check for balanced parenthesis by using Stacks