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?