A height function labels each vertex in a flow network. In push-relabel, flow can be pushed along a residual edge only from a vertex exactly one level higher: h(u) = h(v) + 1. If an active vertex has no eligible neighbor, relabel it to one more than the lowest height among its residual neighbors. section 10.1
A local height adjustment
If a node’s residual neighbors have height 0, relabeling it to height 1 makes a push to a height-0 neighbor admissible. In the traced network, Node 1 relabels to 1 and pushes its excess to Node 2. 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 comparison maps vertex heights to tank elevations: flow moves downhill, and relabeling raises a tank when no downhill route is available. section 10.1
