This directory collects algorithms for the maximum-flow problem: given a
directed graph whose edges have capacities, a source, and a sink, how
much flow can be pushed from source to sink without exceeding any edge's
capacity?
Maximum flow turns up all over the place — routing traffic through a network, matching people to jobs, scheduling, image segmentation, and any problem that can be phrased as "move as much as possible from here to there through a shared network." Its close relative, the minimum cut, finds the cheapest set of edges whose removal disconnects the sink from the source, and the max-flow min-cut theorem says the two always have the same value.
New to the topic? These are good starting points:
- https://en.wikipedia.org/wiki/Maximum_flow_problem
- https://en.wikipedia.org/wiki/Flow_network
- https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
| File | Description |
|---|---|
ford_fulkerson.py |
The Ford-Fulkerson method, finding augmenting paths with a breadth-first search (the Edmonds-Karp refinement). Uses an adjacency-matrix representation. Runs in O(V * E^2). |
minimum_cut.py |
Finds the edges of a minimum s-t cut from the residual graph left behind by Ford-Fulkerson, illustrating the max-flow min-cut theorem. |
dinic.py |
Dinic's algorithm: repeatedly build a BFS level graph and saturate a blocking flow on it. Adjacency-list based, so it handles parallel edges and sparse graphs well. Runs in O(V^2 * E), or O(E * sqrt(V)) on unit-capacity networks. |
push_relabel.py |
The push-relabel (Goldberg-Tarjan) method: instead of augmenting whole paths, it maintains a preflow and locally pushes excess towards the sink. With highest-label selection it runs in O(V^2 * sqrt(E)), and is a strong choice on dense graphs. |
All four compute the same maximum-flow value; they differ in speed and in how the graph is represented.
- Just learning the idea? Start with
ford_fulkerson.pyandminimum_cut.py— the augmenting-path picture is the most intuitive. - Sparse graph, or parallel edges? Reach for
dinic.py; the adjacency-list representation and level-graph batching make it fast in practice. - Dense graph?
push_relabel.pytends to win, because it avoids re-scanning long augmenting paths.
Each file is self-contained, fully type-hinted, and verified with doctests — run
any of them directly (for example python networking_flow/dinic.py) to execute
the tests.