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 ScapeGoat Tree
Java Program to Implement Warshall Algorithm
Spring Boot Configuration with Jasypt
Java Program to Find All Pairs Shortest Path
Java Program to Implement the Binary Counting Method to Generate Subsets of a Set
Refactoring Design Pattern với tính năng mới trong Java 8
Custom Thread Pools In Java 8 Parallel Streams
RestTemplate Post Request with JSON
Java Program to Implement PrinterStateReasons API
Java Program to Implement Sorted Array
Simple Single Sign-On with Spring Security OAuth2
Guide to UUID in Java
Java Scanner hasNext() vs. hasNextLine()
HashMap trong Java hoạt động như thế nào?
Java Program to Implement Dijkstra’s Algorithm using Set
Giới thiệu Java 8
Tạo chương trình Java đầu tiên sử dụng Eclipse
Get and Post Lists of Objects with RestTemplate
New Features in Java 8
Map Interface trong java
Inject Parameters into JUnit Jupiter Unit Tests
Spring Cloud – Adding Angular
Encode a String to UTF-8 in Java
Converting Between an Array and a Set in Java
Java Program to Check whether Directed Graph is Connected using BFS
How to Get All Spring-Managed Beans?
Java Program to Implement Control Table
Java Program to Encode a Message Using Playfair Cipher
Java Program to Implement DelayQueue API
A Guide to Apache Commons Collections CollectionUtils
A Guide to Spring Cloud Netflix – Hystrix
Java Program to Find Number of Articulation points in a Graph