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:
Đồng bộ hóa các luồng trong Java
Unsatisfied Dependency in Spring
Compact Strings in Java 9
@Order in Spring
Thao tác với tập tin và thư mục trong Java
Java Program to Perform Finite State Automaton based Search
Chuyển đổi từ HashMap sang ArrayList
Java Program to Implement Skew Heap
Model, ModelMap, and ModelAndView in Spring MVC
Java Program to Implement Leftist Heap
Introduction to Spring Boot CLI
A Guide to JUnit 5 Extensions
Java Program to Print only Odd Numbered Levels of a Tree
Java Program to Implement Interval Tree
Java – InputStream to Reader
Merging Two Maps with Java 8
Basic Authentication with the RestTemplate
Java Perform to a 2D FFT Inplace Given a Complex 2D Array
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
Semaphore trong Java
Predicate trong Java 8
The SpringJUnitConfig and SpringJUnitWebConfig Annotations in Spring 5
Lớp TreeMap trong Java
Converting Iterator to List
Sử dụng CountDownLatch trong Java
Jackson – Change Name of Field
Introduction to Spring Cloud Netflix – Eureka
Java Program to Implement Floyd-Warshall Algorithm
Comparing Two HashMaps in Java
Spring MVC Content Negotiation
Java Program to Perform Searching Based on Locality of Reference
Java Program to Implement Regular Falsi Algorithm