Modified EDMONDS-KARP Algorithm to Solve Maximum Flow Problems ()
Received 18 January 2016; accepted 26 February 2016; published 29 February 2016
1. Introduction
The maximum amount of commodities that can be shipped through any network from source to sink is called maximum flow and this problem is called MFP, which is a classical network flow problem. Network flows problem has got a vast application in the field of Mathematics, Computer Science, Management and Operations Research.
At first the effective solution procedure to obtain the maximum flow in a flow network was introduced by Lester R. Ford and Delbert R. Fulkerson [1] [2] in 1955 which is the well known Ford-Fulkerson algorithm. The improvement of the Ford-Fulkerson method is Edmonds-Karp algorithm [3] which observed that augmenting along shortest paths leads to a polynomial-time algorithm, and performs better than the previous one. Again extensive discussion, further improvement and effectiveness of the solution procedure of MFP are studied by a good no. of researchers [1] [2] [4] -[16] . Those researchers also proposed various methods to solve the MFP basing on the merits and demerits of the previous methods. Very recently, Ahmed, F. et al. [17] and Khan, Md. A. et al. [18] also proposed new approaches for finding maximum flow problem.
In this paper, a modified Edmonds-Karp algorithm is proposed to compute maximum amount of flow from source to sink for a MFP. Numerical illustration of the proposed algorithm is also done by solving a good number of examples to test the effectiveness and usefulness of the proposed algorithm.
2. Basic Definitions
Some of the basic ideas related to maximum flow problems are given below with an aim to accustom the readers with the article.
2.1. Capacity Constraint
The flow f(u, v) through an edge cannot be negative and cannot exceed the capacity of the edge c(u, v), 0 ≤ f(u, v) ≤ c(u, v). If an edge (u, v) doesn’t exist in the network, then c(u, v) = 0.
2.2. Flow Conservation
Aside from the source vertex s and sink vertex t, each vertex u belongs to V must satisfy the property that the sum of f(v, u) for all edges (v, u) in E (the flow into u) must equal the sum of f(u, w) for all edges (u, w) belongs to E (the flow out of u).
This property ensures that flow is neither produced nor consumed in the network, except at s and t.
2.3. Skew Symmetry
For consistency, the quantity f(v, u) represents the net flow from vertex u to v. This means that it must be the case that f(u, v) = −f(v, u); this holds even if both edges (u, v) and (v, u) exist in a directed graph.
2.4. Residual Network
Intuitively, given a flow network and a flow, the residual network consists of edges that can admit more flow. More formally, let a flow network with source s and sink t. Let f be a flow in G, and consider a pair of vertices The amount of additional flow which can be pushed from u to v before exceeding the capacity c(u, v) is the residual capacity of (u, v), given by cf(u, v) = c(u, v) − f(u, v).
3. Proposed Algorithm
It is to be mentioned that the proposed algorithm is a modified version of Ford-Fulkerson algorithm. The basic steps of this algorithm are explained below.
4. Mathematical Illustration
Two numerical examples have been solved for finding the maximum value of a MFP by using proposed algorithm which is given below.
4.1. Example-1
Consider the water supply system in a Campus. The pipeline between the supply points of any two areas has a stated capacity in gallons per hour, given as a maximum flow at which water can flow through the pipe between those two areas. To supply water from the source area, A (say) to the sink area, I (say) and water passes through 7 other areas before reaching from source to sink. Suppose these 7 areas are B, C, D, E, F, G, H and pipeline between any two areas has a defined capacity. Table 1 shows the defined capacities of each pipeline between any two areas which can flow between corresponding two areas.
Table 1. Defined capacities of each pipeline between two areas.
Calculate the maximum amount of water which can flow from A to I.
Solution of Example-1
Now the problem discussed in the Example 1 is converted into directed graph by representing areas as vertices of the graph and pipelines between any two areas as edges of the graph. The capacity of the pipeline in gallons per hour is represented as capacity of an edge in units between vertices.
Now, following correspondence between areas and vertices is used to create the graph.
Table 2. Correspondence between areas and vertices.
So, the initial graph corresponding to Table 1 and Table 2 is as follows.
Figure 1. The initial flow network corresponding to the problem.
Now we use the modified Edmonds-Karp Method to compute a maximum flow in G.
According to the Figure 1, the maximum capacity is 48. So, the value of the variable C in the above algorithm will be 48.
So, , this will be the value of the variable I in the 1st iteration of the algorithm.
Iteration-1: I = 27. So, the augmenting path with capacity at least 27 will be searched by the Breadth First Search (BFS) procedure. But, there is no augmenting path with capacity at least 27. So, no flow will be added to the initial flow of the graph which is 0.
Iteration-2: I = I/3 = 27/3 = 9. So, now the augmenting path with capacity at least 9 will be searched by the same BFS procedure in the residual graph which is given in Figure 2 corresponding to the initial graph. The augmenting path will be searched till path with capacity at least 9 is found in the graph. Now, in the consecutive figures, Figure 2 shows the residual graph and Figure 3 shows the corresponding flow in the graph.
Figure 2. Residual Graph before any augmentation.
Figure 3. Flow graph after 1st augmentation.
Whenever the augmenting path is to be found in the graph, if there are more than 1 path satisfying the capacity criteria, then the path is determined by BFS procedure on the basis of sequential ordering of the vertices and corresponding edges which has been given as input.
1st Augmentation: So, the augmenting path found in 2nd iteration is s - v1 - v3 - v6 - t with capacity 20. So, the initial flow is augmented by 20 units and the flow in the graph is shown in Figure 3 giving maximum flow value f = 20. The residual graph after 1st augmentation is shown in Figure 4.
Figure 4. Residual Graph after 1st augmentation.
Figure 5. Flow Graph after 2nd augmentation.
2nd Augmentation: Now, again there is a path with capacity at least 18 and the path found in the same 2nd iteration is s - v4 - v3 - v7 - t with capacity 18. So, the maximum flow is augmented by 18 units and the flow in the graph is shown in Figure 5 giving maximum flow value f = 20 + 18 = 38. Now, there is no path with capacity at least 18. Same procedure will be followed until variable I becomes < 1. Residual graph after 2nd augmentation is shown in Figure 6.
Figure 6. Residual Graph after 2nd augmentation.
Figure 7. Flow Graph after 3rd augmentation.
3rd Augmentation: Now, again there is a path with capacity at least 12 and the path found in the same 2nd iteration is s - v2 - v5 - v7 - t with capacity 12. So, the maximum flow is augmented by 12 units and the flow in the graph is shown in Figure 7 giving maximum flow value f = 38 + 12 = 50. Now, there is no path with capacity at least 12. Same procedure will be followed until variable I becomes < 1. Residual graph after 3rd augmentation is shown in Figure 8.
Figure 8. Residual Graph after 3rd augmentation.
Figure 9. Flow Graph after 4th augmentation.
4th Augmentation: Now, again there is a path with capacity at least 15 and the path found in the same 2nd iteration is s - v4 - v5 - v7 - v6 - t with capacity 15. So, the maximum flow is augmented by 15 units and the flow in the graph is shown in Figure 9 giving maximum flow value f = 50 + 15 = 65. Now, there is no path with capacity at least 15. Same procedure will be followed until variable I becomes < 1.
3rd Iteration: I = I/3 = 9/3 = 3. So, now the augmenting path with capacity at least 3 will be searched in the residual graph which is given in Figure 10 corresponding to the initial graph.
5th Augmentation: So, the augmenting path found in 3rd iteration is s - v1 - v4 - v3 - v5 - v7 - v6 - t with capacity 5. So, the initial flow is augmented by 5 units and the flow in the graph is shown in Figure 11 gives maximum flow value f = 65 + 5 = 70. The residual graph after 4th augmentation is shown in Figure 10.
Figure 10. Residual Graph after 4th augmentation.
Figure 11. Flow Graph after 5th augmentation.
4th Iteration: I = I/3= 3/3 = 1. So, the augmenting path with capacity at least 1 will be searched in the residual graph which is given in Figure 12 corresponding to the initial graph.
6th Augmentation: So, the augmenting path found in 4th iteration is s - v2 - v4 - v3 - v6 - t with capacity 2. So, the initial flow is augmented by 2 units and the flow in the graph is shown in Figure 13 giving maximum flow value f = 70 + 2 = 72. The residual graph after 6th augmentation is shown in Figure 14.
Figure 12. Residual Graph after 5th augmentation.
Figure 13. Flow graph after 6th augmentation.
The residual graph after 6th augmentation is shown below:
4.2. Example-2
Suppose a pipeline system in a Campus to supply gas in different areas of a Campus. The pipeline between any two areas has a stated capacity in per unit per hour, given as a maximum flow at which gas can flow through the pipe between those two areas. Now, suppose we want to supply gas from the source area, suppose A to the sink area, say F and gas passes through 4 other areas before reaching from source to sink. Suppose these 4 areas are B, C, D, E and pipeline between any two areas has defined capacity.
The following table shows the defined capacities of each pipeline between any two areas which can flow between corresponding two areas.
Table 3. Defined capacities of each pipeline between two areas.
Calculate the maximum amount of gas which can flow from A to F.
Solution of Example-2
Now the problem discussed in the Example 2 is converted into directed graph by representing areas as vertices of the graph and pipelines between any two areas as edges of the graph. The capacity of the pipeline in unit per hour is represented as capacity of an edge in units between vertices.
Now, following correspondence between areas and vertices is used to create the graph.
Table 4. Correspondence between areas and vertices.
So, the initial graph corresponding to Table 3 and Table 4 is shown in Figure 15.
Figure 15. The initial flow network corresponding to the problem.
Solving the above example using our proposed algorithm, the maximum flow value f = 19.
5. Outcome
Table 5 shows a comparison of no. of iteration and no. of augmentation required to obtain the maximum flow by using various existing methods and our proposed Modified Edmonds-Karp algorithm by means of the abovetwo sample examples and it is seen that our proposed algorithm requires less number of iterations and augmentation paths to reach the maximum flow.
6. Conclusion
In this paper, we have modified Edmonds-Karp algorithm to compute maximum amount of flow from source to
Table 5. Comparison of the resul obtained by different methods.
sink in a flow network. We have also solved several number of maximum flow problems by using our proposed algorithm, Ford-Fulkerson algorithm, Md. Al-Amin Khan et al.’s Algorithm, and Faruque Ahmed et al.’s algorithm and Edmonds-Karp algorithm to test the efficiency of the proposed algorithm. During this process, it is observed that our proposed algorithm is faster and taking less number of iterations and less number of augmentations to determine the maximum flow in maximum flow problems in comparison with the other well known algorithms.