Add maximum flow / minimum cut algorithm
- Dominant language
- C++
- Stars
- 413
- Forks
- 67
- Avg merge
- 7h 24m
- Merged PRs (30d)
- 53
Description
## Summary
Graaf has no maximum-flow / minimum-cut algorithm. This is one of the most fundamental graph algorithm families (network capacity planning, bipartite matching, image segmentation, project selection) and is a standard offering in comparable libraries such as the Boost Graph Library.
## Current state
`include/graaflib/algorithm/` has no `max_flow` (or `flow`) subdirectory. A search across the codebase for "max_flow", "maxflow", "min_cut", or "mincut" returns no results.
There is a related historical request, [#83 "[ALGO] Edmonds-Karp Algorithm for Maximum Flow"](../issues/83), which was closed without being implemented (closed due to inactivity, not as "won't do").
## Why this matters
Max flow / min cut underlies a large number of practical applications built on graphs: network capacity/bandwidth planning, bipartite matching (job assignment, resource allocation), image segmentation, and feasibility/scheduling problems expressed as flow networks. A general-purpose graph library that omits this entirely is missing one of the algorithms most likely to be the actual reason someone reaches for a graph library in the first place, and it's a conspicuous gap relative to Boost Graph Library, which Graaf positions itself against in its own README.
## Suggested resolution
- Implement Edmonds-Karp (BFS-augmenting-path Ford-Fulkerson) as a baseline, since it has a well-understood, easy-to-verify complexity bound (`O(V * E^2)`) and reuses the existing BFS traversal infrastructure.
- Expose the min-cut as a natural by-product of the max-flow computation (the set of edges crossing the final residual-graph partition).
- Follow the existing `algorithm//.h` + `.tpp` structure and add corresponding docs under `docs/docs/algorithms/`, including complexity.
- Consider a follow-up with a faster algorithm (e.g. Dinic's) once Edmonds-Karp establishes the API shape.
## Acceptance criteria
- [ ] A max-flow algorithm (e.g. Edmonds-Karp) is implemented under `include/graaflib/algorithm/max_flow/`.
- [ ] The min cut is derivable from the result.
- [ ] Documentation page added under `docs/docs/algorithms/`, including time/space complexity.
- [ ] Unit tests cover directed weighted graphs, including graphs with no feasible flow increase (zero-flow case) and disconnected source/sink.
Contributor guide
Research direction
The issue specifies implementing a max-flow/min-cut algorithm like Edmonds-Karp. Start by examining the existing algorithm directory structure at `include/graaflib/algorithm/` and the BFS traversal infrastructure. The new code should follow the `algorithm//.h` + `.tpp` pattern. Look at existing algorithm implementations for API shape and testing patterns. The work involves designing the algorithm, implementing it, adding documentation under `docs/docs/algorithms/`, and writing unit tests for directed weighted graphs.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 25/100