Preflow-Push Maxflow Algorithms
In this section, we consider another approach to solving the maxflow problem. Using a generic method known as the preflow-push method, we incrementally move flow along the outgoing edges of vertices that have more inflow than outflow. The preflow-push approach was developed by A. Goldberg and R. E. Tarjan in 1986 on the basis of various earlier algorithms. It is widely used because of its simplicity, flexibility, and efficiency. As defined in , a flow must satisfy the equilibrium conditions that the outflow from the source is equal to the inflow to the sink and that inflow is equal to the outflow at each of the internal nodes. We refer to such a flow as a feasible flow. An augmenting-path algorithm always maintains a feasible flow: It increases the flow along augmenting paths until a maxflow is achieved. By contrast, the preflow-push algorithms that we consider in this section maintain maxflows that are not feasible because some vertices have more inflow than outflow: They push flow through such vertices until a feasible flow is achieved (no such vertices remain). Definition 22.5 In a flow network, a preflow is a set of positive edge flows satisfying the conditions that the flow on each edge is no greater than that edge's capacity and that inflow is no smaller than outflow for every internal vertex. An active vertex is an internal vertex whose inflow is larger than its outflow (by convention, the source and sink are never active). We refer to the difference between an active vertex's inflow and outflow as that vertex's excess. To change the set of active vertices, we choose one and push its excess along an outgoing edge, or, if there is insufficient capacity to do so, push the excess back along an incoming edge. If the push equalizes the vertex's inflow and outflow, the vertex becomes inactive; the flow pushed to another vertex may activate that vertex. The preflow-push method provides a systematic way to push excess out of active vertices repeatedly so that the process terminates in a maxflow, with no active vertices. We keep active vertices on a generalized queue. As for the augmenting-path method, this decision gives a generic algorithm that encompasses a whole family of more specific algorithms. Screenshot is a small example that illustrates the basic operations used in preflow-push algorithms, in terms of the metaphor that we have been using, where we imagine that flow can go only down the page. Either we push excess flow out of an active vertex down an outgoing edge or we imagine that the vertex temporarily moves up so that we can push excess flow back down an incoming edge.
Screenshot Preflow-push example
In the preflow-push algorithm, we maintain a list of the active nodes that have more incoming than outgoing flow (shown below each network). One version of the algorithm is a loop that chooses an active node from the list and pushes flow along outgoing edges until it is no longer active, perhaps creating other active nodes in the process. In this example, we push flow along 0-1, which makes 1 active. Next, we push flow along 1-2 and 1-3, which makes 1 inactive but 2 and 3 both active. Then, we push flow along 2-4, which makes 2 inactive. But 3-4 does not have sufficient capacity for us to push flow along it to make 3 inactive, so we also push flow back along 3-1 to do so, which makes 1 active. Then we can push the flow along 1-2 and then 2-4, which makes all nodes inactive and leaves a maxflow.
Screenshot is an example that illustrates why the preflow-push approach might be preferred to the augmenting-paths approach. In this network, any augmenting-path method successively puts a tiny amount of flow through a long path over and over again, slowly filling up the edges on the path until finally the maxflow is reached. By contrast, the preflow-push method fills up the edges on the long path as it traverses that path for the first time, then distributes that flow directly to the sink without traversing the long path again.
Screenshot Bad case for the Ford–Fulkerson algorithm
This network represents a family of networks with V vertices for which any augmenting-path algorithm requires V/2 paths of length V/2 (since every augmenting path has to include the long vertical path), for a total running time proportional to V2. Preflow-push algorithms find maxflows in such networks in linear time.
As we did in augmenting-path algorithms, we use the residual network (see Definition 22.4) to keep track of the edges that we might push flow through. Every edge in the residual network represents a potential place to push flow. If a residual-network edge is in the same direction as the corresponding edge in the flow network, we increase the flow; if it is in the opposite direction, we decrease the flow. If the increase fills the edge or the decrease empties the edge, the corresponding edge disappears from the residual network. For preflow-push algorithms, we use an additional mechanism to help decide which of the edges in the residual network can help us to eliminate active vertices. Definition 22.6 A height function for a given flow in a flow network is a set of nonnegative vertex weights h(0)...h(V – 1) such that h(t) = 0 for the sink t and h (u) h(v) + 1 for every edge u-v in the residual network for the flow. An eligible edge is an edge u-v in the residual network with h (u) = h(v) + 1. A trivial height function, for which there are no eligible edges, is h(0) = h(1) = ... = h(V – 1) = 0. If we set h(s) = 1, then any edge that emanates from the source and has flow corresponds to an eligible edge in the residual network. We define a more interesting height function by assigning to each vertex the latter's shortest-path distance to the sink (its distance to the root in any BFS tree for the reverse of the network rooted at t, as illustrated in Screenshot). This height function is valid because h(t) = 0, and, for any pair of vertices u and v connected by an edge u-v, any shortest path to t starting with u-v is of length h(v) + 1; so the shortest-path length from u to t, or h(u), must be less than or equal to that value. This function plays a special role because it puts each vertex at the maximum possible height. Working backward, we see that t has to be at height 0; the only vertices that could be at height 1 are those with an edge directed to t in the residual network; the only vertices that could be at height 2 are those that have edges directed to vertices that could be at height 1, and so forth.
Screenshot Initial height function
The tree at the right is a BFS tree rooted at 5 for the reverse of our sample network (left). The vertex-indexed array h gives the distance from each vertex to the root and is a valid height function: For every edge u-v in the network, h[u] is less than or equal to h[v]+1.
Property 22.9 For any flow and associated height function, a vertex's height is no larger than the length of the shortest path from that vertex to the sink in the residual network. Proof: For any given vertex u, let d be the shortest-path length from u to t, and let u = u1, u2, ..., ud = t be a shortest path. Then
The intuition behind height functions is the following: When an active node's height is less than the height of the source, it is possible that there is some way to push flow from that node down to the sink; when an active node's height exceeds the height of the source, we know that that node's excess needs to be pushed back to the source. To establish this latter fact, we reorient our view of Property 22.9, where we thought about the length of the shortest path to the sink as an upper bound on the height; instead, we think of the height as a lower bound on the shortest-path length: Corollary If a vertex's height is greater than V, then there is no path from that vertex to the sink in the residual network. Proof: If there is a path from the vertex to the sink, the implication of Property 22.9 would be that the path's length is greater than V, but that cannot be true because the network has only V vertices.
Now that we understand these basic mechanisms, the generic preflow-push algorithm is simple to describe. We start with any height function and assign zero flow to all edges except those connected to the source, which we fill to capacity. Then, we repeat the following step until no active vertices remain:
We do not specify what the initial height function is, how to choose the active vertex, how to choose the eligible edge, or how much flow to push. We refer to this generic method as the edge-based preflow-push algorithm. The algorithm depends on the height function to identify eligible edges. We also use the height function both to prove that the algorithm computes a maxflow and to analyze performance. Therefore, it is critical to ensure that the height function remains valid throughout the execution of the algorithm. Property 22.10 The edge-based preflow-push algorithm preserves the validity of the height function. Proof: We increment h(u) only if there are no edges u-v with h(u) = h(v) + 1. That is, h(u) < h (v) + 1 for all edges u-v before incrementing h(u), so h(u) h(v) + 1 afterward. For any incoming edges w-u, incrementing h(u) certainly preserves the inequality h(w) h(u) + 1. Incrementing h(u) does not affect inequalities corresponding to any other edge, and we never increment h(t) (or h(s)). Together, these observations imply the stated result.
All the excess flow emanates from the source. Informally, the generic preflow-push algorithm tries to push the excess flow to the sink; if it cannot do so, it eventually pushes the excess flow back to the source. It behaves in this manner because nodes with excess always stay connected to the source in the residual network. Property 22.11 While the preflow-push algorithm is in execution on a flow network, there exists a (directed) path in that flow network's residual network from each active vertex to the source, and there are no (directed) paths from source to sink in the residual network. Proof: By induction. Initially, the only flow is in the edges leaving the source, which are filled to capacity, so the destination vertices of those edges are the only active vertices. Since the edges are filled to capacity, there is an edge in the residual network from each of those vertices to the source, and there are no edges in the residual network leaving the source. Thus, the stated property holds for the initial flow. The source is reachable from every active vertex because the only way to add to the set of active vertices is to push flow from an active vertex down an eligible edge. This operation leaves an edge in the residual network from the receiving vertex back to the active vertex, from which the source is reachable, by the inductive hypothesis. Initially, no other nodes are reachable from the source in the residual network. The first time that another node u becomes reachable from the source is when flow is pushed back along u-s (thus causing s-u to be added to the residual network). But this can happen only when h(u) is greater than h(s), which can happen only after h(u) has been incremented, because there are no edges in the residual network to vertices with lower height. The same argument shows that all nodes reachable from the source have greater height. But the sink's height is always 0, so it cannot be reachable from the source.
Corollary During the preflow-push algorithm, vertex heights are always less than 2V. Proof: We need to consider only active vertices, since the height of each inactive vertex is either the same as or 1 greater than it was the last time that the vertex was active. By the same argument as in the proof of Property 22.9, the path from a given active vertex to the source implies that that vertex's height is at most V – 2 greater than the height of the source (t cannot be on the path). The height of the source never changes, and it is initially no greater than V. Thus, active vertices are of height at most 2V – 2, and no vertex has height 2V or greater.
The generic preflow-push algorithm is simple to state and implement. Less clear, perhaps, is why it computes a maxflow. The height function is the key to establishing that it does so. Property 22.12 The preflow-push algorithm computes a maxflow. Proof: First, we have to show that the algorithm terminates. There must come a point where there are no active vertices. Once we push all the excess flow out of a vertex, that vertex cannot become active again until some of that flow is pushed back; and that pushback can happen only if the height of the vertex is increased. If we have a sequence of active vertices of unbounded length, some vertex has to appear an unbounded number of times; and it can do so only if its height grows without bound, contradicting the corollary to Property 22.9. When there are no active vertices, the flow is feasible. Since, by Property 22.11, there is also no path from source to sink in the residual network, the flow is a maxflow, by the same argument as that in the proof of Property 22.5.
It is possible to refine the proof that the algorithm terminates to give an O(V2E) bound on its worst-case running time. We leave the details to exercises (see Exercises 22.66 through 22.67), in favor of the simpler proof in Property 22.13, which applies to a less general version of the algorithm. Specifically, the implementations that we consider are based on the following more specialized instructions for the iteration:
That is, once we have chosen a vertex, we push out of it as much flow as possible. If we get to the point that the vertex still has excess flow but no eligible edges remain, we increment the vertex's height. We refer to this generic method as the vertex-based preflow-push algorithm. It is a special case of the edge-based generic algorithm, where we keep choosing the same active vertex until it becomes inactive or we have used up all the eligible edges leaving it. The correctness proof in Property 22.12 applies to any implementation of the edge-based generic algorithm, so it immediately implies that the vertex-based algorithm computes a maxflow. Program 22.5 is an implementation of the vertex-based generic algorithm that uses a generalized queue for the active vertices. It is a direct implementation of the method just described and represents a family of algorithms that differ only in their initial height function (see, for example, Exercise 22.52) and in their generalized-queue ADT implementation. This implementation assumes that the generalized queue disallows duplicate vertices; alternatively, we could add code to Program 22.5 to avoid enqueueing duplicates (see Exercises 22.61 and 22.62). Perhaps the simplest data structure to use for active vertices is a FIFO queue. Screenshot shows the operation of the algorithm on a sample network. As illustrated in the figure, it is convenient to break up the sequence of active vertices chosen into a sequence of phases, where a phase is defined to be the contents of the queue after all the vertices that were on the queue in the previous phase have been processed. Doing so helps us to bound the total running time of the algorithm.
Screenshot Residual networks (FIFO preflow-push)
This figure shows the flow networks (left) and the residual networks (right) for each phase of the FIFO preflow-push algorithm operating on our sample network. Queue contents are shown below the flow networks and distance labels below the residual networks. In the initial phase, we push flow through 0-1 and 0-2, thus making 1 and 2 active. In the second phase, we push flow from these two vertices to 3 and 4, which makes them active and 1 inactive (2 remains active and its distance label is incremented). In the third phase, we push flow through 3 and 4 to 5, which makes them inactive (2 still remains active and its distance label is again incremented). In the fourth phase, 2 is the only active node, and the edge 2-0 is admissible because of the distance-label increments, and one unit of flow is pushed back along 2-0 to complete the computation.
Property 22.13 The worst-case running time of the FIFO queue implementation of the preflow-push algorithm is proportional to V2E. Proof: We bound the number of phases using a potential function. This argument is a simple example of a powerful technique in the analysis of algorithms and data structures that we examine in more detail in Part 8.
Define the quantity f to be 0 if there are no active vertices and to be the maximum height of the active vertices otherwise, then consider the effect of each phase on the value of f. Let h0(s) be the initial height of the source. At the beginning, f = h0(s); at the end, f = 0. First, we note that the number of phases where the height of some vertex increases is no more than 2V2 – h0(s), since each of the V vertex heights can be increased to a value of at most 2V, by the corollary to Property 22.11. Since f can increase only if the height of some vertex increases, the number of phases where f increases is no more than 2V2 – h0(s). If, however, no vertex's height is incremented during a phase, then f must decrease by at least 1, since the effect of the phase was to push all excess flow from each active vertex to vertices that have smaller height. Together, these facts imply that the number of phases must be less than 4V2: The value of f is h0(s) at the beginning and can be incremented at most 2V2 – h0(s) times and therefore can be decremented at most 2V2 times. The worst case for each phase is that all vertices are on the queue and all of their edges are examined, leading to the stated bound on the total running time. This bound is tight. Screenshot illustrates a family of flow networks for which the number of phases used by the preflow-push algorithm is proportional to V2.
Screenshot FIFO preflow-push worst case
This network represents a family of networks with V vertices such that the total running time of the preflow-push algorithm is proportional to V2. It consists of unit-capacity edges emanating from the source (vertex 0) and horizontal edges of capacity v – 2 running from left to right towards the sink (vertex 10). In the initial phase of the preflow-push algorithm (top), we push one unit of flow out each edge from the source, making all the vertices active except the source and the sink. In a standard adjacency-lists representation, they appear on the FIFO queue of active vertices in reverse order, as shown below the network. In the second phase (center), we push one unit of flow from 9 to 10, making 9 inactive (temporarily); then we push one unit of flow from 8 to 9, making 8 inactive (temporarily) and making 9 active; then we push one unit of flow from 7 to 8, making 7 inactive (temporarily) and making 8 active; and so forth. Only 1 is left inactive. In the third phase (bottom), we go through a similar process to make 2 inactive, and the same process continues for V – 2 phases.
Because our implementations maintain an implicit representation of the residual network, they examine edges leaving a vertex even when those edges are not in the residual network (to test whether or not they are there). It is possible to show that we can reduce the bound in Property 22.13 from V2E to V3 for an implementation that eliminates this cost by maintaining an explicit representation of the residual network. Although the theoretical bound is the lowest that we have seen for the maxflow problem, this change may not be worth the trouble, particularly for the sparse graphs that we see in practice (see Exercises 22.63 through 22.65). Again, these worst-case bounds tend to be pessimistic and thus not necessarily useful for predicting performance on real networks (though the gap is not as excessive as we found for augmenting-path algorithms). For example, the FIFO algorithm finds the flow in the network illustrated in Screenshot in 15 phases, whereas the bound in the proof of Property 22.13 says only that it must do so in fewer than 182.
Screenshot Preflow-push algorithm (FIFO)
This sequence illustrates how the FIFO implementation of the preflow-push method finds a maximum flow in a sample network. It proceeds in phases: First it pushes as much flow as it can from the source along the edges leaving the source (top left). Then, it pushes flow from each of those nodes, continuing until all nodes are in equilibrium.
To improve performance, we might try using a stack, a randomized queue, or any other generalized queue in Program 22.5. One approach that has proved to do well in practice is to implement the generalized queue such that GQget returns the highest active vertex. We refer to this method as the highest-vertex preflow-push maxflow algorithm. We can implement this strategy with a priority queue, although it is also possible to take advantage of the particular properties of heights to implement the generalized-queue operations in constant time. A worst-case time bound of (which is V5/2 for sparse graphs) has been proved for this algorithm (see reference section); as usual, this bound is pessimistic. Many other preflow-push variants have been proposed, several of which reduce the worst-case time bound to be close to VE (see reference section). Table 22.2 shows performance results for preflow-push algorithms corresponding to those for augmenting-path algorithms in Table 22.1, for the two network models discussed in . These experiments show less performance variation for the various preflow-push methods than we observed for augmenting-path methods.
Table 22.2. Empirical study of preflow-push algorithms
There are several other possibilities to consider and many options to try for each, leading to a multitude of different algorithms to study (see, for example, Exercises 22.56 through 22.60). The dependence of an algorithm's performance on characteristics of the input network further multiplies the possibilities. The two generic algorithms that we have discussed (augmenting-path and preflow-push) are among the most important from an extensive research literature on maxflow algorithms. The quest for better maxflow algorithms is still a potentially fruitful area for further research. Researchers are motivated to develop and study new algorithms and implementations by the reality of faster algorithms for practical problems and by the possibility that a simple linear algorithm exists for the maxflow problem. Until one is discovered, we can work confidently with the algorithms and implementations that we have discussed; numerous studies have shown them to be effective for a broad range of practical maxflow problems.