With a huge number of people working towards technological development, complex problems are bound to come up. Thus, experts all over the world are continuously devising specific algorithms to tackle particular types of questions. One such algorithm is Ford Fulkerson Algorithm. In this blog, we shall discuss its implementation in C++ & Java.
What is Ford-Fulkerson Algorithm?
Ford-Fulkerson Algorithm is a set of steps that we follow to tackle the max-flow min-cut problem. It uses a greedy approach to find the maximum flow coming out of a flow network. Discovered in 1956 by Ford and Fulkerson, this algorithm tackles the above-stated problem in a very neat way.
Don't know what the max-flow min-cut problem is? Don't worry, let's start from the beginning.
What is Max-Flow Min-Cut Problem?
You are given a graph that represents a network flow as illustrated in the given image. Every edge of this network has a certain capacity. You are also given 2 special vertices called source 's' and sink 't'. Now, you need to find the maximum possible flow from source to sink with the following constraints:
- The flow specified for an edge does not exceed its capacity.
- The net incoming flow should be equal to the net outgoing flow except for s and t.
To understand the intuition behind this, first, let's go through some terminologies that we'll be using throughout.
Augmenting Path: The multiple paths available in the flow network.
Residual Graph: The flow network that has additional flow.
- Residual Capacity: The capacity of flow left in the edge after subtracting the flow.
Ford-Fulkerson Approach with an Example
The intuition behind solving this problem is quite simple. Let's understand this with the help of an example.
Imagine you have a network of roads from where daily certain cars travel. Take a look at below car network. Now, obviously, the roads cannot be infinitely wide, thus, they all have a fixed width that ensures only a certain number of cars travel through them at a time.
There is a starting point and a destination as well. The cars always start from the starting point and have to reach the destination. But, there are several paths to take. Let's start sending cars one by one to all the roads.
Here, you'll start by sending 2 cars for 0->1. Why? Although this road's capacity is 4 if we look further, only 2 cars can pass through 2->5. Therefore, we take 2 here. Now, 2 cars have reached their destination.
Cars Reached = 2
Now, here you'll take 3 cars and make them reach the destination by following the path mentioned.
Cars Reached = 2+3 = 5
Now, 2 cars have already gone through road 0->1 and 1->2, therefore, we'll take the remaining cars, that is, 2. Similarly, on road 2->3 we have a residual capacity of 3 so, after traveling of 2 cars, we'll have 1 over there. The same goes for the other 2 roads in this augmenting path.
Cars Reached = 5+2 = 7
Now, although we still have paths left, we don't have any augmented paths. Why? This is because the path starting from the source has ended, the roads have been full to their capacity and thus, we cannot make any more cars travel.
Therefore, the final answer comes out to be 7. In the same way, we process the maximum flow by taking cars as data or any other element.
Steps to Follow
Now that you've understood what to do, it's important that you know how to do it. Below are the steps to be followed to find the maximum flow in a network:
- Initialize the start flow as 0.
- Observe the augmenting path from source to sink.
- Find the max flow from that particular path.
- Add it to the final maximum possible flow.
What is Ford-Fulkerson Algorithm Used for?
The Ford-Fulkerson method is a popular approach for resolving network flow issues. It is employed to determine the maximum flow within a flow network, a directed graph that depicts the movement of a particular commodity across a system of pipes or channels. The algorithm has the names of the two authors who first published it in 1956: L. R. Ford Jr. and D. R. Fulkerson.
The Ford-Fulkerson algorithm begins with a flow of 0, increases it iteratively, and stops when there is no more flow to add. This is how the algorithm operates:
- Set all edges (u, v) in E's flow f(u, v) to 0 at the beginning.
- While the residual graph G' contains an augmenting path p:
- Determine the path's bottleneck capacity, or b(p), which is the combined minimum capacity of all of its edges.
- For all edges in p, increase the flow f(u, v) along path p by b(p).
- The total amount of flows f(u, v) exiting the source vertex should be returned as the maximum flow.
When there are no more augmenting paths in the residual graph, the process is finished. Depending on how the augmenting path is found will determine how difficult the algorithm is.
Implementation with C++
Here is the C++ implementation for the Ford-Fulkerson Algorithm:
Let's take another flow network and find the maximum possible flow using its implementation in Java.
Implementation with Java
The graph we used over here is:
Below is the Java code for the Ford-Fulkerson algorithm:
The time taken by Ford Fulkerson Algorithm is O (max_flow * E).
Does Ford-Fulkerson Algorithm use BFS or DFS?
The Ford-Fulkerson algorithm can identify the augmenting path using either BFS (breadth-first search) or DFS (depth-first search). The properties of the graph and the technique used to determine the path influence the method selection.
If the graph is thin or there are fewer augmenting pathways, using DFS to locate them can produce a faster approach. BFS might be quicker, though, if the graph is thick or if there are many augmenting pathways.
In C++, the augmenting path can be found using either DFS or BFS. Here is an illustration of the Ford-Fulkerson algorithm implemented in C++ using DFS:
In this implementation, the 'residual vector represents the residual graph, and the 'parent' vector is used to store the parent node of each node in the augmenting path. The 'dfs' function performs a depth-first search to find an augmenting path in the residual graph, and the `maxFlow` function implements the Ford-Fulkerson algorithm using DFS.
To use BFS instead of DFS, we can replace the 'dfs' function with a BFS implementation, as follows:
In this approach, the stack is swapped out for a queue, and the augmenting path is discovered via a breadth-first search. The Ford-Fulkerson algorithm can be used using the maxFlow function and either DFS or BFS.
The Ford Fulkerson Algorithm is an essential topic to enhance your programming skills. While solving it a high sense of imagination power is definitely required to search for all the potential augmenting paths and find out the residual capacity of the same.