Excess flow is the amount of incoming flow a vertex temporarily retains rather than sending onward. In push–relabel, intermediate vertices may hold positive excess while local pushes and relabels route it toward the sink or back to the source. section 10.1 section 10.4
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.
|
Picture a junction tank that temporarily holds more water than it drains: excess need not be balanced immediately. section 10.1
Excess in a four-node network
After initialization, Node 1 holds 10 units and Node 2 holds 5. Node 1 pushes 10 to Node 2, leaving Node 2 with 15 units of excess. section 10.1
