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. Compared to the Ford–Fulkerson algorithm, which perform global augmentations that send flow following paths from the source to the sink, the push-relabel algorithm relies on local updates that move flow between neighboring vertices.

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.

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.

Definitions

Main article: Flow network

The push-relabel algorithm finds maximum flow on a flow network. There are three conditions for a flow network:

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 _{w\in V}f(u,w)=\mathrm {excess} (u)\geq 0$ for all nodes $u\neq s$. More flow enters a node than exits.

Given a flow network $G(V,E)$ with capacity from node u to node v given as $c(u,v)$, and the flow across u and v given as $f(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. Some key concepts used in the algorithm are:

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.
height(u):	Each vertex is assigned a height value. For values $\leq |V|$, the height serves as an estimate of the distance to the sink node t. For values $>|V|$, the height is an estimate of the distance back to the sink s.

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.

Push-relabel 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. The algorithm relies on two functions:

Push

A push from u to v means sending as much excess flow from u to v as we can. Three conditions must be met for a push to take place:

$u$ is active	Or $\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$	u is higher than v.

If all these conditions are met we can execute a Push:

Function Push(u,v)
   flow = min(excess(u), c(u,v)-f(u,v));
   excess(u) -= flow;                   // subtract the amount of flow moved from the current vertex
   excess(v) += flow;                   // add the flow to the vertex we are pushing to
   f(u,v) += flow;                      // add the amount of flow moved to the flow across the edge (u,v)
   f(v,u) -= flow;                      // subtract the flow from the edge in the other direction.

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
$\mathrm {height} (u)\leq \mathrm {height} (v)$ where $r(u,v)>0$

So we have excess flow to push, but we are not higher than any of our neighbours that have available capacity across their edge. Then we can execute Relabel:

Function Relabel(u)
   height(u) = min(height(v) where r(u,v) > 0) + 1;

Push–relabel algorithm

The generic Push–relabel algorithm has the following structure:

Algorithm Push-relabel(G(V,E),s,t) 
   while push or relabel are legal:   //in other words while there is excess in the network
      Perform a legal push, or
      perform a legal relabel;

Executing these two functions in any order, so long as there remains any active vertices results in termination of the algorithm in a maximum flow. 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

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:

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

• Template:Cite isbn/978026203293

• Template:Cite isbn/978026203293