Java Program to Implement Network Flow Problem

This Java program is to Implement Network Flow problem. In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, except when it is a source, which has more outgoing flow, or sink, which has more incoming flow. A network can be used to model traffic in a road system, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

Here is the source code of the Java program to implement network flow problem. 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 NetworkFlowProb
{                                 
    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 NetworkFlowProb (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  networkFlow (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();
 
        NetworkFlowProb networkFlowProb = new NetworkFlowProb(numberOfNodes);
        maxFlow = networkFlowProb.networkFlow(graph, source, sink);
 
        System.out.println("The Max flow in the graph is " + maxFlow);
        System.out.println("The Minimum Cut Set in the Graph is ");
        networkFlowProb.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 NetworkFlowProb.java
$java NetworkFlowProb
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 in the graph is 23
The Minimum Cut Set in the Graph is 
2-4
5-6
5-4

Related posts:

Java Program to Implement Interpolation Search Algorithm
Java Program to Generate All Possible Subsets with Exactly k Elements in Each Subset
New Stream Collectors in Java 9
Spring Boot - Unit Test Cases
Java Program to Repeatedly Search the Same Text (such as Bible by building a Data Structure)
Spring Boot - Application Properties
Guide to CopyOnWriteArrayList
Đồng bộ hóa các luồng trong Java
Sử dụng CyclicBarrier trong Java
Call Methods at Runtime Using Java Reflection
Spring REST API + OAuth2 + Angular
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Java Program to Implement Graph Structured Stack
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not
Java Program to do a Depth First Search/Traversal on a graph non-recursively
Java Program to Implement Control Table
Java Program to Implement Ternary Tree
Java Program to Implement Disjoint Sets
Generating Random Dates in Java
Simultaneous Spring WebClient Calls
JUnit5 Programmatic Extension Registration with @RegisterExtension
Java Program to Find a Good Feedback Edge Set in a Graph
Xây dựng ứng dụng Client-Server với Socket trong Java
Java Program to Implement First Fit Decreasing for 1-D Objects and M Bins
Checked and Unchecked Exceptions in Java
Creating a Web Application with Spring 5
Java Program to Describe the Representation of Graph using Adjacency List
Java 8 Streams peek() API
Introduction to Spring MVC HandlerInterceptor
Converting Between a List and a Set in Java
Giới thiệu về Stream API trong Java 8
The Registration API becomes RESTful