bobluppes / bobluppes/graaf

Add maximum flow / minimum cut algorithm

Aperta
#331 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub
enhancement good first issue help wanted
Lingua principale
C++
Stelle
413
Fork
67
Merge medio
7h 24m
PR unite (30g)
53

Descrizione

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

Guida per i contributori

Apri la guida per i contributori

Direzione di ricerca

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.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Valutazione

Stack tecnologico
cpp
Tipo di issue
Funzionalità
Difficoltà
5/5
Tempo stimato
Più di una settimana
Stato di attività
Attiva
Chiarezza
Specificata chiaramente
Idoneità per principianti
25/100

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.