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^{2}{\sqrt {E}})$ complexity, and the implementation with Sleator's and Tarjan's dynamic tree data structure runs in $O(VE\log(V^{2}/E))$ time. Asymptotically, it is more efficient than the Edmonds–Karp algorithm, which runs in $O(VE^{2})$ time.

Overview

In a flow network, flow going into a vertex must equal flow going out of a vertex (with the exception of the source node and the sink node, s and t respectively). Thus we cannot accumulate flow anywhere in the network.

The Preflow algorithm relaxes this constraint while it determines the maximum flow of the network, allowing a vertex to have more flow coming into it than going out. This is called the excess flow of a vertex, or preflow. Any vertex with excess flow is known as an active vertex. Excess flow can only be moved down residual edges of the residual graph. Flow is pushed through the network by adjusting the height of the vertices. Height is updated and maintained via the concept of a valid labelling. Stated precisely this labelling is $h(u)\leq h(v)+1$, where h(u) is height of vertex u, for each residual edge incident to u. In other words a vertex cannot be more than 1 higher from its neighbour on a residual edge (there is no bound on how much lower it can be). Flow always goes from a higher vertex to a lower vertex.

To push preflow is to move it down a residual edge from a vertex u to a vertex v, where $h(u)=h(v)+1$. It is called a saturating push if all of the capacity of the residual edge was used (and thus the edge (u,v) is removed from the residual graph). It is called a non-saturating push if after the push there is still available capacity on edge (u,v). Note that a non-saturating push will deplete all the excess flow from vertex u. A saturating push may deplete u, but not necessarily.

Definition

Given a flow network $G(V,E)$ with capacity from node u to node v given as $c(u,v)$, 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.
residual edge:	If available capacity $c(u,v)-f(u,v)>0$ we have a residual edge $r(u,v)$.
residual edge (Alternate):	$r(v,u)=-f(u,v)$. We can push flow back along an edge.
residual graph:	The set of all residual edges forms the residual graph.
legal labelling:	For each residual edge $(u,v),\mathrm {height} (u)\leq \mathrm {height} (v)+1$. We only push from u to v if $\mathrm {height} (u)=\mathrm {height} (v)+1$.
excess(u):	Sum of flow to and from u.

There are three conditions for flow networks:

Capacity constraints:	$\ f(u,v)\leq c(u,v)$. The flow along an edge cannot exceed its capacity.
Skew symmetry:	$\ f(u,v)=-f(v,u)$. The net flow from $\ u$ to $\ v$ must be the opposite of the net flow from $\ v$ to $\ u$ (see example).
Flow conservation:	$\ \sum _{w\in V}f(u,w)=0$, unless $\ u=s$ or $\ u=t$. The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.

The preflow algorithm observes the first two of the conditions of flow networks, plus a relaxed third condition for the duration of the algorithm (the algorithm finishes once all the excess is gone from the graph, at which point we have a legal flow, and the Flow conservation constraint is again observed):

Non-negativity constraint: $\ \sum _{v}f(v,u)=\mathrm {excess} (u)\geq 0$ for all nodes $u\neq s$. More flow enters a node than exits.

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, $\mathrm {height} (s)=|V|$ and $\mathrm {height} (t)=0$, and if there is a positive flow from u to v, $\mathrm {height} (u)>\mathrm {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.

Algorithm

The heights of active vertices are raised just enough to send flow into neighbouring vertices, 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 $\mathrm {height} (s)=|V|$. The height of t is kept at 0.

Once we move all the flow we can to t, there is no more path in the residual graph from s to t (in fact this is true as soon as we saturate the min-cut). This means that once the remaining excess flows back to s not only do we have a legal flow, but we have a maximum flow by the max-flow min-cut theorem.

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:

$u$ is active	Which means $\mathrm {excess} (u)>0$. There is more flow entering than exiting the vertex.
$r(u,v)>0$	There is a residual edge $r(u,v)$ from u to v, where $r(u,v)=c(u,v)-f(u,v)$
$\mathrm {height} (u)=\mathrm {height} (v)+1$	We have a legal labelling of u and v.

When we execute the push we send an amount of flow equal to $\min(\mathrm {excess} (u),c(u,v)-f(u,v))$.

Relabel

When we relabel a node u we increase its height until it is 1 higher than its lowest neighbour in the residual graph. Conditions for a relabel:

• u is active, that is $\mathrm {excess} (u)>0$.
• $\mathrm {height} (u)\leq \mathrm {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 $\mathrm {height} (u)$ to be 1 greater than its lowest neighbour v where $c(u,v)-f(u,v)>0$.

Push–relabel algorithm

Push–relabel algorithms in general have the following layout:

1. 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 when not observing any order to the Push and Relabel operations is $O(V^{2}E)$ (argument omitted). The bottleneck is the number of non-saturating pushes.

Relabel-to-Front Algorithm (FIFO heuristic)

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 are the vertices it will attempt to push flow to. Then, starting at the first vertex, we Discharge a vertex $u\in L$ if it is active. Discharge is detailed below:

Discharge

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

1. While $\mathrm {excess} (u)>0$:
   1. If there are still neighbours in the neighbour list since the last relabel:
      1. Try to push flow to the next neighbour.
   2. Else:
      1. Relabel u
      2. Move pointer to head of neighbour list

Relabel-to-Front

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

1. For each edge incident to $s,(s,v)$, push flow from s equal to $c(s,v)$ (saturate the edge).
2. Build a list $L$ of all vertices except s and t.
3. For each $u\in L$:
   1. Discharge the current vertex u.
   2. If the height of u has changed:
      1. Move u to the front of the list L
      2. Restart the traversal from the element following u in L.

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. Not 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:

1. 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$.
2. 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

• 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. 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–146. ISBN 0-89791-193-8, 1986