Networking Flow

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

What's in this directory

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.

Which one should I use?

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.py and minimum_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.py tends 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.