priya-sundaram-dev
8e0817e829
* Clean up the networking_flow directory - Add networking_flow/README.md covering max-flow / min-cut, with a file-by-file table and guidance on which algorithm to use. - minimum_cut.py: add a module docstring with a Wikipedia URL, type hints, and corner-case doctests; work on a copy so the input graph is no longer mutated. - Add dinic.py: Dinic's algorithm (BFS level graph + DFS blocking flow), adjacency-list based so it handles parallel edges and sparse graphs. - Add push_relabel.py: the Goldberg-Tarjan push-relabel (preflow) method with highest-label selection. Both new algorithms are fully type-hinted, documented with a Wikipedia reference, and validated by doctests; their output was cross-checked against ford_fulkerson.py on thousands of random graphs. * Address review: drop __future__ import, use descriptive names, apply README wording
2.9 KiB
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.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.