• • Max flow problem

The max flow problem can be defined as “Given a flow network as directed graph, where each edge has a capacity greater than 0 and two distinct nodes source S and sink T, find the maximum flow from source node S to sink node T.”

The condition with problem is
(1) Flow on each edge cannot exceed by its capacity.
(2) For every node the incoming  flow is equal to outgoing flow, except source node s and sink node t.

A flow that satisfies the above condition is called a feasible flow. The edge of the graph can be seen as pipelines or roads and nodes can be seen as junction. For example let us see below graph. The edge weight of the graph is flow capacity. The Ford-Fulkerson algorithm determines the maximum flow of the network from source to sink node.
Augmenting Path:

An Augmenting Path is simple path from source node to sink node ( without cycle ) , where we can send a positive flow along the path from source node to sink node. For example in above example graph , we can send a positive flow along the augmenting path 5 0 1 6.

Residual Graph:

After sending a positive flow along an augmenting path, the flow capacities of edges are being adjusted , these adjusted flow capacities are called residual capacities and the resulting graph/network is called residual graph/network.

Ford-Fulkerson Algorithm
1) Start with initial flow as 0.
2) While there is a augmenting path from source to sink.
Find the min flowcapacity
Add this min flow to the flow

3) Return flow.

Here is steps for max flow on example graph  using Ford-Fulkerson method.

Step ( 1)

Find a augmenting path from Source S to sink T.  ( 5 –> 0 -> 1 -> 6 )

Choose minimum capacity : 4 , say it f1 = 4 . Adjust the capacity of each path. Now we can see that along this augmenting path we can send maximum flow of capacity 4. Step ( 2)

Find a another augmenting path from Source S to sink T. (Let it is , 5 –> 0–> 2–>6 )

find min capacity along this path : 2. Adjust the capacities of each edge. We can send max flow along this path is 2. f2 = 2. Step ( 3)

Find a another augmenting path from Source S to sink T. (Let it is , 5 –> 3-> 4–>6)

find min capacity along this path : 2. f3 = 2, Adjust the capacities of each edge. Now there is no augmenting path from source to sink. Hence total max flow capacity is f = f1 + f2 + f3 = 4 + 2 + 2 = 8.

Here is sample implementation in c++.  For searching augmenting path from source to sink node depth first search has been used in the c++ implementation.

Max flow problem Ford Fulkerson algorithm sample code

#include <iostream>
#include <string.h>
using namespace std;

#define N 7
#define INF 9999999

// flow network
int Flow[N][N];
// visited array
bool visited[N];

// original flow network graph shown in the above example
//0 1  2  3  4 5  6
int graph[N][N] = {
{ 0, 5, 4, 0, 0, 0, 0 }, //0
{ 0, 0, 0, 0, 0, 0, 4 }, //1
{ 0, 0, 0, 3, 0, 0, 6 }, //2
{ 0, 0, 0, 0, 5, 0, 0 }, //3
{ 0, 0, 0, 0, 0, 0, 8 }, //4
{ 6, 0, 0, 2, 0, 0, 0 }, //5
{ 0, 0, 0, 0, 0, 0, 0 }, //6
};

int dfs(int s, int t, int minimum) {
visited[s] = true;

// if source and sink is same
if (s == t)
return minimum;

for (int i = 0; i < N; i++) {
int flow_capacity = graph[s][i] - Flow[s][i];
if (!visited[i] && flow_capacity > 0) {
// find min capacity in dfs path
if (int sent = dfs (i, t, min (minimum, flow_capacity))) {
// adjust the capacity
Flow[s][i] += sent;
Flow[i][s] -= sent;
return sent;
}
}
}

return false;
}

int main() {
// initialize initial flow capacity 0
memset(Flow, 0, sizeof(Flow));

// initialize visited array false initially
memset(visited, 0, sizeof(visited));

int s = 5;
int t = 6;

int max_flow = 0;
// while ther is augmenting path , from s and t
// with positive flow capacity
while (int sent = dfs(s, t, INF)) {
max_flow += sent;
// reset visited array , for searching next path
memset(visited, 0, sizeof(visited));
}
cout << "The max flow from node 5 to sink node 6 is " << max_flow;
cout << endl;
}