mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 21:45:27 +08:00
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
46 lines
2.9 KiB
Markdown
46 lines
2.9 KiB
Markdown
# 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](https://en.wikipedia.org/wiki/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`](ford_fulkerson.py) | The [Ford-Fulkerson](https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm) method, finding augmenting paths with a breadth-first search (the [Edmonds-Karp](https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm) refinement). Uses an adjacency-matrix representation. Runs in `O(V * E^2)`. |
|
|
| [`minimum_cut.py`](minimum_cut.py) | Finds the edges of a [minimum s-t cut](https://en.wikipedia.org/wiki/Minimum_cut) from the residual graph left behind by Ford-Fulkerson, illustrating the max-flow min-cut theorem. |
|
|
| [`dinic.py`](dinic.py) | [Dinic's algorithm](https://en.wikipedia.org/wiki/Dinic%27s_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`](push_relabel.py) | The [push-relabel](https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm) (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.
|