bobluppes / bobluppes/graaf

Add maximum flow / minimum cut algorithm

Ouverte
#331 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub
enhancement good first issue help wanted
Langage dominant
C++
Étoiles
413
Forks
67
Merge moyen
7 h 24 min
PR mergées (30 j)
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.

Guide de contribution

Ouvrir le guide de contribution

Piste de recherche

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.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Évaluation

Stack technique
cpp
Type d'issue
Fonctionnalité
Difficulté
5/5
Temps estimé
Plus d'une semaine
Activité
Active
Clarté
Clairement spécifiée
Accessibilité débutants
25/100

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.