liveBook · Manning

Preflow

As explained in Algorithms Every Programmer Should Know

A preflow is a flow assignment that respects edge capacities and flow conservation at intermediate vertices may be temporarily violated by allowing excess flow.

A preflow respects edge capacities but temporarily allows intermediate vertices to hold more incoming flow than they send onward. This lets a maximum-flow algorithm move capacity through local operations instead of first finding a complete source-to-sink path. section 10.1 section 10.4

Push-relabel initializes a preflow by saturating edges leaving the source. Vertices with excess push it along residual edges toward lower heights; when no such push is possible, relabeling raises a vertex's height. The process ends when intermediate excess has drained to the sink or returned to the source. section 10.1 section 10.4

A small network

In a four-node network, the source initially sends 10 units to one intermediate node and 5 to another. After pushes and relabels, all intermediate excess clears and the sink receives 15 units. section 10.1

Table 10.1 Comparison of algorithm with a water system network
Algorithm concept
Water system equivalent
What its doing
Source(s)/sink(t)
Reservoir/Drainage point
Where water enters and where it should end up
Edge capacity
Pipe diameter
The most water per unit time that connection can carry
Preflow
Flooding every pipe outgoing from the reservoir
Get water moving into the network without waiting to plan the full route first
Excess at a node
Water pooling at a junction tank
A tank can hold more water than it drains, it doesn't have to balance the in and out right away.
Height
Each tank’s elevation
Water or flow only moves from higher elevation to strictly lower one
Relabel
Raising a tank’s elevation
When every neighbor is lower or at the same elevation, there is nowhere downhill to push, so the current tank or node is ‘raised’ to a higher elevation just enough to open the downhill path.

Use the water-system comparison to relate preflow to flooding pipes before planning a complete route, and excess to water pooling at junctions. section 10.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines temporary excess and traces initialization, pushes, relabeling, and termination, including complexity.
Examples
Uses a municipal water-network analogy and a four-node capacity network that reaches flow 15.
What you can do after
Apply it via the push-relabel algorithm to compute maximum flow without global augmenting-path searches.
How it connects
Connects maximum flow to push-relabel, residual capacity, vertex heights, and augmenting-path methods.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.