Cormen, Leiserson, Rivest, Stein. Introduction to algorithms 2ed, MIT, 2001 ISBN 0070131511 984s Chapter 26
In this section, we present the "push-relabel" approach to computing maximum flows. To date, many of the asymptotically fastest maximum-flow algorithms are push-relabel algorithms, and the fastest actual implementations of maximum-flow algorithms are based on the push-relabel method. Other flow problems, such as the minimum-cost flow problem, can be solved efficiently by push-relabel methods. This section introduces Goldberg's "generic" maximum-flow algorithm, which has a simple implementation that runs in O(V^2 E) time, thereby improving upon the O(VE2) bound of the Edmonds-Karp algorithm. Section 26.5 refines the generic algorithm to obtain another push-relabel algorithm that runs in O(V3) time.
Push-relabel algorithms work in a more localized manner than the Ford-Fulkerson method. Rather than examine the entire residual network G = (V,E) to find an augmenting path, push-relabel algorithms work on one vertex at a time, looking only at the vertex's neighbors in the residual network. Furthermore, unlike the Ford-Fulkerson method, push-relabel algorithms do not maintain the flow-conservation property throughout their execution. They do, however, maintain apreflow, which is a function: VxV -> R, that satisfies skew symmetry, capacity constraints, and the following relaxation of flow conservation: : f(V; u) > 0 for all vertices u E V-s. That is, the total net flow at each vertex other than the source is nonnegative. We call the total net flow at a vertex è the excess flow into u9 given by e(u)=f(V,u). We say that a vertex u E V-{s,t} is overflowing if e(u)>0.
We shall start this section by describing the intuition behind the push-relabel method. We shall then investigate the two operations employed by the method: "pushing" preflow and "relabeling" a vertex. Finally, we shall present a generic push-relabel algorithm and analyze its correctness and running time.
The intuition behind the push-relabel method is probably best understood in terms of fluid flows: we consider a flow network G = (F, E) to be a system of interconnected pipes of given capacities. Applying this analogy to the Ford-Fulkerson method, we might say that each augmenting path in the network gives rise to an additional stream of fluid, with no branch points, flowing from the source to the sink. The Ford-Fulkerson method iteratively adds more streams of flow until no more can be added.
The generic push-relabel algorithm has a rather different intuition. As before, directed edges correspond to pipes. Vertices, which are pipe junctions, have two interesting properties. First, to accommodate excess flow, each vertex has an out-flow pipe leading to an arbitrarily large reservoir that can accumulate fluid. Second, each vertex, its reservoir, and all its pipe connections are on a platform whose height increases as the algorithm progresses.
Vertex heights determine how flow is pushed: we only push flow downhill, that is, from a higher vertex to a lower vertex. The flow from a lower vertex to a higher vertex may be positive, but operations that push flow only push it downhill. The height of the source is fixed at |V| and the height of the sink is fixed at 0. All other vertex heights start at 0 and increase with time. The algorithm first sends as much flow as possible downhill from the source toward the sink. The amount it sends is exactly enough to fill each outgoing pipe from the source to capacity; that is, it sends the capacity of the cut (s, V - s). When flow first enters an intermediate vertex, it collects in the vertex's reservoir. From there, it is eventually pushed downhill.
It may eventually happen that the only pipes that leave a vertex è and are not already saturated with flow connect to vertices that are on the same level as è or are uphill from u. In this case, to rid an overflowing vertex è of its excess flow, we must increase its height-an operation called "relabeling" vertex u. Its height is increased to one unit more than the height of the lowest of its neighbors to which it has an unsaturated pipe. After a vertex is relabeled, therefore, there is at least one outgoing pipe through which more flow can be pushed.
Eventually, all the flow that can possibly get through to the sink has arrived there. No more can arrive, because the pipes obey the capacity constraints; the amount of flow across any cut is still limited by the capacity of the cut. To make the preflow a "legal" flow, the algorithm then sends the excess collected in the reservoirs of overflowing vertices back to the source by continuing to relabel vertices to above the fixed height |V| of the source. As we shall see, once all the reservoirs have been emptied, the preflow is not only a "legal" flow, it is also a maximum flow.
From the preceding discussion, we see that there are two basic operations performed by a push-relabel algorithm: pushing flow excess from a vertex to one of its neighbors and relabeling a vertex. The applicability of these operations depends on the heights of vertices, which we now define precisely.
Let G = (V;E) be a flow network with source s and sink t, and let/be a preflow in G. A function h : V -> N is a height function if h(s) = |V|, h(t) = 0 and h(u) < h(v) + 1 for every residual edge (u;v) E Ef. We immediately obtain the following lemma.
Let f - be a flow network, let/be a preflow in G, and let h be a height function on V For any two vertices u,v E V, if h(u) > h(v) + 1, then (u, v) is not an edge in the residual graph.
The basic operation Push(u; v) can be applied if è is an overflowing vertex, c(u; v) > 0 and h(u) = h(v)+1. The pseudocode below updates the preflow f in an implied network G=(V;E). It assumes that residual capacities can also be computed in constant time given ñ and f The excess flow stored at a vertex è is maintained as the attribute e[u], and the height of è is maintained as the attribute h[u]. The expression df(u, v) is a temporary variable that stores the amount of flow that can be pushed from è to v.
Push(u,v) 1. Applies when: u is overflowing, cf(u,,v)>0, and h[u]=h[v]+1 2. Action: Push df(u,v)=min(e[u],cf(u,n)) units of flow fuom u to v 3. df(u,v)=min(e[u],cf(u,v)) 4. f[u,v]=f[u,v]+df(u,v) 5. f[v,t]=-f[u,v] 6. e[u]=e[u]-df(u,v) 7. e[v]=e[v]+df(u,v)
The code for PUSH operates as follows:
Vertex è is assumed to have a positive excess e[u], and the residual capacity of (w, v) is positive. Thus, we can we increase the flow from è to v by min(e[u];cf(u; v)) > 0. without causing e[u] to become negative or the capacity c(u, v) to be exceeded. Line 3 computes the value df(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 è 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(w, v) a push from è to v. If a push operation applies to some edge (w, v) leaving a vertex u, we also say that the push operation applies to u. It is a saturating push if edge (w, v) becomes saturated (cf(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.
After a nonsaturating push from è to v, the vertex è is no longer overflowing.
Since the push was nonsaturating, the amount of flow dj(u, v) actually pushed must equal e[u] prior to the push. Since e[u] is reduced by this amount, it becomes 0 after the push.
The basic operation RELABEL (u) applies if è is overflowing and if h[u] < h[v] for all edges (u, v) E Ef. In other words, we can relabel an overflowing vertex è if for every vertex v for which there is residual capacity from è to v, flow cannot be pushed from è to v because v is not downhill from u. (Recall that by definition, neither the source s nor the sink t can be overflowing, so neither s nor t can be relabeled.)
Relabel(u)
1. Applies when: u is overflowing and for all v E V such that (u,v) E Ef, we have h[v]>=f[u]
2. Action: Increase the height of u.
3. h[u]=1+min{h[v]: (u,v) E Ef}
When we call the operation RELABEL(w), we say that vertex è is relabeled. Note that when u is relabeled, Ef must contain at least one edge that leaves u, so that the minimization in the code is over a nonempty set. This property follows from the assumption that è is overflowing. Since e[u] > 0, we have e[u] =f {V, u) > 0, and hence there must be at least one vertex v such that f[v,u] > 0. But then,
cf(u,v) = c(u,v) - f[u,v] = = c(u,v) + f[v,u] > > 0
which implies that (u;v) E Ef. The operation RELABEL(w) thus gives è the greatest height allowed by the constraints on height functions.
The generic push-relabel algorithm uses the following subroutine to create an initial preflow in the flow network.
Imitialize-Preflow(G,s) 1. for each vertex u E V[G] 2. do h[u]=0 3. e[u]=0 4. for each edge (u,v) E E[G] 5. do f[u,v]=0 6. f[v,u]=0 7. h[s]=|V[G]| 8. for each vertex r E 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
c(u,v) if u=s;
f[u,v]= -c(v,u) if v=s;
0 otherwise
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
h[u]=|V| if u=s;
0 otherwise
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.
Gemeric-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