Question on pseudocode for Ford-Fulkerson in Kleinberg-Tardos Text
-
04-11-2019 - |
Question
I am looking at the following pseudocode from the Kleinberg-Tardos text "Algorithm Design".
Max-Flow
Initially f(e)=0 for all e in G
While there is an s-t path in the residual graph G_f
Let P be a simple s-t path in G_f
f' = augment(f,P)
Update f to f'
Update the residual graph G_f to be G_f'
Endwhile
Return f
This seems to make sense to me. However, prior to displaying this pseudocode, the textbook gives pseudocode for the augment subroutine:
augment(f,P)
Let b = bottleneck(P,f)
For each edge (u,v) in P
If e = (u,v) is a forward edge then
increase f(e) in G by b
Else ((u,v) is a backward edge, and let e = (v,u))
decrease f(e) in G by b
Endif
Endfor
Return(f)
Unfortunately, the textbook does not give any implemenation details on the bottleneck() subroutine.
But what I cannot understand is why we would need to pass the flow function $f$, to the bottleneck subroutine?
It seems that the bottleneck routine is looking at a simple s-t path in the residual graph $G_f$. Hence bottleneck is only concerned with the residual capacity along each edge. When we create the residual graph I was under the impression that each edge is labeled with the corresponding residual capacity. Hence, a call such as bottleneck($P$) would seem to suffice which simply looked for the minimum capacity along the edges in $P$.
Can someone shed any light on why we pass $f$ to this bottleneck subroutine?
No correct solution