SKEDSOFT

The code for PUSH operates as follows. Vertex u is assumed to have a positive excess e[u], and the residual capacity of (u, v) is positive. Thus, we can we increase the flow from u to v by d_f(u, v) = min(e[u], c_f (u, v)) without causing e[u] to become negative or the capacity c(u, v) to be exceeded. Line 3 computes the value d_f(u, v), and we update f in lines 4-5 and e in lines 6-7. Thus, if f is a preflow before PUSH is called, it remains a preflow afterward.

Observe that nothing in the code for PUSH depends on the heights of u and v, yet we prohibit it from being invoked unless h[u] = h[v] 1. Thus, excess flow is pushed downhill only by a height differential of 1. By Lemma 26.13, no residual edges exist between two vertices whose heights differ by more than 1, and thus, as long as the attribute h is indeed a height function, there is nothing to be gained by allowing flow to be pushed downhill by a height differential of more than 1.

We call the operation PUSH(u, v) a push from u to v. If a push operation applies to some edge (u, v) leaving a vertex u, we also say that the push operation applies to u. It is a saturating push if edge (u, v) becomes saturated (c_f(u, v) = 0 afterward); otherwise, it is a nonsaturating push. If an edge is saturated, it does not appear in the residual network. A simple lemma characterizes one result of a nonsaturating push.

The generic algorithm

The generic push-relabel algorithm uses the following subroutine to create an initial preflow in the flow network.

	INITIALIZE-PREFLOW(G, s)
 1  for each vertex u ∈ V[G]
 2       do h[u] ← 0
 3          e[u] ← 0
 4  for each edge (u, v) ∈ E[G]
 5       do f[u, v] ← 0
 6          f[v, u] ← 0
 7  h[s] ← |V[G]|
 8  for each vertex u ∈ Adj[s]
 9       do f[s, u] ← c(s, u)
10          f[u, s] ← -c(s,  u)
11          e[u] ← c(s, u)
12          e[s] ← e[s] - c(s, u)

INITIALIZE-PREFLOW creates an initial preflow f defined by

That is, each edge leaving the source s is filled to capacity, and all other edges carry no flow. For each vertex v adjacent to the source, we initially have e[v] = c(s, v), and e[s] is initialized to the negative of the sum of these capacities. The generic algorithm also begins with an initial height function h, given by

This is a height function because the only edges (u, v) for which h[u] > h[v] 1 are those for which u = s, and those edges are saturated, which means that they are not in the residual network.

Initialization, followed by a sequence of push and relabel operations, executed in no particular order, yields the GENERIC-PUSH-RELABEL algorithm:

	GENERIC-PUSH-RELABEL(G)
1 INITIALIZE-PREFLOW(G, s)
2 while there exists an applicable push or relabel operation
3     do select an applicable push or relabel operation and perform it