liveBook · Manning

Excess flow

As explained in Algorithms Every Programmer Should Know

Excess flow is the net amount of incoming flow currently retained at a vertex rather than sent onward.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines excess, then traces initialization, pushes, relabeling, and the clearing of intermediate vertices.
Examples
Traces Node 1’s 10 units joining Node 2’s initial 5 units of excess in a four-node network.
What you can do after
Understand how local pushes and relabels clear intermediate excess until flow reaches the sink or returns to the source.
How it connects
Connects preflow, residual capacity, active vertices, push–relabel, and height labels.

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.