Push-Relabel Max Flow, in depth: preflows, height labels, a traced worked example, gap and global relabel heuristics

Preflows: relaxing conservation

A flow must satisfy two rules: capacity (no edge carries more than it can) and conservation (every vertex other than s and t sends out exactly what it receives). A preflow keeps the capacity rule but relaxes conservation to an inequality: every vertex may receive at least as much as it sends. The surplus is the vertex's excess, e(u) = inflow(u) - outflow(u) >= 0. A vertex other than s or t with positive excess is active.

The algorithm starts by saturating every edge out of the source, which is the most flow that could ever leave it. That creates excess on the source's neighbours. From then on the job is to move excess toward the sink, and whatever cannot reach the sink back to the source, until no vertex is active. At that moment the preflow is a flow, and it is maximum.

Like every max-flow method, push-relabel works in the residual graph: an edge u to v with capacity c and flow f leaves residual capacity c - f forwards and f backwards. Pushing along a backward residual edge cancels flow sent earlier. If residual graphs are new to you, read the Ford-Fulkerson walkthrough first; the rest of this article assumes it.

Heights and the valid labelling

Push-relabel gives each vertex an integer height h(u), a lower bound on its residual distance to t, and only lets excess flow downhill, one level at a time. The heights form a valid labelling when three conditions hold:

• h(s) = n, the number of vertices, and h(t) = 0, always.
• For every residual edge u to v, h(u) ≤ h(v) + 1. An edge may drop at most one level.
• Heights never decrease.

The second condition carries the proof. Suppose some residual path from s to t existed. It would have at most n - 1 edges, each dropping at most one level, so it could descend at most n - 1 levels. But it starts at height n and ends at height 0, a drop of n. Contradiction: while the labelling is valid, no augmenting path exists. That is the opposite of path-based methods. They keep a valid flow and work toward having no augmenting path; push-relabel keeps no augmenting path and works toward having a valid flow. When the last active vertex goes quiet, both properties hold, and by the max-flow min-cut theorem the flow is maximum.

Push, relabel and discharge

There are only two operations, and each touches one active vertex u.

Push(u, v) applies when u is active, u to v has residual capacity, and the edge is admissible: h(u) = h(v) + 1. It moves d = min(e(u), residual(u, v)) units. A push that fills the edge is saturating; one that empties u is non-saturating.

Relabel(u) applies when u is active but has no admissible edge. It sets h(u) to 1 + min h(v) over residual edges out of u. That is the largest height that keeps the labelling valid, and it guarantees at least one admissible edge afterwards.

Implementations discharge a vertex until its excess is zero, walking its edges with a current-arc pointer that only resets on relabel. A complete FIFO version with the gap heuristic:

from collections import deque

class PushRelabel:
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]       # edge = [to, residual_cap, reverse_index]

    def add_edge(self, u, v, cap):
        self.g[u].append([v, cap, len(self.g[v])])
        self.g[v].append([u, 0, len(self.g[u]) - 1])

    def max_flow(self, s, t):
        n, g = self.n, self.g
        h, ex, cur = [0] * n, [0] * n, [0] * n
        cnt = [0] * (2 * n)                   # vertices at each height, for the gap test
        h[s], cnt[0], cnt[n] = n, n - 1, 1
        q = deque()
        for e in g[s]:                        # saturate every edge out of s
            v, cap, r = e
            if cap > 0:
                e[1] -= cap; g[v][r][1] += cap
                ex[v] += cap; ex[s] -= cap
                if v != t and ex[v] == cap:
                    q.append(v)
        while q:
            u = q.popleft()
            while ex[u] > 0:                  # discharge u completely
                if cur[u] == len(g[u]):       # no admissible edge left: relabel
                    old = h[u]
                    h[u] = min([h[v] + 1 for v, cap, _ in g[u] if cap > 0] + [2 * n])
                    cnt[old] -= 1; cnt[h[u]] += 1; cur[u] = 0
                    if cnt[old] == 0 and old < n:          # gap heuristic
                        for w in range(n):
                            if old < h[w] < n:
                                cnt[h[w]] -= 1; h[w] = n + 1; cnt[h[w]] += 1
                    continue
                e = g[u][cur[u]]
                v, cap, r = e
                if cap > 0 and h[u] == h[v] + 1:           # admissible: push
                    d = min(ex[u], cap)
                    e[1] -= d; g[v][r][1] += d
                    ex[u] -= d; ex[v] += d
                    if v not in (s, t) and ex[v] == d:     # v just became active
                        q.append(v)
                else:
                    cur[u] += 1
        return ex[t]

Test any max-flow code against a plain BFS solver on small random graphs; this one agrees with Edmonds-Karp on 300 of them.

Worked example: a traced run

Run the code above on this graph, with edges added in the order s-a, s-c, a-b, a-c, a-d, c-d, d-b, b-t, d-t. Initialisation sets h(s) = 6 and saturates both source edges, so a and c each hold 10 units of excess and enter the queue. The trace below is the program's actual output; the initial saturation is not counted as a push.

Final tally: 12 pushes, 8 relabels, value 4 + 10 + 5 = 19 at the sink. Note the slosh: d pushed 3 units to a and a pushed 5 back. Local decisions waste work, which the global relabel heuristic fixes. And c climbed above n once its only residual edge led to s: it is cut off from t and only drains excess home.

The minimum cut falls out for free: the vertices still reachable from s in the residual graph are {s, c}, and the edges leaving that set, s to a (10) and c to d (9), total 19.

Complexity and the selection rule

The analysis bounds each operation type separately.

Generic push-relabel is therefore O(V squared E), FIFO is O(V cubed) and highest-label is O(V squared root E). On paper Dinic's O(V squared E) looks similar; in practice the gap is set by heuristics, not by the worst case.

The heuristics that make it fast

Textbook push-relabel is often slower than a decent Dinic implementation. The two heuristics below, studied by Cherkassky and Goldberg in 1997, are what make it a fast algorithm in practice, often by more than an order of magnitude.

Global relabelling. Heights drift far below the true distances, so excess wanders. Periodically run a backward BFS from t in the residual graph and set every height to its exact distance to t; vertices that cannot reach t get distances to s plus n, or are dropped from the first phase. A common schedule is one global relabel after work proportional to m, for example after every n relabels. Too frequent and the BFS dominates.

Gap heuristic. Keep a count of vertices at each height. If some height k below n becomes empty, every vertex above k and below n has lost every route to t, because a residual path would need a vertex at level k. Lift them all to n + 1 at once. Production code keeps a bucket list per height so the lift costs only the vertices moved.

Two-phase operation. Many solvers stop the first phase when no vertex below height n is active. At that point the minimum cut is fixed and the maximum flow value is known. If you need the flow on each edge, a second phase returns the stranded excess to s, which is cheap. Applications that only need the cut, such as image segmentation or project selection, skip it.

Choosing a max-flow algorithm

Benchmark on your own graphs; this table is only a starting point.

You rarely need to write it yourself. The Boost Graph Library ships push_relabel_max_flow, LEMON has a Preflow class, and the Google OR-Tools max-flow solver is a push-relabel implementation. Writing it is still worth doing once, because modelling decisions such as vertex capacities, lower bounds and circulations all reduce to a graph you then hand to one of these solvers, and min-cost flow solvers such as cost scaling reuse the same push and relabel ideas with reduced costs in place of heights.

Failure modes

• Forgetting the reverse edge index. Storing reverse edges by searching the adjacency list turns every push into a linear scan. Store the index at insertion, as the code above does.
• Resetting the current-arc pointer at the wrong time. It may only reset on relabel. Resetting it on every discharge loses the bound and can make runs quadratic in edges.
• Enqueueing a vertex twice. Enqueue only when excess goes from zero to positive, and never enqueue s or t.
• Integer overflow. Source saturation can pile every source capacity into one vertex; use 64-bit excess.
• Floating-point capacities. Tiny residuals keep vertices active forever. Scale to integers.
• Skipping global relabels. Correct but slow; on large graphs the difference is often 10x or more. Count relabels per vertex in a profile; long climbs mean the heuristic is missing.

What to do next

1. Type in the implementation above and reproduce the 12-push, 8-relabel trace on the example graph.
2. Add a randomized test against a BFS augmenting-path solver, including parallel and zero-capacity edges.
3. Add global relabelling every n relabels and measure the change in pushes on a 10,000-vertex random graph.
4. Switch FIFO selection to highest-label with height buckets and compare again.
5. Stop after phase one, extract the minimum cut, and check that its capacity equals the flow value.
6. Model one real problem, such as assignment as bipartite matching, and solve it with a library push-relabel implementation.