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.^[1]

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.^[2] 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.^[3]^[4] Subcubic O(VE² log (V²/E)) time complexity can be achieved using dynamic trees, although in practice it is less efficient.^[2]

The push-relabel algorithm has been extended to compute minimum cost flows.^[5] 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.^[4]^[6]

Concepts

Definitions and notations

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, the excess of 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) 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 but not violate them.

The generic push-relabel algorithm

Description

Since h(s) = |V|, h(t) = 0, and there is not path 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, 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.

Relabel-to-Front Algorithm

The Relabel-to-Front algorithm is a variant of the Push-Relabel algorithm that improves the running time from $O(V^{2}E)$ to $O(V^{3})$ . It does so by executing Push and Relabel in a specified order. The main difference is we wish to apply Push and Relabel to a single vertex until its excess is completely spent. This limits the number of non-saturating pushes that we make, which is the main bottle-neck of this algorithm.

To do this, we maintain a list of all the vertices in the graph $L=V-\{s,t\}$ , in any particular order (they will be put in order as the algorithm executes). In addition to this master list, each vertex maintains a list of its neighbours in the graph, in arbitrary but static order. These neighbours are the vertices it can potentially push flow to. Then, starting at the first vertex in the list and moving to each in turn, we Discharge a vertex $u\in L$ if it is active. If a vertex is relabelled during discharge, it is moved to the front of the list, and we start again at the next vertex (formerly the first vertex). Discharge is detailed below:

Discharge

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

Function Discharge(u):
    while excess(u) > 0:
       if (u.currentNeighbour != NIL):
          push(u, u.currentNeighbour);
          u.currentNeighbour = u.nextNeighbour;
       else:
          relabel(u);
          u.currentNeighbour = u.headOfNeighbourList;    //start again at the beginning of the neighbour list

Relabel-to-Front

In the relabel-to-front algorithm we fully discharge each vertex before moving to the next one. The ordering tends to reduce the number of non-saturating pushes we do:

Algorithm Relabel-to-Front(G(V,E),s,t):
   for each vertex v incident to s:
      push(s,v);                       //note that this will saturate the edges (s,v), since the flow from s is limitless
   L = v - {s,t};                      //build a list of all vertices in any order
   current = L.head;
   while (current != NIL):
      old_height = height(u);
      discharge(u);
      if height(u) > old_height:
         Move u to front of L
      current = current.next;

The running time for relabel-to-front is $O(V^{3})$ (proof omitted). Again the bottleneck is non-saturating pushes, but we have reduced the number. Note that after step 1 there is no path from s to t in the residual graph.

Sample implementation

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])

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,\ldots ,n-1$ .
Use a gap heuristic. If there is a $k$ such that for no node, $\mathrm {height} (u)=k$ , you can set $\mathrm {height} (u)=\max(\mathrm {height} (u),\mathrm {height} (s)+1)$ for all nodes except $s$ for which $\mathrm {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\mid \mathrm {height} (u)>k\}$ to the nodes $T=\{v\mid \mathrm {height} (v)<k\}$ . If $(S,T)$ was not a minimal cut, there would be an edge $(u,v)$ such that $u\in S$ , $v\in T$ and $c(u,v)-f(u,v)>0$ . But then $\mathrm {height} (u)$ would never be set higher than $\mathrm {height} (v)+1$ , contradicting that $\mathrm {height} (u)>k$ and $\mathrm {height} (v)<k$ .

References

^ Template:Cite isbn/978026203293
^ ^a ^b Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/12130.12144, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/12130.12144 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/S0377-2217(96)00269-X, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/S0377-2217(96)00269-X instead.
^ ^a ^b Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/978-3-540-87744-8_39, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/978-3-540-87744-8_39 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1006/jagm.1995.0805, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1006/jagm.1995.0805 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1002/1520-6750(199106)38:3<413::AID-NAV3220380310>3.0.CO;2-J, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1002/1520-6750(199106)38:3<413::AID-NAV3220380310>3.0.CO;2-J instead.

[clrs26-1] Template:Cite isbn/978026203293

[goldberg86-2] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/12130.12144, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/12130.12144 instead.

[ahuja97-3] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/S0377-2217(96)00269-X, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/S0377-2217(96)00269-X instead.

[goldberg08-4] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/978-3-540-87744-8_39, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/978-3-540-87744-8_39 instead.

[goldberg97-5] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1006/jagm.1995.0805, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1006/jagm.1995.0805 instead.

[ahuja91-6] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1002/1520-6750(199106)38:3<413::AID-NAV3220380310>3.0.CO;2-J, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1002/1520-6750(199106)38:3<413::AID-NAV3220380310>3.0.CO;2-J instead.

[1]

[2]

[3]

[4]

[5]

[6]