liveBook · Manning

Relabel operation

As explained in Algorithms Every Programmer Should Know

A relabel operation raises an active vertex's height to enable a valid push along an edge with residual capacity.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines the minimum-neighbor-height rule and traces successive relabels through a small flow network.
Examples
Traces Node 1 rising to height 1 and Node 2 relabeling twice before excess returns toward the source.
What you can do after
Apply the minimum-neighbor-height rule to decide when and how to relabel an active vertex.
How it connects
Connects relabeling to push-relabel, residual capacity, active vertices, and preflow.

Related concepts

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.