Does relabeling change an edge's capacity?

No. It changes a vertex's height label.

Can excess return to the source?

Yes, through residual edges that undo part of an earlier assignment.

Does the method directly solve multiple commodities sharing capacity?

No. That is a different modeling problem from the single-commodity maximum-flow task described here.

AI Glossary / Graphs and symbolic AI / Advanced

Preflow-Push

Definition

Preflow-push, also called push-relabel, is an algorithmic approach for finding a maximum flow from a source to a sink in a capacitated network. It temporarily permits excess flow at intermediate vertices, then moves that excess using residual edges and height labels. NetworkX provides a highest-label implementation named preflow_push.

What it means

A feasible flow balances incoming and outgoing flow at every intermediate vertex. A preflow relaxes that balance: an intermediate vertex may temporarily receive more than it sends onward, while capacity restrictions remain respected. The extra amount is its excess. The algorithm works locally to move excess toward the sink or return unusable excess toward the source. This temporary imbalance is part of a mathematical search procedure, not an instruction to overload a real facility.

How it works

In a standard generic initialization, set the source's height to the number of vertices, set other heights to zero and saturate the source's outgoing edges. An intermediate vertex with positive excess is active. A push transfers the smaller of its excess and the available residual capacity along an admissible edge, where the receiving vertex's height is one less.
If an active vertex cannot push, relabel it to one plus the minimum height among its residual out-neighbors. Reverse residual edges allow earlier flow assignments to be undone. The generic procedure continues until intermediate excess is cleared. Height-label invariants support the maximum-flow guarantee. Implementations can use different active-vertex selection rules and relabeling heuristics; the highest-label variant gives priority to active vertices with the greatest height.

Three practical examples

A capacity-planning model represents transfer links by maximum throughput. A maximum-flow calculation identifies how much a single modeled commodity can move from an origin to a destination.
A bipartite assignment problem can be transformed into a flow network with appropriate capacities. A flow algorithm then helps compute a maximum-cardinality assignment under the encoded compatibility rules.
A graph-cut formulation of a labeling problem uses a maximum-flow/minimum-cut calculation as an optimization component. Whether this models the intended labeling objective depends on how the graph and capacities are constructed.

Think of it this way

Imagine a planner tentatively allocating more work to an intermediate station than the next station can accept. The planner must pass some allocation onward and retract the remainder. Height labels guide these adjustments. The analogy concerns revising a plan; the algorithm's temporary excess is not a claim that physical work has already been completed or transported.

Worked example

Take three vertices: source S, intermediate vertex A and sink T. The only original directed edges are S to A with capacity 5 and A to T with capacity 3.
Follow the generic initialization described above. Set heights h(S) = 3, h(A) = 0 and h(T) = 0. Saturating S-to-A assigns it flow 5, leaving A with excess 5. A-to-T still carries zero. This is a preflow, not a feasible flow, because A has unequal inflow and outflow.
A initially has no admissible outgoing residual edge: T has the same height, while S has height 3. Relabel A to 1, one above the minimum neighboring residual height of 0. It can now push min(5, 3) = 3 units to T. A's excess falls to 2, and A-to-T is saturated.
The only remaining residual route out of A is the reverse edge to S, with residual capacity 5. Relabel A to 4, one above S's height of 3. Push its remaining 2 units back to S. This reduces the original S-to-A flow from 5 to 3; it does not add a new original transport link.
The final original-edge flows are 3 on S-to-A and 3 on A-to-T. A's excess is zero, and the sink receives 3. The cut separating {S, A} from {T} has capacity 3, so no feasible flow can exceed 3. The constructed flow reaches that bound and is therefore maximum.
This is a trace of the generic method for explanation, not a claimed step-by-step trace of NetworkX's implementation. Its initialization heuristics can produce different intermediate labels while solving the same flow problem.

Illustrative case study

In a fictional transfer-planning exercise, a team sees the source's initial allocation of 5 and reports a throughput of 5. Checking the example reveals that only 3 can reach the destination; the other 2 must be withdrawn from the intermediate allocation.
The team changes its reporting to use the completed solution's flow value and checks conservation at intermediate vertices. It then considers increasing S-to-A's capacity from 5 to 8. The maximum flow remains 3 because A-to-T is unchanged. Increasing A-to-T to 4 instead, with the original upstream capacity 5, raises the maximum to 4.

Common misconceptions and mistakes

A preflow is not necessarily a feasible flow, and the total initially sent from the source is not automatically the final throughput. Reverse residual edges represent the ability to revise assignments; they need not correspond to original physical links.
Maximum flow also differs from minimum-cost flow. Capacities alone do not encode prices, travel times or service priorities. In NetworkX, an omitted capacity attribute is treated as infinite, not zero. Another integration mistake is expecting preflow_push to return an ordinary flow dictionary: it returns a residual network, with the value stored in its flow_value graph attribute.

Business use

Preflow-push is useful when the operational question can be modeled as maximum single-commodity throughput. Confirm edge directions, capacity units and source/sink definitions. Validate the final flow against capacities and conservation, and use a matching cut bound to explain bottlenecks where appropriate. If calling NetworkX with value_only set to true, recognize that the maximum preflow is sufficient to obtain the value but should not automatically be treated as a completed feasible routing. Measure implementation performance on representative graphs rather than assuming one flow algorithm is always fastest.

Check your understanding

Why is the initial value 5 not the final maximum flow?

Answer: The sink's incoming edge can carry only 3.

What does the reverse push accomplish?

Answer: It reduces S-to-A's assigned flow by 2 and clears A's excess.

What proves the final flow is maximum?

Answer: Its value 3 equals the capacity of the stated cut.

Related terms

Maximum Flow
preflow
residual network
excess
push-relabel
height label
capacity
minimum cut
flow conservation

Learn next

Repeat the generic trace after changing A-to-T's capacity to 4. Then explain why increasing only S-to-A cannot improve throughput while the downstream capacity remains 3.

Sources

NetworkX, preflow_push: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.preflow_push.html Norbert Zeh, Algorithms II, The Generic Preflow-Push Algorithm: https://web.cs.dal.ca/~nzeh/Teaching/4113/book/maxflow/preflow_push/generic/algorithm.html

Previous: Prefix language modeling Next: Prefrontal cortex basal ganglia working memory