feat: Add Dinic's Algorithm for Maximum Flow
Describe your change:
- [x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Add or change doctests? -- Note: Please avoid changing both code and tests in a single pull request.
- [ ] Documentation change?
Checklist:
- [x] I have read CONTRIBUTING.md.
- [x] This pull request is all my own work -- I have not plagiarized.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Python files are placed inside an existing directory.
- [x] All filenames are in all lowercase characters with no spaces or dashes.
- [x] All functions and variable names follow Python naming conventions.
- [x] All function parameters and return values are annotated with Python type hints.
- [x] All functions have doctests that pass the automated testing.
- [x] All new algorithms include at least one URL that points to Wikipedia or another similar explanation.
- [x] If this pull request resolves one or more open issues then the description above includes the issue number(s) with a closing keyword: "Fixes #ISSUE-NUMBER".
Great implementation of Dinic's Algorithm for Maximum Flow! The algorithm is correctly implemented and the comments explain the approach well.
Feedback:
- The algorithm correctly uses BFS to build level graphs and DFS to find blocking flows
- Time complexity O(V^2 * E) is optimal for dense graphs
- Code structure is clean and follows the project conventions
Minor suggestions:
- Consider adding more detailed docstrings with parameter descriptions
- Add type hints for better code clarity
- Include complexity analysis in the docstring
Overall, this is a solid contribution that adds value to the algorithms collection.
Thanks again for the review!
I've just pushed the updates based on your feedback:
- Added detailed
ArgsandReturnssections to docstrings. - Updated type hints to be more specific (e.g.,
list[int]). - Added time complexity analysis to the
max_flowdocstring.
Please let me know if there's anything else needed! 🚀
Friendly Follow-up / Request for Review
Hi maintainers, I am very sorry to bother you as I know everyone has a busy schedule.
I am a university student currently taking an Open Source Development course. For our final project, we are required to contribute to an open-source community and have at least one PR merged. This is my very first contribution to the open-source world, and I’ve learned a lot during the process. I definitely plan to stay involved in the future!
As my final course report draft is due this coming Tuesday, I am kindly checking if anyone might have a moment to take a look at this PR? All automated checks have passed, and I have addressed the previous feedback from the bot.
I apologize again for the rush and any inconvenience caused. Thank you so much for your time and for maintaining this amazing project! 🙏
Impressive implementation of Dinic's Algorithm! The code effectively handles the construction of the level graph and the blocking flow computation. The documentation is thorough, and the time complexity analysis is clear. A great addition to the networking flow module. Approved!
Thank you so much for the approval! I really appreciate you taking the time to review the implementation. Your feedback means a lot to me. Thanks again for your thorough review!