Add maximum flow / minimum cut algorithm
- Ngôn ngữ chính
- C++
- Star
- 413
- Fork
- 67
- Merge trung bình
- 7 giờ 24 phút
- Pull request đã merge (30 ngày)
- 53
Mô tả
## 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.
Hướng dẫn đóng góp
Hướng nghiên cứu
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.
Do mô hình lập chỉ mục viết ra từ nội dung của issue.
Đánh giá
- Công nghệ
- cpp
- Loại issue
- Tính năng
- Độ khó
- 5/5
- Thời gian dự kiến
- Hơn một tuần
- Mức độ hoạt động
- Sôi nổi
- Độ rõ ràng
- Đặc tả rõ ràng
- Mức phù hợp với người mới
- 25/100