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.

  1. import java.util.ArrayList;
  2. import java.util.HashSet;
  3. import java.util.Iterator;
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  6. import java.util.Scanner;
  7. import java.util.Set;
  8.  
  9. public class NetworkFlowProb
  10. {                                 
  11.     private int[] parent;
  12.     private Queue<Integer> queue;
  13.     private int numberOfVertices;
  14.     private boolean[] visited;
  15.     private Set<Pair> cutSet;
  16.     private ArrayList<Integer> reachable;
  17.     private ArrayList<Integer> unreachable;
  18.  
  19.     public NetworkFlowProb (int numberOfVertices)
  20.     {
  21.         this.numberOfVertices = numberOfVertices;
  22.         this.queue = new LinkedList<Integer>();
  23.         parent = new int[numberOfVertices + 1];
  24.         visited = new boolean[numberOfVertices + 1];
  25.         cutSet = new HashSet<Pair>();
  26.         reachable = new ArrayList<Integer>();
  27.         unreachable = new ArrayList<Integer>();
  28.     }
  29.  
  30.     public boolean bfs (int source, int goal, int graph[][])
  31.     {
  32.         boolean pathFound = false;
  33.         int destination, element;
  34.         for (int vertex = 1; vertex <= numberOfVertices; vertex++)
  35.         {
  36.             parent[vertex] = -1;
  37.             visited[vertex] = false;
  38.         }
  39.         queue.add(source);
  40.         parent[source] = -1;
  41.         visited[source] = true;
  42.  
  43.         while (!queue.isEmpty())
  44.         {
  45.             element = queue.remove();
  46.             destination = 1;
  47.             while (destination <= numberOfVertices)
  48.             {
  49.                 if (graph[element][destination] > 0 &&  !visited[destination])
  50.                 {
  51.                     parent[destination] = element;
  52.                     queue.add(destination);
  53.                     visited[destination] = true;
  54.                 }
  55.                 destination++;
  56.             }
  57.         }
  58.  
  59.         if (visited[goal])
  60.         {
  61.             pathFound = true;
  62.         }
  63.         return pathFound;
  64.     }
  65.  
  66.     public int  networkFlow (int graph[][], int source, int destination)
  67.     {
  68.         int u, v;
  69.         int maxFlow = 0;
  70.         int pathFlow;
  71.         int[][] residualGraph = new int[numberOfVertices + 1][numberOfVertices + 1];
  72.  
  73.         for (int sourceVertex = 1; sourceVertex <= numberOfVertices; sourceVertex++)
  74.         {
  75.             for (int destinationVertex = 1; destinationVertex <= numberOfVertices; destinationVertex++)
  76.             {
  77.                 residualGraph[sourceVertex][destinationVertex] = graph[sourceVertex][destinationVertex];
  78.             }
  79.         }
  80.  
  81.         /*max flow*/
  82.         while (bfs(source, destination, residualGraph))
  83.         {
  84.             pathFlow = Integer.MAX_VALUE;
  85.             for (v = destination; v != source; v = parent[v])
  86.             {
  87.                 u = parent[v];
  88.                 pathFlow = Math.min(pathFlow, residualGraph[u][v]);
  89.             }
  90.             for (v = destination; v != source; v = parent[v])
  91.             {
  92.                 u = parent[v];
  93.                 residualGraph[u][v] -= pathFlow;
  94.                 residualGraph[v][u] += pathFlow;
  95.             }
  96.             maxFlow += pathFlow;	
  97.         }
  98.  
  99.         /*calculate the cut set*/		
  100.         for (int vertex = 1; vertex <= numberOfVertices; vertex++)
  101.         {
  102.             if (bfs(source, vertex, residualGraph))
  103.             {
  104.                 reachable.add(vertex);
  105.             }
  106.             else
  107.             {    
  108.                 unreachable.add(vertex);
  109.             }
  110.         }
  111.         for (int i = 0; i < reachable.size(); i++)
  112.         {
  113.             for (int j = 0; j < unreachable.size(); j++)
  114.             {
  115.                 if (graph[reachable.get(i)][unreachable.get(j)] > 0)
  116.                 {
  117.                     cutSet.add (new Pair(reachable.get(i), unreachable.get(j)));
  118.                 }
  119.             }
  120.         }
  121.         return maxFlow;
  122.     }
  123.  
  124.     public void printCutSet ()
  125.     {
  126.         Iterator<Pair> iterator = cutSet.iterator();
  127.         while (iterator.hasNext())
  128.         {
  129.             Pair pair = iterator.next();
  130.             System.out.println(pair.source + "-" + pair.destination);
  131.         }
  132.     }
  133.  
  134.     public static void main (String...arg)
  135.     {
  136.         int[][] graph;
  137.         int numberOfNodes;
  138.         int source;
  139.         int sink;
  140.         int maxFlow;
  141.  
  142.         Scanner scanner = new Scanner(System.in);
  143.         System.out.println("Enter the number of nodes");
  144.         numberOfNodes = scanner.nextInt();
  145.         graph = new int[numberOfNodes + 1][numberOfNodes + 1];
  146.  
  147.         System.out.println("Enter the graph matrix");
  148.         for (int sourceVertex = 1; sourceVertex <= numberOfNodes; sourceVertex++)
  149.         {
  150.             for (int destinationVertex = 1; destinationVertex <= numberOfNodes; destinationVertex++)
  151.             {
  152.                 graph[sourceVertex][destinationVertex] = scanner.nextInt();
  153.             }
  154.         }
  155.         System.out.println("Enter the source of the graph");
  156.         source= scanner.nextInt();
  157.  
  158.         System.out.println("Enter the sink of the graph");
  159.         sink = scanner.nextInt();
  160.  
  161.         NetworkFlowProb networkFlowProb = new NetworkFlowProb(numberOfNodes);
  162.         maxFlow = networkFlowProb.networkFlow(graph, source, sink);
  163.  
  164.         System.out.println("The Max flow in the graph is " + maxFlow);
  165.         System.out.println("The Minimum Cut Set in the Graph is ");
  166.         networkFlowProb.printCutSet();
  167.         scanner.close();
  168.     }
  169. }
  170.  
  171. class Pair
  172. {    
  173.     public int source;
  174.     public int destination;
  175.  
  176.     public Pair(int source, int destination)
  177.     {
  178.         this.source = source;
  179.         this.destination = destination;
  180.     }
  181.  
  182.     public Pair()
  183.     {
  184.     }
  185. }


$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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.