Practical Application: Maximum Flow Algorithm Implementation in Java

This assignment presents a Java implementation of the Maximum Flow algorithm, a fundamental concept in graph theory and computer science. The code utilizes the Dinic's algorithm to efficiently compute the maximum flow in a network represented as a graph. The solution includes the creation of a graph data structure, the addition of edges with capacities, and the implementation of the dinicBFS and dinicDFS methods for finding augmenting paths and updating flow. The driver program demonstrates the algorithm's functionality with a randomly generated graph, showcasing the calculation of maximum flow between a source and a sink node. This assignment is designed to provide students with a practical understanding of network flow algorithms and their implementation in Java, providing a valuable resource for students to learn and understand the concepts of maximum flow algorithms.

1.) Question 2 correction
import java.util.*;
public class MaximumFlow
{
static class Edge
{
int t, rev, cap, f;
public Edge(int t, int rev, int cap)
{
this.t = t;
this.rev = rev;
this.cap = cap;
}
}
//lets use the ArrayList data structure to create our graph
public static List<Edge>[] createGraph( int nodes)
{
List<Edge>[] graph = new List[nodes];//an array havind arraylist and os
size of provided nodes
for(int i = 0; i < nodes; i++)
{
graph[i] = new ArrayList<>();
}
return graph;
}
public static void addEdge(List<Edge>[] graph, int src, int dst, int cap)
//graph= our graph
// src = source "s";
//dst = sink "t";
//cap = capacity
{
graph[src].add(new Edge(dst, graph[dst].size(), cap));
graph[dst].add( new Edge(src, graph[src].size(), cap));
}
static boolean dinicBFS(List<Edge>[] graph, int src, int dest, int[] dist)
//dist = distance(path).
{
//by default lets alllocate distances to -1
Arrays.fill( dist, -1);
dist[src] = 0;//from itself =0

int [] q = new int[graph.length];
int sizeq = 0;
q[sizeq++] = src;
for(int i = 0; i < sizeq; i++)
{
int u = q[i];
for(Edge e : graph[u])
{
if(dist[e.t] < 0 && e.f < e.cap)
{
dist[e.t] = dist[u] + 1;
q[sizeq++] = e.t;
}
}
}
return dist[dest] >= 0;
}
static int dinicDFS(List<Edge>[] graph, int [] ptr, int [] dist,int dest,int u, int f)
{
if( u== dest)
return f;
for(;ptr[u] < graph[u].size();++ptr[u])
{
Edge e = graph[u].get(ptr[u]);
if(dist[e.t] == dist[u] + 1 && e.f < e.cap)
{
int df = dinicDFS(graph, ptr,dist,dest, e.t, Math.min(f, e.cap
- e.f) );
if(df > 0)
{
e.f += df;
graph[e.t].get(e.rev).f -= df;
return df;
}
}
}
return 0;
}
public static int maxFlow(List<Edge>[] graph, int src, int dest)
{
int flow = 0;

int [] dist = new int[graph.length];
while(dinicBFS(graph, src, dest, dist))
{
int [] ptr = new int[graph.length];
while(true)
{
int df = dinicDFS(graph,ptr, dist, dest, src,
Integer.MAX_VALUE);
if( df == 0)
break;
flow += df;
}
}
return flow;
}
static int RandomIntegers(int min,int max)
{
Random r = new Random();
return r.nextInt((max - min) + 1) + min;
}
//Driver program with an example
public static void main(String[] args)
{
List<Edge>[] g =createGraph(12);
int [] nodes = new int[12];//this refers to nodes inclusive
//of source and vertex
for(int i = 0; i < 12;i++)
{
nodes[i] = RandomIntegers(4,12);
}
for(int i = 1,j = 1; i < 12 && j < 12; i++, j++)
{
addEdge(g,nodes[i],nodes[j],RandomIntegers(5,20));//allocating
//capacities randomly
}
System.out.println(maxFlow(g,0,11));//returns maxFlow else zero if
//none found
}
}