Push-relabel maximum flow algorithm

The push-relabel algorithm is one of the most efficient algorithms to compute a maximum flow. The general algorithm has $O(V^2\; E)$ time complexity, while the implementation with FIFO vertex selection rule has $O(V^3)$ running time, the highest active vertex selection rule provides $O(V^2sqrt\{E\})$ complexity, and the implementation with Sleator's and Tarjan's dynamic tree data structure runs in $O(V\; E\; log(V^2/E))$ time. In most cases it is more efficient than the Edmonds-Karp algorithm, which runs in $O(VE^2)$ time.

Algorithm

Given a flow network $G(V,E)$ with capacity from node "u" to node "v" given as $c(u,v)$, and source "s" and sink "t", we want to find the maximum amount of flow you can send from "s" to "t" 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)$. For all "u", $height(u)$ is a non-negative integer.
* $excess(u)$. Sum of flow to and from "u".

After each step of the algorithm, the flow is a preflow, satisfying:

* $f(u,v)\; leq\; c(u,v)$. The flow between $u$ and $v$, does not exceed the capacity.
* $f(u,v)\; =\; -\; f(v,u)$. We maintain the net flow.
* $sum\_v\; f(u,v)\; =\; excess(u)\; geq\; 0$ for all nodes $u\; eq\; s$. Only the source may produce flow.

Notice that the last condition for a preflow is relaxed from the corresponding condition for a legal flow in a regular flow network.

We observe that the longest possible path from "s" to "t" is $|V|$ nodes long. Therefore it must be possible to assign "height" to the nodes such that for any legal flow, $height(s)\; =\; |V|$ and $height(t)\; =\; 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 throughout the execution of the algorithm.

In short words, the heights of nodes (except "s" and "t") is adjusted, and flow is sent between nodes, until all possible flow has reached "t". Then we continue increasing the height of internal nodes until all the flow that went into the network, but did not reach "t", has flowed back into "s". A node can reach the height $2|V|-1$ before this is complete, as the longest possible path back to "s" excluding "t" is $|V|-1$ long, and $height(s)\; =\; |V|$. The height of "t" 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)+1$. 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 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(u)\; leq\; height(v)$ for all "v" such that $c(u,v)-f(u,v)\; >\; 0$. The only nodes we have available capacity to are higher.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
## Perform a legal push, or
## 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$:
## If not all neighbours have been tried since last "relabel":
### Try to "push" flow to an untried neighbour.
## Else:
### "Relabel" "u"

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

Relabel-to-front algorithm, ie. using FIFO heuristic

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

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

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

ample implementation

Python implementation:

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(n): 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)] )

Note that the above implementation is not very efficient. It is slower than Edmonds-Karp algorithm even for very dense graphs. To speed it up, you can do at least two things:

# Make neighbour lists for each node, and let the index seen [u] be an iterator over this, instead of the range $0..n-1$.
# Use a gap heuristic. If there is a $k$ such that for no node, $height(u)=k$, you can set $height(u)=max(height(u),\; height(s)\; +\; 1)$ for all nodes except $s$ for which $height(u)>k$. This is because any such $k$ represents a minimal cut in the graph, and no more flow will go from the nodes $S\; =\; \{u|height(u)>k\}$ to the nodes

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 0-262-03293-7. Section 26.4: Push-relabel algorithms, and section 26.5: The relabel-to-front-algorithm.

* Andrew V. Goldberg, Robert E. Tarjan. [http://doi.acm.org/10.1145/12130.12144 A new approach to the maximum flow problem] . Annual ACM Symposium on Theory of Computing, Proceedings of the eighteenth annual ACM symposium on Theory of computing, 136&ndash;146. ISBN:0-89791-193-8 1986