COMS 482: unofficial class blog

Ford-Fulkerson Algorithm:

ford_fulkerson(G, s, t, capacity):
    f[e] = 0 for all e
    while there exists an s -> t path in the residual graph
        choose a path p
        f = augment(f, p)
        update residual graph
    Endwhile

augment(f, path):
    c = lowest capacity on path
    for each edge e on path
        if e if a forward edge
            f[e] += c
        if e is a backwards edge
            f[e] -= c
    Endfor

Termination:

Every time we find a path, the flow on s increases by at least 1 each time (assuming integer capacities). There is also a maximum possible flow from s, equal to C = sum( c_e ) of e out of s = f^out(s). We can find a path at most C times, so the total time = O( C * work to find and update path) = O(m*C).

Application: Bipartite Matching:

A Bipartite Matching is defined as V= X + Y where X & Y = {} and for all edges (a, b) in V, a is in X and b is in Y. Imagine wanting to assign people and tasks. You can create a network flow diagram for this:

Here, we draw an edge between a person and a task iff that person can perform said task. Then, running the flow algorithm will assign 1 person to every task, or find the best possible match. This runs in O(m*n) time, where m is the number of edges and n is the number of vertices.