Preflow

A preflow is a generalization of a network flow used in the study of directed graphs with a designated source and sink. Given a directed graph G = (V, E) with nonnegative edge capacities c(u, v), a preflow is a function f: E → R+ that satisfies 0 ≤ f(u, v) ≤ c(u, v) for all edges. Unlike a standard s–t flow, a preflow relaxes the conservation constraint at intermediate vertices: some vertices may accumulate excess flow.

For a vertex v ∈ V, the excess e(v) is defined as the total inflow minus the total outflow: e(v) = ∑u f(u, v) − ∑w f(v, w). In a preflow, e(v) ≥ 0 for all vertices v ≠ s, meaning intermediate nodes can hold excess, while the source s typically has negative excess equal to the net outflow, and the sink t can accumulate net inflow.

A common way to obtain and work with preflows is via the push-relabel framework. The initial preflow is produced by saturating all edges leaving the source: set f(s, v) = c(s, v) for all v. Then the algorithm repeatedly performs pushes along edges with residual capacity and respects a height (potential) function: flow can be pushed from u to v only if there is residual capacity and the height of u is greater than the height of v. If no admissible pushes exist at a vertex, its height is increased (relabel) to create new opportunities for pushing.

Preflows are central to efficient max-flow algorithms, particularly the push-relabel method. A maximum flow corresponds to a feasible preflow with no excess at any intermediate vertex, effectively turning the preflow into a standard s–t flow. Conversely, any maximum preflow can be extended to a maximum flow by routing its excess to the sink.