Network Flow Algorithm: Ford-Fulkarson’s Algorithm

Let us consider a directed graph G = (V, E), along with special vertices s and t called the source and target. Here, u → v denotes the directed edge from vertex u to vertex v.

If we want to determine the maximum possible transport from one city to another over the connecting roads where roads are unidirectional having limited capacity of transportation, we have to use a network flow algorithm.

Here, we consider the cities as vertices of the graph and roads as edges, where maximum material transport over using the road is the weight of the edge.

Intuitively, the maximum flow problem asks for the largest amount of material that can be transported from one vertex to another; the minimum cut problem asks for the minimum damage needed to separate two vertices.

---

Flow

An (s, t )-flow (or just a flow if the source and target are clear from context) is a function that satisfies the following conservation constraint at every vertex v except possibly s and t:

We say that a flow f is feasible (with respect to c) if f(e) ≤ c(e) for every edge e. Most of the time we will consider only flows that are feasible with respect to some fixed capacity function c. We say that a flow f saturates edge e if f(e) = c(e), and avoids edge e if f(e) = 0. The maximum flow problem is to compute a feasible (s, t)-flow in a given directed graph, with a given capacity function, whose value is as large as possible.

Each edge is labelled with its flow/capacity.

---

Cuts

An (s, t )-cut is a partition of the vertices into disjoint subsets S and T - meaning S ∪ T = V and S ∩ T = φ where s ∈ S and t ∈ T. If we have a capacity function c: E → R, the capacity of a cut is the sum of the capacities of the edges that start in S and ending in T:

|| S, T||:= ∑_v∈S ∑_w∈T c(v → w)

Notice that the definition is asymmetric; edges that start in T and end in S are unimportant. The minimum cut problem is to compute an (s, t)-cut whose capacity is as large as possible.

---

The Max-Flow Min-Cut Theorem

The value of the maximum flow is equal to the capacity of the minimum cut.

Let f be a feasible flow. We define a new capacity function c_f: V x V → R, called the residual capacity, as follows:

cf(u → v)	=	c(u → v) - f(u → v)	if u → v 2 ∈ E
	=	f(v → u)	if v → u ∈ E
	=	0	otherwise

Source code

#include <stdio.h> #define WHITE 0 #define GRAY 1 #define BLACK 2 #define MAX_NODES 1000 #define oo 1000000000 int n; // number of nodes int e; // number of edges int capacity[MAX_NODES][MAX_NODES]; // capacity matrix int flow[MAX_NODES][MAX_NODES]; // flow matrix int color[MAX_NODES]; // needed for breadth-first search int pred[MAX_NODES]; // array to store augmenting path int min (int x, int y) { return x < y ? x : y; // returns minimum of x and y } int head,tail; int q[MAX_NODES+2]; void enqueue (int x) { q[tail] = x; tail++; color[x] = GRAY; } int dequeue () { int x = q[head]; head++; color[x] = BLACK; return x; } int bfs (int start, int target) { int u,v; for (u=0; u<n; u++) { color[u] = WHITE; } head = tail = 0; enqueue(start); pred[start] = -1; while (head!=tail) { u = dequeue(); // Search all adjacent white nodes v. If the capacity from u to v in the residual network is positive, enqueue v. for (v=0; v<n; v++) { if (color[v]==WHITE && capacity[u][v]-flow[u][v]>0) { enqueue(v); pred[v] = u; } } } // If the color of the target node is black now, it means that we reached it. return color[target]==BLACK; } int max_flow (int source, int sink) { int i,j,u; // Initialize empty flow. int max_flow = 0; for (i=0; i<n; i++) { for (j=0; j<n; j++) { flow[i][j] = 0; } } // While there exists an augmenting path, // increment the flow along this path. while (bfs(source,sink)) { // Determine the amount by which we can increment the flow. int increment = oo; for (u=n-1; pred[u]>=0; u=pred[u]) { increment = min(increment,capacity[pred[u]][u]-flow[pred[u]][u]); } // Now increment the flow. for (u=n-1; pred[u]>=0; u=pred[u]) { flow[pred[u]][u] += increment; flow[u][pred[u]] -= increment; } max_flow += increment; } // No augmenting path anymore. We are done. return max_flow; } void read_input_file() { int a,b,c,i,j; FILE* input = fopen("data.txt","r"); // read number of nodes and edges fscanf(input,"%d %d",&n,&e); printf("\nNumber of Vertices : %d Edges : %d",n,e); // initialize empty capacity matrix for (i=0; i<n; i++) { for (j=0; j<n; j++) { capacity[i][j] = 0; } } // read edge capacities for (i=0; i<e; i++) { fscanf(input,"%d %d %d",&a,&b,&c); capacity[a][b] = c; printf("\nA : %d B : %d Capacity : %d",a,b,c); } fclose(input); } int main () { read_input_file(); printf("\nPlease enter Source(s) and Sink(t) :\n"); int s=0,t=n-1; scanf("%d %d",&s,&t); printf("\nMax Flow : %d\n",max_flow(s,t)); return 0; }

---

Happy Exploring!