Previous Next 
Flow NetworksTo describe networkflow algorithms, we begin with an idealized physical model in which several of the basic concepts are intuitive. Specifically, we imagine a collection of interconnected oil pipes of varying sizes, with switches controlling the direction of flow at junctions, as in the example illustrated in Screenshot. We suppose further that the network has a single source (say, an oil field) and a single sink (say, a large refinery) to which all the pipes ultimately connect. At each vertex, the flowing oil reaches an equilibrium where the amount of oil flowing in is equal to the amount flowing out. We measure both flow and pipe capacity in the same units (say, gallons per second). Screenshot Network flowA flow network is a weighted network where we interpret edge weights as capacities (top). Our objective is to compute a second set of edge weights, bounded by the capacities, which we call the flow. The bottom drawing illustrates our conventions for drawing flow networks. Each edge's width is proportional to its capacity; the amount of flow in each edge is shaded in gray; the flow is always directed down the page from a single source at the top to a single sink at the bottom; and intersections (such as 14 and 23 in this example) do not represent vertices unless labeled as such. Except for the source and the sink, flow in is equal to flow out at every vertex: For example, vertex 2 has 2 units of flow coming in (from 0) and 2 units of flow going out (1 unit to 3 and 1 unit to 4). If every switch has the property that the total capacity of the ingoing pipes is equal to the total capacity of the outgoing pipes, then there is no problem to solve: We simply fill all pipes to full capacity. Otherwise, not all pipes are full, but oil flows through the network, controlled by switch settings at the junctions, such that the amount of oil flowing into each junction is equal to the amount of oil flowing out. But this local equilibrium at the junctions implies an equilibrium in the network as a whole: We prove in Property 22.1 that the amount of oil flowing into the sink is equal to the amount flowing out of the source. Moreover, as illustrated in Screenshot, the switch settings at the junctions of this amount of flow from source to sink have nontrivial effects on the flow through the network. Given these facts, we are interested in the following question: What switch settings will maximize the amount of oil flowing from source to sink? Screenshot Controlling flow in a networkWe might initialize the flow in this network by opening the switches along the path 0135, which can handle 2 units of flow (top), and by opening switches along the path 0245 to get another 1 unit of flow in the network (center). Asterisks indicate full edges. Since 01, 24, and 35 are full, there is no direct way to get more flow from 0 to 5, but if we change the switch at 1 to redirect enough flow to fill 14, we open up enough capacity in 35 to allow us to add flow on 0235, giving a maxflow for this network (bottom). We can model this situation directly with a network (a weighted digraph, as defined in ) that has a single source and a single sink. The edges in the network correspond to the oil pipes, the vertices correspond to the junctions with switches that control how much oil goes into each outgoing edge, and the weights on the edges correspond to the capacity of the pipes. We assume that the edges are directed, specifying that oil can flow in only one direction in each pipe. Each pipe has a certain amount of flow, which is less than or equal to its capacity, and every vertex satisfies the equilibrium condition that the flow in is equal to the flow out. This flownetwork abstraction is a useful problemsolving model that applies directly to a variety of apps and indirectly to still more. We sometimes appeal to the idea of oil flowing through pipes for intuitive support of basic ideas, but our discussion applies equally well to goods moving through distribution channels and to numerous other situations. The flow model directly applies to a distribution scenario: We interpret the flow values as rates of flow so that a flow network describes the flow of goods in a manner precisely analogous to the flow of oil. For example, we can interpret the flow in Screenshot as specifying that we should be sending two items per time unit from 0 to 1 and from 0 to 2, one item per time unit from 1 to 3 and from 1 to 4, and so forth. Another way to interpret the flow model for a distribution scenario is to interpret flow values as amounts of goods so that a flow network describes a onetime transfer of goods. For example, we can interpret the flow in Screenshot as describing the transfer of four items from 0 to 5 in the following threestep process: First, send two items from 0 to 1 and two items from 0 to 2, leaving two items at each of those vertices. Second, send one item each from 1 to 3, 1 to 4, 2 to 3, and 2 to 4, leaving two items each at 3 and 4. Third, complete the transfer by sending two items from 3 to 5 and two items from 4 to 5. As with our use of distance in shortestpaths algorithms, we are free to abandon any physical intuition when convenient because all the definitions, properties, and algorithms that we consider are based entirely on an abstract model that does not necessarily obey physical laws. Indeed, a prime reason for our interest in the networkflow model is that it allows us to solve numerous other problems through reduction, as we see in s 22.4 and 22.6. Because of this broad applicability, it is worthwhile to consider precise statements of the terms and concepts that we have just informally introduced. Definition 22.1 We refer to a network with a designated source s and a designated sink t as an stnetwork. We use the modifier "designated" here to mean that s does not necessarily have to be a source (vertex with no incoming edges) and t does not necessarily have to be a sink (vertex with no outgoing edges), but that we nonetheless treat them as such, because our discussion (and our algorithms) will ignore edges directed into s and edges directed out of t. To avoid confusion, we use networks with a single source and a single sink in examples; we consider more general situations in . We refer to s and t as "the source" and "the sink," respectively, in the stnetwork because those are the roles that they play in the network. We also refer to the other vertices in the network as the internal vertices. Definition 22.2 A flow network is an stnetwork with positive edge weights, which we refer to as capacities. A flow in a flow network is a set of nonnegative edge weights—which we refer to as edge flows—satisfying the conditions that no edge's flow is greater than that edge's capacity and that the total flow into each internal vertex is equal to the total flow out of that vertex. We refer to the total flow into a vertex (the sum of the flows on its incoming edges) as the vertex's inflow and the total flow out of a vertex (the sum of the flows on its outgoing edges) as the vertex's outflow. By convention, we set the flow on edges into the source and edges out of the sink to zero, and in Property 22.1 we prove that the source's outflow is always equal to the sink's inflow, which we refer to as the network's value. With these definitions, the formal statement of our basic problem is straightforward. Maximum flow Given an stnetwork, find a flow such that no other flow from s to t has larger value. For brevity, we refer to such a flow as a maxflow and the problem of finding one in a network as the maxflow problem. In some apps, we might be content to know just the maxflow value, but we generally want to know a flow (edge flow values) that achieves that value. Variations on the problem immediately come to mind. Can we allow multiple sources and sinks? Should we be able to handle networks with no sources or sinks? Can we allow flow in either direction in the edges? Can we have capacity restrictions for the vertices instead of or in addition to the restrictions for the edges? As is typical with graph algorithms, separating restrictions that are trivial to handle from those that have profound implications can be a challenge. We investigate this challenge and give examples of reducing to maxflow a variety of problems that seem different in character, after we consider algorithms to solve the basic problem, in s 22.2 and 22.3. The characteristic property of flows is the local equilibrium condition that inflow be equal to outflow at each internal vertex. There is no such constraint on capacities; indeed, the imbalance between total capacity of incoming edges and total capacity of outgoing edges is what characterizes the maxflow problem. The equilibrium constraint has to hold at each and every internal vertex, and it turns out that this local property determines global movement through the network, as well. Although this idea is intuitive, it needs to be proved. Property 22.1 Any stflow has the property that outflow from s is equal to the inflow to t. Proof: (We use the term stflow to mean "flow in an stnetwork.") Augment the network with an edge from a dummy vertex into s, with flow and capacity equal to the outflow from s, and with an edge from t to another dummy vertex, with flow and capacity equal to the inflow to t. Then, we can prove a more general property by induction: Inflow is equal to outflow for any set of vertices (not including the dummy vertices). This property is true for any single vertex, by local equilibrium. Now, assume that it is true for a given set of vertices S and that we add a single vertex v to make the set S' = S {v}. To compute inflow and outflow for S', note that each edge from v to some vertex in S reduces outflow (from v) by the same amount as it reduces inflow (to S); each edge to v from some vertex in S reduces inflow (to v) by the same amount as it reduces outflow (from S); and all other edges provide inflow or outflow for S' if and only if they do so for S or v. Thus, inflow and outflow are equal for S', and the value of the flow is equal to the sum of the values of the flows of v and S minus sum of the flows on the edges connecting v to a vertex in S (in either direction). Applying this property to the set of all the network's vertices, we find that the source's inflow from its associated dummy vertex (which is equal to the source's outflow) is equal to the sink's outflow to its associated dummy vertex (which is equal to the sink's inflow). Corollary The value of the flow for the union of two sets of vertices is equal to the sum of the values of the flows for the two sets minus the sum of the weights of the edges that connect a vertex in one to a vertex in the other. Proof: The proof just given for a set S and a vertex v still works if we replace v by a set T (which is disjoint from S) in the proof. An example of this property is illustrated in Screenshot. Screenshot Flow equilibriumThis diagram illustrates the preservation of flow equilibrium when we merge sets of vertices. The two smaller figures represent any two disjoint sets of vertices, and the letters represent flow in sets of edges as indicated: A is the amount of flow into the set on the left from outside the set on the right, x is the amount of flow into the set on the left from the set on the right, and so forth. Now, if we have flow equilibrium in the two sets, then we must have
for the set on the left and
for the set on the right. Adding these two equations and canceling the x + y terms, we conclude that
or inflow is equal to outflow for the union of the two sets. We can dispense with the dummy vertices in the proof of Property 22.1, augment any flow network with an edge from t to s with flow and capacity equal to the network's value, and know that inflow is equal to outflow for any set of nodes in the augmented network. Such a flow is called a circulation, and this construction demonstrates that the maxflow problem reduces to the problem of finding a circulation that maximizes the flow along a given edge. This formulation simplifies our discussion in some situations. For example, it leads to an interesting alternate representation of flows as a set of cycles, as illustrated in Screenshot. Screenshot Cycle flow representationThis figure demonstrates that the circulation at left decomposes into the four cycles 13541, 0135420, 135421, 3543, with weights 2, 1, 1, and 3, respectively. Each cycle's edges appear in its respective column, and summing each edge's weight from each cycle in which it appears (across its respective row) gives its weight in the circulation. Given a set of cycles and a flow value for each cycle, it is easy to compute the corresponding circulation by following through each cycle and adding the indicated flow value to each edge. The converse property is more surprising: We can find a set of cycles (with a flow value for each) that is equivalent to any given circulation. Property 22.2 (Flow decomposition theorem) Any circulation can be represented as flow along a set of at most E directed cycles. Proof: A simple algorithm establishes this result. Iterate the following process as long as there is any edge that has flow: Starting with any edge that has flow, follow any edge leaving that edge's destination vertex that has flow and continue until encountering a vertex that has already been visited (a cycle has been detected). Go back around the cycle to find an edge with minimal flow, then reduce the flow on every edge in the cycle by that amount. Each iteration of this process reduces the flow on at least one edge to 0, so there are at most E cycles. Screenshot illustrates the process described in the proof. For stflows, applying this property to the circulation created by the addition of an edge from t to s gives the result that any stflow can be represented as flow along a set of at most E directed paths, each of which is either a path from s to t or a cycle. Screenshot Cycle flow decomposition processTo decompose any circulation into a set of cycles, we iterate the following process: Follow any path until encountering a node for the second time, then find the minimum weight on the indicated cycle, then subtract that weight from each edge on the cycle and remove any edge whose weight becomes 0. For example, the first iteration is to follow the path 013541 to find the cycle 13541, then subtract 1 from the weights of each of the edges on the cycle, which causes us to remove 41 because its weight becomes 0. In the second iteration, we remove 01 and 20; in the third iteration, we remove 13, 42, and 21; and in the fourth iteration, we remove 35, 54, and 43. Corollary Any stnetwork has a maxflow such that the subgraph induced by nonzero flow values is acyclic. Proof: Cycles that do not contain ts do not contribute to the value of the flow, so we can change the flow to 0 along any such cycle without changing the value of the flow. Corollary Any stnetwork has a maxflow that can be represented as flow along a set of at most E directed paths from s to t. Proof: Immediate. This representation provides a useful insight into the nature of flows that is helpful in the design and analysis of maxflow algorithms. On the one hand, we might consider a more general formulation of the maxflow problem where we allow for multiple sources and sinks. Doing so would allow our algorithms to be used for a broader range of apps. On the other hand, we might consider special cases, such as restricting attention to acyclic networks. Doing so might make the problem easier to solve. In fact, as we see in , these variants are equivalent in difficulty to the version that we are considering. Therefore, in the first case, we can adapt our algorithms and implementations to the broader range of apps; in the second case, we cannot expect an easier solution. In our figures, we use acyclic networks because the examples are easier to understand when they have an implicit flow direction (down the page), but our implementations allow networks with cycles. To represent flow networks, we use essentially the same class that we used for sparse undirected graphs in , with references to objects of a more sophisticated Edge type. Instead of the single weight that we used in s 20 and 21, we use pcap and pflow private data fields (with cap() and flow() public methods that return their values) for capacity and flow, respectively. Even though flow networks are directed graphs, our algorithms need to traverse edges in both directions, so we use the undirected graph representation from and the method from to distinguish uv from vu (the edges hold their direction). Since flow networks are typically sparse, we use an adjacencylists–based representation like Program 20.5. Typical flow networks may have multiple edges (of varying capacities) connecting two given vertices. This situation requires no special treatment with adjacency lists, but with an adjacencymatrix–based representation, clients have to collapse such edges into a single edge. Specifically, we drop the second constructor argument, the digraph flag, and the directed method from Program 20.5 and use the name Network for the resulting class. Working with references to edges allows us to separate the abstraction needed by our algorithms (edges going in both directions) from the client's concrete data structure and leaves a simple goal for our algorithms: Assign values to the flow data fields in the client's edges that maximize flow through the network. Indeed, a critical component of our implementations involves a changing network abstraction that is dependent on flow values and implemented with Edge methods. We will consider an Edge implementation (Program 22.2) in . In the network representations of s 20 and 21, we used the convention that weights are real numbers between 0 and 1. In this chapter, we assume that the weights (capacities and flows) are all mbit integers (between 0 and 2^{m} – 1). We do so for two primary reasons: First, we frequently need to test for equality among linear combinations of weights, and doing so can be inconvenient in floatingpoint representations. Second, the running times of our algorithms can depend on the relative values of the weights, and the parameter M = 2^{m} gives us a convenient way to bound weight values. For example, the ratio of the largest weight to the smallest nonzero weight is less than M. The use of integer weights is but one of many possible alternatives (see, for example, Exercise 20.8) that we could choose to address these problems.
We sometimes refer to edges as having infinite capacity, or, equivalently, as being uncapacitated. That might mean that we do not compare flow against capacity for such edges, or we might use a sentinel value that is guaranteed to be larger than any flow value. Program 22.1 is a client that checks whether a flow satisfies the equilibrium condition at every node and returns that flow's value if the flow does. Typically, we might do such a check as the final action of a maxflow algorithm. Despite our confidence as mathematicians in Property 22.1, our paranoia as programmers dictates that we also check that the flow out of the source is equal to the flow into the sink. It might also be prudent to check that no edge's flow exceeds that edge's capacity and that the data structures are internally consistent (see Exercise 22.12). Exercises

Previous Next 