What is Max Flow?

Given a graph representing a flow network in which one of the vertexes is considered as a source (From where the flow will start) and another single vertex as a sink (where the flow will end). Each edge has some specific capacity which represents the maximum flow through that edge.

We need to find the maximum possible flow from source to sink in the given graph (network). The maximum possible flow value is known as max flow.

Tip: Consider each edge as water pipe with a specific width (capacity in case of the graph). We need to find the maximum flow of water from source to sink in the given pipe network (Pipe with larger width/capacity will allow large flow).

Ford Fulkerson Algorithm

Ford Fulkerson Algorithm helps in finding the max flow of the graph. In the Ford-Fulkerson method, we repeatedly find augmenting path through the residual graph and augment the flow until no more augmenting paths can be found.

Residual Graph: It is the given original graph but with the extra equal number of opposite edges as total original edges in the original graph. The capacity of each opposite edge is 0.

Network Graph

Each Edge has (flow, Capacity) and initially flow = 0.

Augmenting Path: It is the path of edges in which the unused capacity is greater than 0 i.e the flow from source to sink is possible through this path.

Augment the path: Means updating the flow value of the edges along the augmenting path.

On getting any augmenting path we update the residual graph ( i.e update flow of edges in the path found). Again we recheck for augmenting path in the updated graph. If found any, then means that more amount can flow through the network graph. Hence we add the possible flow of the augmenting path to the max flow.

InShort: Repeatedly find the path through which the flow from source to sink is possible and update the flow of the graph until no such path is still left.

Java Program to Implement Ford Fulkerson Algorithm

Before starting program first we need to know how to make a network graph in a programming language.

For this, we first need to make Edge and Vertex class. Each Edge class object will represent a different edge and each Vertex class object will represent a different vertex.

So each Edge will have:

Edge class in Ford Fulkerson Algorithm

Similarly, each Vertex will have:

Vertex class in Ford Fulkerson Algorithm

So we need to create objects of Vertex and Edge class depending on the size of the graph and connect them with each other to make complete network graph.

The Ford Fulkerson algorithm is not applicable to the original graph, we need to create the residual graph of the original graph by creating opposite residual edges for each original edges.

Remember: Initially flow for all edges is 0 and capacity of residual edges should be 0.

Now apply Ford Fulkerson algorithm until no argument path is left.

Note: Backtracking is used to find the augmenting path in the residual graph.

We have made augment method in the edge class to update the flow of the current edge and to reduce the flow of the residual edge.

Remember:  Residual edge of the original edge is opposite edge and the residual edge of the opposite edge is the original edge. So in augment, we increase the flow value of the current edge (can be original or opposite edge) and decrease the flow of the corresponding residual edge.

Max Flow is the sum of all possible flow of the augmenting paths.

Output

Ford Fulkerson Max Flow Program

That’s all for Ford Fulkerson Max Flow algorithm. It is possible that you may understand this algorithm or program in one go. Give it few try and watch the video again.  You will surely start getting an idea how this algorithm works. Still you have any doubt then comment below.

Leave a Reply

Close Menu