How To Convert A Pre-Flow Push Network With Excess Flow To A Flow Network

Question

I implemented first phase of the highest label push relabel algorithm for maximum flow but I could not find any resources about how to implement the second phase, i.e. to convert the preflow push network to a valid flow network.

Answer 1

If you really need the max flow (it's possible to derive a min cut directly from the preflow and use it to verify the preflow), then I know of two approaches.

The first approach is covered in the original Goldberg--Tarjan paper on the push relabel algorithm. In essence, the second phase is implemented almost exactly as the first. The only difference is that the source is held at distance n (instead of the sink, at distance 0). This has the effect of routing the excesses back to the source.

I'm not sure where the second approach is described. I know that it's in Goldberg's implementation, on which the Boost Graph implementation is based (see convert_preflow_to_flow). Conceptually, there are three steps.

1. Until the preflow is acyclic, cancel a flow cycle by sending enough flow on the reverse cycle to remove one of the arcs from the flow graph.

2. Topologically sort the nodes of the flow graph from sinkmost to sourcemost.

3. For each node in topological order, eliminate its excess by decreasing the flow on incoming arcs (which effects a corresponding increase in the excess of nodes yet to be processed).

Practically speaking, Steps 1 and 2 both involve depth-first searches. Naively, one would restart the depth-first search for cycle-detection after each cycle is detected and canceled, but it's possible to rewind the depth-first search just to the point where it first used an arc that canceling removed, saving the time to get to that point in the search again. The topological order can be obtained as a byproduct of the search, saving a separate traversal for Step 2.