Push–relabel maximum flow algorithm

The relabel-to-front algorithm finds the maximum flow in a flow network in $O(V^{3})$ time. It is in the class of push-relabel maximum flow algorithms which run in $O(V^{2}E)$ . For dense graphs it is much more efficient than the Edmonds-Karp algorithm, which runs in $O(VE^{2})\subseteq O(V^{5})$ time.

Algorithm

Given a flow network $G(V,E)$ with capacity from node u to node v given as $C[u][v]$ , and the nodes source and sink, we want to find the maximum amount of flow you can send from source to sink through the network. Two types of operations are performed on nodes, push and relabel. Throughout we maintain:

$F[u][v]$ . Flow from u to v. Available capacity is $C[u][v]-F[u][v]$ .
$height[u]$ . We only push from u to v if $height[u]>height[v]$
$excess[u]$ . Sum of flow to and from u.

We observe that the longest possible path from source to sink is $|V|$ nodes long. Therefore it must possible to assign height to the nodes such that for any legal flow, $height[source]=|V|$ and $height[sink]=0$ , and if there is a positive flow from u to v, $height[u]>height[v]$ .As we adjust the height of the nodes, the flow goes through the network as water through a landscape. Differing from algorithms such as Ford-Fulkerson, the flow through the network is not necessarily a legal flow before the algorithm terminates.

In short words, the heights of nodes (except source and sink) is adjusted, and flow is sent between nodes, until all possible flow has reached sink. Then we continue increasing the height of internal nodes until all the flow that went into the network, but did not reach sink, has flowed back into source. A node can reach the height $2|V|-1$ before this is complete, as the longest path back to source excluding sink is $|V|-1$ long, and $height[source]=|V|$ . The height of sink is kept at 0.

Push

A push from u to v means sending a part of the excess flow into u on to v. Three conditions must be met for a push to take place:

$excess[u]>0$ . More flow into the node than out of it so far.
$C[u][v]-F[u][v]>0$ . Available capacity from u to v.
$height[u]>height[v]$ . Can only send to lower node.

We send an amount of flow equal to $\min(excess[u],C[u][v]-F[u][v])$ .

Relabel

Doing a relabel on a node u is increasing its height until it can it is higher than at least one of the nodes it has available capacity to. Conditions for a relabel:

$excess[u]>0$ . There must be a point in relabelling.
$height[v]\geq height[u]$ for all v such that $C[u][v]-F[u][v]>0$ . There are higher nodes we could send flow to.

When relabelling u, we set $height[u]$ to be the lowest value such that $height[u]>height[v]$ for some v where $C[u][v]-F[u][v]>0$ .

Push-relabel algorithm

Push-relabel algorithms in general have the following layout:

As long as there is legal push or relabel operation
1. Perform a legal push, or
2. a legal relabel.

The running time for these algorithms are in general $O(V^{2}E)$ (argument omitted).

Discharge

In relabel-to-front, a discharge on a node u is the following:

As long as $excess[u]>0$ $excess[u]>0$ :
1. If not all neighbours have been tried since last relabel:
  1. Try to push flow to an untried neighbour.
2. Else:
  1. Relabel u

This requires that for each node, it is known which nodes have been tried since last relabel.

Relabel-to-front algorithm

In the relabel-to-front algorithm, the order of the push and relabel operations is given:

Send as much flow from source as possible.
Build a list of all nodes except source and sink.
As long as we have not traversed the entire list:
1. Discharge the current node.
2. If the height of the current node changed:
  1. Move the current node to the front of the list
  2. Restart the traversal from the start of the list.

The running time for relabel-to-front is $O(V^{3})$ (proof omitted).

Python code

def relabel_to_front(C, source, sink):
    n = len(C) # C is the capacity matrix
    F = [[0] * n for _ in xrange(n)]
    # residual capacity from u to v is C[u][v] - F[u][v]
   
    height = [0] * n # height of node
    excess = [0] * n # flow into node minus flow from node
    seen   = [0] * n   # neighbours seen since last relabel
    # node "queue"
    list   = [i for i in xrange(n) if i != source and i != sink]
   
    def push(u, v):
        send = min(excess[u], C[u][v] - F[u][v])
        F[u][v] += send
        F[v][u] -= send
        excess[u] -= send
        excess[v] += send
       
    def relabel(u): 
        # find smallest new height making a push possible,
        # if such a push is possible at all
        min_height = height[u]
        for v in xrange(u):
            if C[u][v] - F[u][v] > 0:
                min_height = min(min_height, height[v])
                height[u] = min_height + 1
               
    def discharge(u):
        while excess[u] > 0:
            if seen[u] < n: # check next neighbour
                v = seen[u]
                if C[u][v] - F[u][v] > 0 and height[u] > height[v]:
                    push(u, v)
                else:
                    seen[u] += 1
            else: # we have checked all neighbours. must relabel
                relabel(u) 
                seen[u] = 0
               
    height[source] = n   # longest path from source to sink is less than n long
    excess[source] = Inf # send as much flow as possible to neighbours of source
    for v in xrange(n): 
        push(source, v) 
   
    p = 0
    while p < len(list):
        u = list[p]
        old_height = height[u]
        discharge(u)
        if height[u] > old_height:
            list.insert(0, list.pop(p)) # move to front of list
            p = 0 # start from front of list
        p += 1
           
    return sum([F[source][i] for i in xrange(n)])

References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 26.4: Push-relabel algorithms, and section 26.5: The relabel-to-front-algorithm.