Updating maximum flow
Discuss this article in the forums This article covers a problem that often arises in real life situations and, as expected, in programming challenges, with Top Coder being no exception.
It is addressed mostly to coders who are not familiar with the subject, but it may prove useful to the more experienced as well.
The image below shows the optimal solution to an instance of this problem, each edge being labeled with the values f/c associated to it. First, let us define two basic concepts for understanding flow networks: residual networks and augmenting paths. The residual network has the same vertices as the original network, and one or two edges for each edge in the original.
More specifically, if the flow along the edge x-y is less than the capacity there is a forward edge x-y with a capacity equal to the difference between the capacity and the flow (this is called the residual capacity), and if the flow is positive there is a backward edge y-x with a capacity equal to the flow on x-y.
Updating the path in the way described here yields the flow shown in Figure 1a.
We are left with the following residual network where a path between the source and the sink doesn’t exist: This example suggests the following algorithm: start with no flow everywhere and increase the total flow in the network while there is an augmenting path from the source to the sink with no full forward edges or empty backward edges - a path in the residual network.
As a side note, the algorithm isn’t guaranteed to even terminate if the capacities are irrationals. It is obvious that in a network in which a maximum flow has been found there is no augmenting path, otherwise we would be able to increase the maximum value of the flow, contradicting our initial assumption.
Rephrasing the statement in terms of graph theory, we are given a network - a directed graph, in which every edge has a certain capacity c associated with it, a starting vertex (the source, X in the example above), and an ending vertex (the sink).
We are asked to associate another value f satisfying f â‰¤ c for each edge such that for every vertex other than the source and the sink, the sum of the values associated to the edges that enter it must equal the sum of the values associated to the edges that leave it. Furthermore, we are asked to maximize the sum of the values associated to the arcs leaving the source, which is the total flow in the network.
The path capacity of a path is the minimum capacity of an edge along that path.
Let’s take the following example: By considering the path X_A_C_Y, we can increase the flow by 1 – the edges X_A and A_C have capacity of 3, as in the original network, but the edge C_Y has capacity 1, and we take the minimum of these values to get the path capacity.