Picture water pooling at a junction tank. It can leave through a pipe only if the pipe has room and the next tank is downhill. In a flow network, a push does the same job: it moves excess flow from an active vertex to a neighbor with positive residual capacity whose height is exactly one lower. section 10.1
To push from vertex u to vertex v:
- Check that u has excess, the edge to v has residual capacity, and h(u) = h(v) + 1. section 10.1
- Send the smaller of u’s excess and the edge’s residual capacity. Increase flow toward v, update reverse flow, subtract the amount from u’s excess, and add it to v’s. section 10.1
- If no eligible neighbor exists, relabel u just high enough to create a valid downhill move. section 10.1
A push can move flow away from the sink
In a four-vertex network, one vertex starts with 10 units of excess and another with 5. After the first vertex relabels, it pushes all 10 to the second, giving that vertex 15. The second pushes 10 to the sink, then relabels and pushes its remaining 5 back to the first. The first sends those 5 directly to the sink. Both intermediate vertices finish with zero excess, and the sink receives 15 units. A push is therefore a local move, not a promise that flow will head straight to the sink. section 10.1
Listing 10.3 Core code functions for push and relabel routines
def _push(self, u, v):
"""Pushes excess flow from node u to node v."""
residual = self.capacity[u][v] - self.flow[u][v] #A
send = min(self.excess[u], residual) #B
self.flow[u][v] += send #C
self.flow[v][u] -= send #D
self.excess[u] -= send #E
self.excess[v] += send #F
def _relabel(self, u):
"""Increases the height of node u based on its residual neighbors."""
min_height = float('inf')
for v in range(self.V):
if self.capacity[u][v] - self.flow[u][v] > 0: #G
min_height = min(min_height, self.height[v])
if min_height != float('inf'):
self.height[u] = min_height + 1
The Python routines show how a push changes forward and reverse flow and both vertices’ excess, while relabel finds the lowest residual neighbor. section 10.1
Pushes work alongside relabels after an initial preflow floods edges leaving the source. Processing continues while an intermediate vertex has excess; it ends when those vertices have drained, with flow reaching the sink or returning to the source. Unlike augmenting-path methods, this uses local vertex operations rather than repeated end-to-end path searches. section 10.4
