liveBook · Manning

Flow conservation

As explained in Algorithms Every Programmer Should Know

Flow conservation is the requirement that, at each intermediate vertex, the total incoming flow equals the total outgoing flow.

Flow conservation requires each intermediate vertex to send out as much flow as it receives. Push-Relabel temporarily relaxes this rule: a vertex can hold excess flow, then push it onward or return it toward the source. When the algorithm finishes, intermediate vertices have zero excess. section 10.1 section 10.4

A temporary imbalance

In a four-node network, initialization sends 10 units from the source to node 1 and 5 to node 2. Those intermediate nodes temporarily hold excess instead of immediately balancing incoming and outgoing flow. After pushes and relabels, both end with zero excess, and 15 units reach the sink. section 10.1 section 10.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines the balance condition and contrasts it with preflow, but does not develop a formal proof.
Examples
Traces source saturation and temporary excess through a four-node network until intermediate vertices balance.
What you can do after
Understand how Push-Relabel permits temporary imbalance while still draining excess from intermediate vertices at termination.
How it connects
Connects flow conservation to preflow, excess flow, and maximum flow.

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.