liveBook · Manning

Residual capacity

As explained in Algorithms Every Programmer Should Know

Residual capacity is the additional flow that can be sent along an edge, accounting for its capacity and current flow.

Residual capacity is the room left on a directed edge after accounting for its current flow: cf(u,v) = c(u,v) - f(u,v). section 10.1

In Push-Relabel, an active node can push toward a neighbor only when the edge has positive residual capacity and the neighbor is exactly one height lower. section 10.1

A saturated edge

The edge from the source to node 1 has capacity 10 and is saturated during initialization. Its remaining forward capacity is therefore zero. section 10.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines residual capacity as capacity minus flow and explains its role in push eligibility alongside the height condition.
Examples
Uses source edges of capacities 10 and 5, saturated during initialization, to illustrate remaining capacity.
What it assumes
Defines edge capacity and current flow before expressing residual capacity as their difference.
What you can do after
Apply residual-capacity calculations to determine whether an edge has room for a push.
How it connects
Connects edge capacity and flow to preflow and the Push-Relabel algorithm.

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.