bobluppes / bobluppes/graaf

Add maximum flow / minimum cut algorithm

オープン
#331 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る
enhancement good first issue help wanted
主要言語
C++
スター
413
フォーク
67
平均マージ
7時間 24分
マージ済み PR(30日)
53

説明

## 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.

コントリビューションガイド

コントリビューションガイドを開く

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

評価

技術スタック
cpp
issue の種類
機能追加
難易度
5/5
見積もり時間
1週間以上
活発さ
活発
明瞭さ
明確に書かれている
初心者へのやさしさ
25/100

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。