liveBook · Manning

Height function

As explained in Algorithms Every Programmer Should Know

A height function assigns labels to network vertices to determine which flow operations are admissible in the push-relabel algorithm.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines the push condition and relabel rule, then traces their operation on a four-node network.
Examples
Uses tank elevations in a water-system analogy and traces relabeling and pushes on a four-node network.
What you can do after
Understand how vertex heights direct local pushes and change when an active node lacks an eligible neighbor.
How it connects
Connects vertex heights to push-relabel, preflow, excess flow, residual graphs, and relabeling.

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.