In push-relabel, an active vertex with excess can push flow only to a residual neighbor exactly one height lower. If no such neighbor exists, relabel the vertex: set its height to one more than the lowest height among its residual neighbors. This opens a downhill route for a later push. section 10.4
Finding a downhill route
Suppose Node 1 has excess but its residual neighbors are both at height 0. Relabel it to height 1, then it can push 10 units to Node 2. Later, Node 2 relabels to height 1 to push toward the sink; when that route is full, it relabels to height 2 to push remaining excess back to Node 1. 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.
|
The water-system analogy treats relabeling as raising a junction tank until flow has a downhill route. section 10.1
