Understanding the Maximum Flow algorithm
1. Given a list of connected pipes with different flow-capacities, find the amount of water that can go from a starting point to a given ending point.
2. You have a lot of cars that you want to take from city ‘s’ to city ‘t’. Each road between two cities has a limit on the number of cars that can go there. What is the maximum number of cars that you can take from ‘s’ to ‘t’?
The two above problems can be visualized in the following way:
In Problem 1, each letter represents a pipe, and each number represents the flow-capacity between two pipes. That is, maximum amount of water that can go from s to a is 11 units, a to b is 12 units and so on.
In Problem 2, each letter represents a city, and each number represents the maximum number of cars that can go from the two cities. Similar to the situation in Problem 1, the number of cars that can go from s to a is 11, from a to b is 12 etc.
What is one way to solve these two problems? It is obvious that here we deal with a Network Flow problem. There are a few known algorithms: Ford–Fulkerson algorithm, Edmond Karp algorithm and Dinic’s algorithm.
Here we discuss the Edmond Karp algorithm, which is almost identical to Ford-Fulkerson, except that the search order is defined.
With defined, it means that it uses Breadth-First-Search to find the paths in terms of hops between the source and the sink. All these paths that start in source and end in sink are called augmenting paths.
And then what? What do we do after we find the augmenting paths between source and sink?
Here comes the key part of the algorithm: We find the minimum edge-weight (number in Figure 1) that is part of our path. For example, referring to our sample graph in Figure 1, if we run BFS from s to t, initially we will end up with the first augmenting path p1 = [ s — c — d — t ].
If we now refer to Problem 1, we can say that the minimum flow capacity of each pipe in the augmenting path p1 lies in the edge d — t which is 4 units.
And then what? What do we do after we find the minimum edge-weight in the augmenting path?
Now we will do two important steps:
- Decrease all the flow-capacities of the forward edges by the minimum edge-weight.
- Increase all the flow-capacities of the backward edges by the minimum edge-weight.
Considering our augmenting path p1, we decrease the following edges [ s-c, c-d, d-t ] and increase the backward edges [ c-s, d-c, t-d ] (if its bi-directional).
The reason for decreasing forward edges is to not mark the already used edge capacities and for increasing backward edges is to allow future flow to cancel the misused capacity used from some earlier flow.
And then what? What do we do after we decrease and increase the flow-capacities of forward and backward edges?
We do this repeatedly until the minimum edge capacity is 0. That would mean that there is no more any augmenting path from s to t.
How do we calculate the maximum flow?
To calculate the maximum flow from s to t we add all the minimum edge capacities of all the augmenting paths found.
MAX_FLOW = 0
MIN_EDGE_W = 0
AUG_PATH = EMPTY LIST
SOURCE, SINKAUGMENT(SINK, MIN_EDGE) -> function that augments (finds the min_edge_w and increases/decreases edges)while(true):
MIN_EDGE_W = 0
RUN BFS FROM SOURCE TO SINK (storing the spanning tree in AUG_PATH)AUGMENT(SINK, MIN_EDGE) - calls the function*in this point we have found the MIN_EDGE_Wif( MIN_EDGE_W == 0 ): -> if it's 0 then stop the program
BREAKMAX_FLOW += MIN_EDGE_W -> add to max flow///RESULT IN MAX_FLOW
Run the program with the sample Graph in Figure 1.
My code can only find max flow in a graph where nodes are given as numbers.
The input is in the following format:
line 1: edges #number of edges
line 2: source sink #given as numbers
following edges lines: a b c # node a,b and weight c
Output will show the max_flow and the augmenting paths.
in input.txt file6
0 2 100
0 3 50
2 1 5
2 4 5
4 1 125
3 4 100in output.txt fileAugmenting paths...
Path: [ 0 -> 2 -> 1 ] flow: 5
Path: [ 0 -> 2 -> 4 -> 1 ] flow: 5
Path: [ 0 -> 3 -> 4 -> 1 ] flow: 50
Maximum flow: 60
Running time? O(V*E) BFS iterations x O(V) per BFS = O(V²*E), where V is the number of vertices and E is the number of edges
Exercise: Change my code to also support strings as nodes and find the max flow in Figure 1 graph and do a pull request to my repository.
References: CP3 book by Steven Halim, Wikipedia