The maximum flow is an optimization problem. You can read the background here.
I will discuss the code for a simple Ford-Fulkerson approach here.
There are three things that need to be true throughout the execution of the Ford-Fulkerson algorithm.
c(u,v) >= f(u,v)This means that the flow between nodes
vis never more than the capacity of the edge between
v. This is the capacity constraint.
f(u,v) = -f(v,u)This means that the net flow from
vis opposite to the direction of net flow from v to u. This is the skew symmetry constraint.
f(u,v)for all pairs of
0. This is the flow conservation constraint.
Now we need to find a path from source (
s) to sink (
t), so that it is possible to push to a positive flow on to that path. This means that for every pair of successive nodes,
v on the path,
c(u,v) - f(u,v) > 0.
This path is found using either Breadth First Search or Depth First Search. I am listing the code below for augmenting path with Depth First Search, since in BFS, there is a need for path-reconstruction.
Let’s start with the basic initialization of the data-structures.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
MAXN is the estimate of the number of nodes we are going to have. s is the source and t is the sink node.
adj[i] is the adjacency list for node
adjsz[i] is the size of the adjacency list of node i. N is the total number of nodes.
c[u][v] is the capacity of the edge between u and v, and similarly
f[u][v] is the flow in the edge between u and v.
g[u][v] is true if there is an edge between either
u. The vis array is a visited array, and
vis[i] is marked true if it has been visited for finding the augmenting path.
Below is the code for adding a new edge between
1 2 3 4 5 6
Note that, if there is an edge from
v with a positive capacity, we make sure that both
v are in each others’ adjacency list. This is done so that, if there is some flow between two nodes that needs to be cancelled to increase the total flow of the network, we can push a flow in the opposite direction on that edge.
Below is the code for Augmenting Path algorithm using DFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
It is pretty easy to understand, it looks for neighbours of a node which are not visited and through which a positive flow can be pushed. It then determines exactly how much flow can be pushed through the current edge (between
u and v). This value exists in the variable cur_cap. Then it recursively calls itself to repeat the procedure with
v, and the new effective bottleneck capacity becoming
cur_cap. When either the sink is found, or there is no eligible neighbor the recursion ends, and returns the current bottleneck capacity of the path,
path_cap, if sink is found. If not, and there is no eligible neighbor, it returns
The returned values trickle down, and finally the ultimate bottleneck capacity is returned.
Ford-Fulkerson does nothing except trying to push more and more flow through the source by repetitively calling the
augment_dfs function. When the returned value (bottleneck capacity of the augmented path) is
0, it implies no more flow can be pushed.
1 2 3 4 5 6 7 8 9 10 11 12 13
In all we need to set N (the number of nodes),
t (sink), and call the add_edge function for each edge we need to add. Also, set the
MAXN macro appropriately.
Here is the complete code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80