liveBook · Manning

Maximum flow

As explained in The Coder Cafe

The maximum flow problem asks for the greatest feasible flow from a source to a sink without exceeding edge capacities.

Maximum flow is the greatest amount that can travel through a flow network from a source to a sink without exceeding any edge’s capacity. A vertex is a point where flow enters or exits; a directed edge carries flow and has a capacity limit. The source is where flow starts, and the sink is where it is collected. section 1.4.2

A path is not always usable

Suppose A is the source and D is the sink. A → B → D is an augmenting path if both edges have capacity left. A → C → D may be a valid path but cannot carry more flow if C → D is already full. section 1.4.2

Ford–Fulkerson repeatedly finds an augmenting path: a source-to-sink path whose edges can all carry additional flow. It adds the path’s bottleneck amount to the total, reduces the available capacity on its forward edges, and increases capacity on backward edges. Those backward edges allow later paths to redistribute flow and correct a suboptimal earlier choice. The process stops when no augmenting path remains. section 1.4.2 section 1.5

def ford_fulkerson(graph, source, sink):
    res = 0
    while True:
        path = get_next_augmenting_path(graph, source, sink)
        if path is None:
            break
        
        bottleneck = get_bottleneck(path)
        for edge in path.get_edges():
            edge.capacity -= bottleneck
            backward_edge = get_backward_edge(graph, edge)
            backward_edge.capacity += bottleneck
        
        res += bottleneck
    
    return res

The pseudocode shows the repeated path search, bottleneck update, backward-edge adjustment, and returned flow total. section 1.4.2

The same question arises in pipelines with limited pipe capacity, data networks with limited bandwidth, and road networks with limited route capacity: how much can reach the destination through the network as a whole? section 1.4.2

How The Coder Cafe covers it

How deep it goes
Explains terminology and iterative flow updates with pseudocode, but leaves path-finding and bottleneck helpers unspecified.
Examples
Illustrates open and blocked paths, plus pipeline, data-network, and traffic-flow scenarios.
What it assumes
Introduces flow-network terms before augmenting paths, while using graph paths and Python-like pseudocode for the algorithm.
What you can do after
Evaluate/understand it by tracing augmenting-path updates and recognizing when no further path is available.
How it connects
Connects directed graphs and capacity-constrained paths to Ford–Fulkerson, augmenting paths, bottlenecks, and backward edges.

Also explained in

Compare how 3 books explain maximum flow →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.