* Add Hopcroft-Karp algorithm for maximum bipartite matching
* refactor(graphs): address Copilot and keeper reviews with private sentinel, iterative DFS, and tests
* Fixed
* Added TSP
* Fixes 12192
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* updating DIRECTORY.md
* Rename travelling_salesman_problem.py to graphs/travelling_salesman_problem.py
* updating DIRECTORY.md
* Fix typo in TSP validation comments
* Fix expected output for TSP function test case
Updated expected output for travelling_salesman_brute_force function.
* Fix error messages in TSP validation functions
* Modify doctest to ignore exception details
Updated doctest to ignore exception details for invalid graph input.
* Fix doctest formatting for validate_graph function
Updated doctest format for invalid graph validation.
* Update doctests in validate_graph function
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: cclauss <cclauss@users.noreply.github.com>
* fix: correct PageRank init, dangling-node handling, and convergence (#14885)
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Apply suggestion from @cclauss
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
* fix: sub-interval midpoint formula in ternary search
* fix(maths): resolve NameError on self-referential class type annotations in matrix_exponentiation.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* fix(maths): remove unnecessary future annotations import
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Fix typos in Johnson's algorithm (nd -> and) to pass codespell
* Rename type aliases and h parameter to follow snake_case and descriptive naming
* Potential fix for pull request finding
Co-authored-by: Copilot Autofix powered by AI <175728472+Copilot@users.noreply.github.com>
---------
Co-authored-by: John Law <johnlaw.po@gmail.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: Copilot Autofix powered by AI <175728472+Copilot@users.noreply.github.com>
* pre-commit autoupdate 2025-09-11
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Fixes#12857 Use collections.deque as queue in graphs BFS shortest path 2
* Use collections.deque as queue in the correct syntax: queue = deque([start])
* Fix CI error due to HTTP 404 on https://finance.yahoo.com/quote/GOOG/\?p\=GOOG
* Undo change in workflows/build.yml as it's fixed in PR 12864
---------
Co-authored-by: Maxim Smolskiy <mithridatus@mail.ru>
* Fix `RuntimeError` in bipartite-check DFS/BFS and clean up doctests
* Iteration over `graph` mutated by `defaultdict` neighbours caused
`RuntimeError: dictionary changed size during iteration`.
– Iterate over `list(graph)` in both DFS and BFS helpers.
* Corrected `if __name__ == "__main__":` typo.
* Updated two doctests that now succeed after the fix.
All doctests now pass (`30/30`), eliminating a critical runtime failure and improving reliability of the graph algorithms.
Co-Authored-By: S. M. Mohiuddin Khan Shiam <147746955+mohiuddin-khan-shiam@users.noreply.github.com>
* Update check_bipatrite.py
* Update check_bipatrite.py
* Update check_bipatrite.py
* Update check_bipatrite.py
* Update check_bipatrite.py
* Update check_bipatrite.py
* Update check_bipatrite.py
* Update check_bipatrite.py
* Update check_bipatrite.py
---------
Co-authored-by: Odio Marcelino <odiomarcelino@gmail.com>
Co-authored-by: Maxim Smolskiy <mithridatus@mail.ru>
* Add bidirectional search algorithm implementation
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix style and linting issues in bidirectional search
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Add doctest for main function
* Add doctest for main function
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* fixed deprications
* fixed deprications
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* removed unused import
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update bidirectional_search.py
* Update bidirectional_search.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update bidirectional_search.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Maxim Smolskiy <mithridatus@mail.ru>
- Utilized `lanczos_iteration` to construct tridiagonal matrices, optimized for large, sparse matrices.
- Added `multiply_matrix_vector` for efficient matrix-vector multiplication using adjacency lists.
- Included `validate_adjacency_list` for input validation.
- Supports varied graph analysis applications, particularly for analyzing graph centrality.
- Included type hints, comprehensive docstrings, and doctests.
- PEP-8 compliant, with optimized handling of inputs and outputs.
This module provides essential tools for eigenvalue-based graph analysis, ideal for centrality insights and structural assessments.
* #9943 : Adding coverage test for basic_graphs.py
* #9943 : Adding coverage test for basic_graphs.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Solve problem of line too long
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Improve comments, add doctests for kahns_algorithm_topo.py
* Improve function docstring
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Rename variables, remove print
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* updating DIRECTORY.md
* Fix some SIM114 per file ignores
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix review issue
---------
Co-authored-by: MaximSmolskiy <MaximSmolskiy@users.noreply.github.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Enable ruff E741 rule
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Enable ruff SIM102 rule
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Enable ruff PLR5501 rule
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Use compiled black as the pre-commit formatter
* ruff-format
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Keep GitHub Actions up to date with Dependabot
---------
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* add ant_colonyant_colony_optimization_algorithms.py
* Modify details
* Modify type annotation
* Add tests for KeyError, IndexError, StopIteration, etc.
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* sync
* fixes#8098
* deleted: graphs/check_bipartite_graph_all.py
new file: graphs/check_bipatrite,py
* renamed: graphs/check_bipatrite,py -> graphs/check_bipatrite.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Add the new tests
---------
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* [ADD] tests for check_bipartite_graph_bfs
* linter fix?
* linter fix
* [ADD] more test cases check_bipartite_graph_bfs
* doctest fixes. Forgot to add 'Traceback...'
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* missed a Traceback
* Update check_bipartite_graph_bfs.py
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
* Adds Doc test in depth_first_search_2.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fixes depth_first_search_2.py formatting
* Cleanup
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Tianyi Zheng <tianyizheng02@gmail.com>
* test: adding more tests to a star algorithm
* Apply suggestions from code review
* Update a_star.py
---------
Co-authored-by: Tianyi Zheng <tianyizheng02@gmail.com>
* Added algorithm to deeply clone a graph
* Fixed file name and removed a function call
* Removed nested function and fixed class parameter types
* Fixed doctests
* bug fix
* Added class decorator
* Updated doctests and fixed precommit errors
* Cleaned up code
* Simplified doctest
* Added doctests
* Code simplification
* Create dijkstra_algorithm.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update dijkstra_algorithm.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update dijkstra_algorithm.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update dijkstra_algorithm.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Delete greedy_methods/dijkstra_algorithm.py
* Update check_bipartite_graph_dfs.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update check_bipartite_graph_dfs.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update graphs/check_bipartite_graph_dfs.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Update graphs/check_bipartite_graph_dfs.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Update check_bipartite_graph_dfs.py
* Update check_bipartite_graph_dfs.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update check_bipartite_graph_dfs.py
* Update check_bipartite_graph_dfs.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update check_bipartite_graph_dfs.py
* Update check_bipartite_graph_dfs.py
* Update check_bipartite_graph_dfs.py
* Let's use self-documenting variable names
This is complex code so let's use self-documenting function and variable names to help readers to understand.
We should not shorten names to simplify the code formatting but use understandable name and leave to code formatting to psf/black.
I am not sure if `nbor` was supposed to be `neighbour`. ;-)
* Update check_bipartite_graph_dfs.py
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Jubayer Ahmed Sojib