Commit Graph
1 Commits
Author SHA1 Message Date
priya-sundaram-dev 8e0817e829 Clean up the networking_flow directory (#15098)
* 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
2026-08-28 00:39:49 +02:00