Push–relabel maximum flow algorithm

In mathematical optimization, the push-relabel algorithm (alternatively, preflow-push algorithm) is an algorithm for computing maximum flows. The name "push-relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring vertices using push operations under the guidance of an admissible network maintained by relabel operations. In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink.

The push-relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a strongly polynomial O(V²E) time complexity, which is asymptotically more efficient than the O(VE²) Edmonds–Karp algorithm. Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label vertex selection rule has O(V²√E) time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic O(VE log (V²/E)) time complexity can be achieved using dynamic trees, although in practice it is less efficient.

The push-relabel algorithm has been extended to compute minimum cost flows. The idea of distance labels has led to an more efficient augmenting path algorithm, which in turn can be incorporated back into the push-relabel algorithm to create a variant with even higher empirical performance.

Concepts

Definitions and notations

Main article: Flow network

Consider a flow network G(V, E) with a pair of distinct vertices s and t designated as the source and the sink, respectively. For each edge (u, v) ∈ E, c(u, v) ≥ 0 denotes its capacity; if (u, v) ∉ E, we assume that c(u, v) = 0. A flow on G is a function f: V × V → R satisfying the following conditions:

Capacity constraints

f(u, v) ≤ c(u, v) ∀u, v ∈ V

Skew symmetry

f(u, v) = −f(v, u) ∀u, v ∈ V

Flow conservation

∑_v ∈ V f(v, u) = 0 ∀u ∈ V \ {s, t}

The push-relabel algorithm introduces the concept of preflows. A preflow is a function with a definition almost identical to that of a flow except that it relaxes the flow conservation condition. Instead of requiring strict flow balance at vertices other than s and t, it allows them to carry positive excesses. Put symbolically:

Nonnegative excesses

e(u) = ∑_v ∈ V f(v, u) ≥ 0 ∀u ∈ V \ {s}

e(s) is assumed to be infinite. A vertex u is called active if e(u) > 0.

For each (u, v) ∈ V × V, denote its residual capacity by c_f(u, v) = c(u, v) − f(u, v). The residual network of G with respect to a preflow f is defined as G_f(V, E_f) where E_f = {(u, v) | u, v ∈ V ∧ c_f(u, v) > 0}. If there is no path from any active vertex to t in G_f, the preflow is called maximum. In a maximum preflow, e(t) is equal to the value of a maximum flow; if T is the set of vertices from which t is reachable in G_f, and S = V \ T, then (S, T) is a minimum s-t cut.

The push-relabel algorithm makes use of distance labels, or heights, of the vertices denoted by h(u). For each vertex u ∈ V \ {s, t}, h(u) is a nonnegative integer satisfying

Valid labeling

h(u) ≤ h(v) + 1 ∀(u, v) ∈ E_f

The heights of s and t are fixed at |V| and 0, respectively. h(u) is a lower bound of the unweighted distance from u to t in G_f if t is reachable from u. If u has been disconnected from t, then (h(u) − |V|) is a lower bound of the unweighted distance from u to s. As a result, if a valid height function exists, there are no s-t paths in G_f because no such paths can be longer than (|V| − 1).

An edge (u, v) ∈ E_f is called admissible if h(u) = h(v) + 1. The network G̃_f(V, Ẽ_f) where Ẽ_f = {(u, v) | (u, v) ∈ E_f ∧ h(u) = h(v) + 1} is called the admissible network. The admissible network is acyclic.

Operations

Push

The push operation applies on an admissible out-edge (u, v) of an active vertex u in G_f. It moves min{e(u), c_f(u, v)} units of flow from u to v.

push(u, v):
    assert e[u] > 0 and h[u] == h[v] + 1
    Δ = min(e[u], c[u][v] - f[u][v])
    f[u][v] += Δ
    f[v][u] -= Δ
    e[u] -= Δ
    e[v] += Δ

A push operation that causes f(u, v) to reach c(u, v) is called a saturating push; otherwise, it is called an unsaturating push. After an unsaturating push, e(u) = 0.

Relabel

The relabel operation applies on an active vertex u without any admissible out-edges in G_f. It modifies h(u) to the minimum value such that an admissible out-edge is created. Note that this always increases h(u) and never creates a steep edge (an edge (u, v) such that c_f(u, v) > 0, and h(u) > h(v) + 1).

relabel(u):
    assert e[u] > 0 and h[u] <= h[v] ∀v such that f[u][v] < c[u][v]
    h[u] = min(h[v] ∀v such that f[u][v] < c[u][v]) + 1

Effects of push and relabel

After a push or relabel operation, h remains a valid height function with respect to f.

For a push operation on an admissible edge (u, v), it may add an edge (v, u) to E_f, where h(v) = h(u) − 1 ≤ h(u) + 1; it may also remove the edge (u, v) from E_f, where it effectively removes the constraint h(u) ≤ h(v) + 1.

To see that a relabel operation on vertex u preserves the validity of h(u), notice that this is trivially guaranteed by definition for the out-edges of u in G_f. For the in-edges of u in the G_f, the increased h(u) can only satisfy the constraints less tightly, not violate them.

The generic push-relabel algorithm

Description

Since h(s) = |V|, h(t) = 0, and there are no paths longer than (|V| − 1) in G_f, in order for h(s) to satisfy the valid labeling condition, s must be disconnected from t. At initialization, the algorithm fulfills this requirement by creating a preflow f that saturates all out-edges of s, after which h(u) = 0 is trivially valid for all v ∈ V \ {s, t}.

After initialization, the algorithm repeatedly executes an applicable push or relabel operation until no such operations apply, at which point the preflow has been converted into a maximum flow.

generic-push-relabel(G(V, E), s, t):
    create a preflow f that saturates all out-edges of s
    let h[u] = 0 ∀v ∈ V
    while there is an applicable push or relabel operation
        execute the operation

Correctness

Because push and relabel operations preserve the validity of preflow f and height function h, when the algorithm terminates, there are no active vertices other than s and t, and thus the preflow becomes a valid flow. Since it is also guaranteed throughout that there are no s-t paths in residual network G_f, the algorithm terminates with a maximum flow.

Time complexity

We bound the numbers of relabels, saturating pushes and nonsaturating pushes separately. Because 0 ≤ h(u) ≤ 2n − 1 for every vertex u, and each relabel increases h(u) by at least one, the total number of relabels on all vertices is O(V²). Each saturating push on an admissible edge (u, v) removes the edge from G_f. For the edge to be reinserted into G_f for another saturating push, v must be first relabeled, followed by a push on edge (v, u), then u must be relabeled. In the process, h(u) increases by at least two. Therefore, there are O(V) saturating pushes on (u, v), and the total number of saturating pushes on all edges is O(VE).

Bounding the number of nonsaturating pushes can be achieved via a potential argument. We use the potential function Φ = ∑_{u ∈ V ∧ e(u) > 0} h(u), i.e., Φ is the sum of the heights of all active vertices. It is obvious that Φ stays nonnegative throughout the execution of the algorithm. Both relabels and saturating pushes can increase Φ. Relabels increase h(u) by O(V) for every vertex u and thus contribute O(V²) increase to Φ. A saturating push on (u, v) activates v if it was inactive before the push, increasing Φ by O(V). Hence, the total contribution of all saturating pushes is O(V²E). An unsaturating push on (u, v) always deactivates u, but it can also activate v as in a saturating push. As a result, it decreases Φ by at least h(u) − h(v) = 1. Since relabels and saturating pushes increase Φ by O(V² + V²E) = O(V²E), the total number of unsaturating pushes is O(V²E).

In sum, the algorithm executes O(V²) relabels, O(VE) saturating pushes and O(V²E) nonsaturating pushes. Data structures can be designed to pick and execute an applicable operation in O(1) time. Therefore, the time complexity of the algorithm is O(V²E).

Practical implementations

While the generic push-relabel algorithm has O(V²E) time complexity, efficient implementations achieve O(V³) or lower time complexity by enforcing appropriate rules in selecting applicable push and relabel operations. The empirical performance can be further improved by heuristics.

"Current-edge" data structure and discharge operation

The "current-edge" data structure is a mechanism for visiting the in- and out-neighbors of a vertex in the flow network in a static circular order. If a singly linked list of neighbors is created for a vertex, the data structure can be as simple as a pointer into the list that steps through the list and rewinds to the head when it runs off the end.

Based on the "current-edge" data structure, the discharge operation can be defined. A discharge operation applies on an active node and repeatedly pushes flow from the node until it becomes inactive, relabeling it as necessary to create admissible edges in the process.

discharge(u):
    while e[u] > 0
        if current-edge[u] has run off the end of neighbors[u]
            relabel(u)
            rewind current-edge[u]
        else
            let (u, v) = current-edge[u]
            if (u, v) is admissible
                push(u, v)
            let current-edge[u] point to the next neighbor of u

Active vertex selection rules

Definition of the discharge operation reduces the push-relabel algorithm to repeatedly selecting an active node to discharge. Depending on the selection rule, the algorithm exhibits different time complexities. For the sake of brevity, we ignore s and t when referring to the vertices in the following discussion.

FIFO selection rule

The FIFO push-relabel algorithm organizes the active vertices into a queue. The initial active nodes can be inserted in arbitrary order. The algorithm always removes the vertex at the front of the queue for discharging. Whenever an inactive vertex is becomes active, it is appended to the back of the queue.

The algorithm has O(V³) time complexity.

Relabel-to-front selection rule

The relabel-to-front push-relabel algorithm organizes all vertices into a linked list and maintains the invariant that the list is topologically sorted with respect to the admissible network. The algorithm scans the list from front to back and performs a discharge operation on the current vertex if it is active. If the node is relabeled, it is moved to the front of the list, and the scan is restarted from the front.

The algorithm also has O(V³) time complexity.

Highest label selection rule

The highest-label push-relabel algorithm organizes all vertices into buckets indexed by their heights. The algorithm always selects an active vertex with the largest height to discharge.

The algorithm has O(V²√E) time complexity. If the lowest-label selection rule is used instead, the time complexity becomes O(V²E).

Implementation techniques

Although in the description of the generic push-relabel algorithm above, h(u) is set to zero for each vertex u other than s and t at the beginning, it is preferable to perform a backward breadth-first search from t to compute the exact heights.

The algorithm is typically separated into two phases. Phase one computes a maximum preflow by discharging only active vertices whose heights are below n. Phase two converts the maximum preflow into a maximum flow by returning excess flow that cannot reach t to s. It can be shown that phase two has O(VE) time complexity regardless of the order of push and relabel operations and is therefore dominated by phase one. Alternatively, it can be implemented using flow decomposition.

Heuristics are crucial to improving the empirical performance of the algorithm. Two commonly used heuristics are the gap heuristic and the global relabeling heuristic. The gap heuristic detects gaps in the height function. If there is a height 0 < h̃ < n for which there is no vertex u such that h(u) = h̃, then any vertex u with h̃ < h(u) < n has been disconnected from t and can be relabeled to (n + 1) immediately. The global relabeling heuristic periodically performs backward breadth-first search from t in G_f to compute the exact heights of the vertices. Both heuristics skips unhelpful relabel operations, which are a bottleneck of the algorithm and contribute to the ineffectiveness of dynamic trees.

Sample implementations

C implementation

#include <stdlib.h> #include <stdio.h> #define NODES 6 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) #define INFINITE 10000000 void push(const int * const * C, int ** F, int *excess, int u, int v) { int send = MIN(excess[u], C[u][v] - F[u][v]); F[u][v] += send; F[v][u] -= send; excess[u] -= send; excess[v] += send; } void relabel(const int * const * C, const int * const * F, int *height, int u) { int v; int min_height = INFINITE; for (v = 0; v < NODES; v++) { if (C[u][v] - F[u][v] > 0) { min_height = MIN(min_height, height[v]); height[u] = min_height + 1; } } }; void discharge(const int * const * C, int ** F, int *excess, int *height, int *seen, int u) { while (excess[u] > 0) { if (seen[u] < NODES) { int v = seen[u]; if ((C[u][v] - F[u][v] > 0) && (height[u] > height[v])){ push(C, F, excess, u, v); } else seen[u] += 1; } else { relabel(C, F, height, u); seen[u] = 0; } } } void moveToFront(int i, int *A) { int temp = A[i]; int n; for (n = i; n > 0; n--){ A[n] = A[n-1]; } A[0] = temp; } int pushRelabel(const int * const * C, int ** F, int source, int sink) { int *excess, *height, *list, *seen, i, p; excess = (int *) calloc(NODES, sizeof(int)); height = (int *) calloc(NODES, sizeof(int)); seen = (int *) calloc(NODES, sizeof(int)); list = (int *) calloc((NODES-2), sizeof(int)); for (i = 0, p = 0; i < NODES; i++){ if((i != source) && (i != sink)) { list[p] = i; p++; } } height[source] = NODES; excess[source] = INFINITE; for (i = 0; i < NODES; i++) push(C, F, excess, source, i); p = 0; while (p < NODES - 2) { int u = list[p]; int old_height = height[u]; discharge(C, F, excess, height, seen, u); if (height[u] > old_height) { moveToFront(p,list); p=0; } else p += 1; } int maxflow = 0; for (i = 0; i < NODES; i++) maxflow += F[source][i]; free(list); free(seen); free(height); free(excess); return maxflow; } void printMatrix(const int * const * M) { int i,j; for (i = 0; i < NODES; i++) { for (j = 0; j < NODES; j++) printf("%d\t",M[i][j]); printf("\n"); } } int main(void) { int **flow, **capacities, i; flow = (int **) calloc(NODES, sizeof(int*)); capacities = (int **) calloc(NODES, sizeof(int*)); for (i = 0; i < NODES; i++) { flow[i] = (int *) calloc(NODES, sizeof(int)); capacities[i] = (int *) calloc(NODES, sizeof(int)); } //Sample graph capacities[0][1] = 2; capacities[0][2] = 9; capacities[1][2] = 1; capacities[1][3] = 0; capacities[1][4] = 0; capacities[2][4] = 7; capacities[3][5] = 7; capacities[4][5] = 4; printf("Capacity:\n"); printMatrix(capacities); printf("Max Flow:\n%d\n", pushRelabel(capacities, flow, 0, 5)); printf("Flows:\n"); printMatrix(flow); return 0; }

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" nodelist = [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 = ∞ 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(nodelist): u = nodelist[p] old_height = height[u] discharge(u) if height[u] > old_height: nodelist.insert(0, nodelist.pop(p)) # move to front of list p = 0 # start from front of list else: p += 1 return sum(F[source])