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
