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:

Guide to CopyOnWriteArrayList
Tìm hiểu về xác thực và phân quyền trong ứng dụng
Java Program to Compute Discrete Fourier Transform Using Naive Approach
Guide to the ConcurrentSkipListMap
Java Program to Check Whether a Directed Graph Contains a Eulerian Path
Java Program to Permute All Letters of an Input String
Java Program to Check if a Directed Graph is a Tree or Not Using DFS
Custom Error Pages with Spring MVC
HashMap trong Java hoạt động như thế nào?
Java Program to Implement Splay Tree
Assert an Exception is Thrown in JUnit 4 and 5
Java Program to Implement PrinterStateReasons API
Java Program to Generate a Random UnDirected Graph for a Given Number of Edges
Java Program to Implement Sparse Array
Java Program to Implement Naor-Reingold Pseudo Random Function
Mapping a Dynamic JSON Object with Jackson
The XOR Operator in Java
Checking for Empty or Blank Strings in Java
Guide to java.util.concurrent.BlockingQueue
Rate Limiting in Spring Cloud Netflix Zuul
Tạo số và chuỗi ngẫu nhiên trong Java
Java Program to Find the Mode in a Data Set
Java Program to Implement Max Heap
Java Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Conne...
Hướng dẫn Java Design Pattern – Object Pool
Java Program to Perform integer Partition for a Specific Case
Java Program to Implement Interpolation Search Algorithm
Java Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm
Connect through a Proxy
Rest Web service: Filter và Interceptor với Jersey 2.x (P1)
Finding Max/Min of a List or Collection
@DynamicUpdate with Spring Data JPA