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(V2E) time complexity, which is asymptotically more efficient than the O(VE2) 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(V2√E) time complexity and is generally regarded as the benchmark for maximum flow algorithms.[3][4] Subcubic O(VE2 log (V2/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 cf(u, v) = c(u, v) − f(u, v). The residual network of G with respect to a preflow f is defined as Gf(V, Ef) where Ef = {(u, v) | u, v ∈ V ∧ cf(u, v) > 0}. If there is no path from any active vertex to t in Gf, 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 Gf, 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) ∈ Ef
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 Gf 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 Gf because no such paths can be longer than (|V| − 1).
An edge (u, v) ∈ Ef is called admissible if h(u) = h(v) + 1. The network G̃f(V, Ẽf) where Ẽf = {(u, v) | (u, v) ∈ Ef ∧ 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 Gf. It moves min{e(u), cf(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 Gf. 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 cf(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 Ef, where h(v) = h(u) − 1 ≤ h(u) + 1; it may also remove the edge (u, v) from Ef, 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 Gf. For the in-edges of u in the Gf, the increased h(u) can only satisfy the constraints less tightly but not violate them.
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 before this is complete, as the longest possible path back to s excluding t is long, and . 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:
is active Or . There is more flow entering than exiting the vertex. There is a residual edge from u to v, where 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:
is active where
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 (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 to . 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 , 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 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 (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 . - Use a gap heuristic. If there is a such that for no node, , you can set for all nodes except for which . This is because any such represents a minimal cut in the graph, and no more flow will go from the nodes to the nodes . If was not a minimal cut, there would be an edge such that , and . But then would never be set higher than , contradicting that and .
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.12144instead. - ^ 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-Xinstead. - ^ 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_39instead. - ^ 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.0805instead. - ^ 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-Jinstead.