Ford Fulkerson from Cormen et al

Question

I am studying the Ford-Fulkerson algorithm from Cormen's "Introduction to algorithms 2nd Edition". It is described in pseudo code for a directed graph G=(V, E) as follows where f is a flow defined on VxV

FORD-FULKERSON(G, s, t)
    for each edge (u,v) in E(G)
        do f[u, v] = 0
           f[v, u] = 0
    while there is a path p from s to t in the residual network Gf
        do m = min{c(u, v)-f[u, v]: (u, v) is on p}
            for each edge (u, v) on p
                do f[u, v] = f[u, v] + m
                   f[v, u] = - f[u, v]

The residual graph Gf has the same vertices as G and have as edges those ordered pairs of vertices (u, v) for which c(u, v) - f(u, v) > 0. (Edit: c is a capacity function given when starting and extended to be zero on edges not part of the graph)

I am unsure about what to do in the case when there exists edges in "both directions", for example what happens in the algorithm when an edge and its reverse is in the graph. I am assuming that the c(u, v) in the minimum is for the original capacities in the graph. Do I somehow need to handle four edges in the residual graph for a case when both (a, b) and (b, a) are edges ? At the moment in my setup I can't directly handle parallel edges.

I found the following question on SO: Maximum flow - Ford-Fulkerson: Undirected graph But I am not clear on what the outcome is.

Tutelary

Answer 1

Nowhere in the pseudo-code is there any assumption about whether the graph is cyclic or has "reverse edges". There are just edges.

If there are edges in "both directions", then c(u,v) and c(v,u) will be distinct. c(u,v) is just the capacity of the edge from u to v, while c(v,u) is the capacity of the edge from v to u. They have no more relationship to each other than they do to any other edges.

Put another way, both c(u,v) and f[u,v] are actually functions on edges, not vertices. (And I think the algorithm would be more clear if it were written that way.) So think of them as c(E) and f[E] where E is an edge. The "residual network" is also a collection of edges, not vertices. The residual network is just all of the edges such that c(E) - f[E] is positive.

All the algorithm does is to find any path from source to target that still has some spare capacity, and then increase the flow to consume that spare capacity. f[E] is the flow across the edge. So, find any path from s to t where all of the f[E] are less than c(E), take the smallest difference along that path, and increase the flow along that path by that difference. Iterate until there are no paths left with spare capacity.

If E and E' happen to be two edges that are the reverse of each other, the algorithm does not care; it treats them as independent edges.

Understanding what the algorithm does is the easy part. Proving that it converges, proving that it gets the right answer, and analyzing its running time are the hard parts.

[update]

Ah, I see; f[u,v] really is the flow from u to v, not the flow along an edge (since there may be two edges connecting u and v in opposite directions).

I think you can just maintain f[u,v] based on vertices, but the cost graph and residual graph still need to be based on edges. So basically do exactly what the algorithm says: For each edge E = (u,v) on the path, find the minimum of c(u,v)-f[u,v] and update the f[] values accordingly. Then compute a new residual graph based on the edges of the original graph; that is, for each edge E = (u,v), if c(u,v) is greater than f[u,v] then E is a member of the residual graph.

Caseinogen

Thanks for your reply. The troublesome spot for me if there are edges (u, v) and (v, u) is in the step after updating f[u, v], f[v, u] is set equal to -f[u, v] independent of what the flow on (v, u) is. My brain have a hard time accepting this will work. I am almost done with my implementation so will try it out soon. – Tutelary

Damn, if I hadn't stopped to think about the pseudo-code, I would have saved a couple of hours. After implementing it works correctly on a large test instance. This is magic to me for now, I will have to study the proof in the weekend. Thanks for the confirmation that I had the formulation correct so I could feel safe about carrying on :) – Tutelary

@Lin: Obviously there is no point having flow from u to v and from v to u at the same time. Now suppose that there is positive flow from u to v, and that there is a path P from source to sink that passes through v to u, with positive residual capacity. Then it is possible to increase flow on P by reducing flow on the u->v edge. It might help to draw a picture. (Such an increase on one path does mean that the source-sink flows change on multiple paths.) – Prajna