on an active node which is neither the source nor the sink without any admissible out-arcs in . It modifies to be the minimum value such that an admissible out-arc is created. Note that this always increases and never creates a steep arc, which is an arc such that , and . relabel(u): assert xf[u] > 0 and 𝓁[u] <= 𝓁[v] for all v such that cf[u][v] > 0 𝓁[u] = 1 + min(𝓁[v] for all v such that cf[u][v] > 0) Effects of push and relabel After a push or relabel operation, remains a valid labeling function with respect to . For a push operation on an admissible arc , it may add an arc to , where ; it may also remove the arc from , where it effectively removes the constraint . To see that a relabel operation on node preserves the validity of , notice that this is trivially guaranteed by definition for the out-arcs of u in . For the in-arcs of in , the increased can only satisfy the constraints less tightly, not violate them. The generic push–relabel algorithm The generic push–relabel algorithm is used as a proof of concept only and does not contain implementation details on how to select an active node for the push and relabel operations. This generic version of the algorithm will terminate in . Since , , and there are no paths longer than in , in order for to satisfy the valid labeling condition must be disconnected from . At initialisation, the algorithm fulfills this requirement by creating a pre-flow that saturates all out-arcs of , after which is trivially valid for all . After initialisation, the algorithm repeatedly executes an applicable push or relabel operation until no such operations apply, at which point the pre-flow has been converted into a maximum flow. generic-push-relabel(G, c, s, t): create a pre-flow f that saturates all out-arcs of s let 𝓁[s] = |V| let 𝓁[v] = 0 for all v ∈ V \ {s} while there is an applicable push or relabel operation do execute the operation Correctness The algorithm maintains the condition that is a valid labeling during its execution. This can be proven true by examining the effects of the push and relabel operations on the label function . The relabel operation increases the label value by the associated minimum plus one which will always satisfy the