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 Find Transitive Closure of a Graph
New Features in Java 8
Spring Boot - Google Cloud Platform
Spring Cloud AWS – RDS
Java Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph
The DAO with Spring and Hibernate
@Order in Spring
Java – Reader to String
Vấn đề Nhà sản xuất (Producer) – Người tiêu dùng (Consumer) và đồng bộ hóa các luồng trong Java
RegEx for matching Date Pattern in Java
Java Program to Implement Ford–Fulkerson Algorithm
The Registration Process With Spring Security
Converting Strings to Enums in Java
Guava Collections Cookbook
Service Registration with Eureka
How to Manually Authenticate User with Spring Security
Spring MVC Async vs Spring WebFlux
Spring Security Registration – Resend Verification Email
Java Program to Decode a Message Encoded Using Playfair Cipher
Period and Duration in Java
Java Program to Implement Adjacency Matrix
Quick Guide to @RestClientTest in Spring Boot
Giới thiệu về Stream API trong Java 8
Java Program to Implement Wagner and Fisher Algorithm for online String Matching
Lớp Collectors trong Java 8
The XOR Operator in Java
Java Program to Find the Vertex Connectivity of a Graph
Java Program to Generate All Subsets of a Given Set in the Lexico Graphic Order
Java Program to Implement Threaded Binary Tree
Xử lý ngoại lệ đối với trường hợp ghi đè phương thức trong java
Validations for Enum Types
Java Program to Implement Rope