liveBook · Manning

Push operation

As explained in Algorithms Every Programmer Should Know

A flow push sends excess flow to a neighboring vertex with residual capacity whose height is exactly one unit lower.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through eligibility, flow and excess updates, relabeling when blocked, and a four-vertex trace.
Examples
Traces excess through a four-vertex network and shows Python routines that update forward flow, reverse flow, and excess.
What it assumes
Introduces source, sink, capacity, preflow, excess, and height through a reservoir-and-pipes analogy before the algorithm trace.
What you can do after
Build it from scratch using the Python push routine and its residual-capacity and height checks.
How it connects
Connects preflow, residual capacity, vertex heights, relabeling, and maximum flow as an alternative to augmenting-path searches.

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.