Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Ford Fulkerson from Cormen et al

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.

like image 390
Lin A Avatar asked Oct 12 '11 13:10

Lin A


People also ask

What is the order of running time for Ford-Fulkerson?

Running time of Ford-Fulkerson Each iteration of Ford-Fulkerson takes O(E) time to find an augmenting path (Gf has at least E and at most 2E edges, so the time is O(V+2E) = O(E+E) = O(E)). Each iteration also increases the flow by at least 1, assuming all capacities are integers.

Which algorithm is designed by Ford and Fulkerson?

Ford-Fulkerson algorithm is a greedy approach for calculating the maximum possible flow in a network or a graph. A term, flow network, is used to describe a network of vertices and edges with a source (S) and a sink (T). Each vertex, except S and T, can receive and send an equal amount of stuff through it.

Why is Edmonds-Karp faster than Ford-Fulkerson?

Edmonds-Karp differs from Ford-Fulkerson in that it chooses the next augmenting path using breadth-first search (bfs). So, if there are multiple augmenting paths to choose from, Edmonds-Karp will be sure to choose the shortest augmenting path from the source to the sink.

What does Ford-Fulkerson do?

The Ford-Fulkerson algorithm is an algorithm that tackles the max-flow min-cut problem. That is, given a network with vertices and edges between those vertices that have certain weights, how much "flow" can the network process at a time? Flow can mean anything, but typically it means data through a computer network.


1 Answers

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.

like image 176
Nemo Avatar answered Sep 29 '22 23:09

Nemo