Python
Python copied to clipboard
Add Hopcroft-Karp algorithm and doctests for manual_accuracy function
Contributes to #9943
Description
This PR includes two contributions:
-
Hopcroft-Karp Algorithm Implementation: Adds the Hopcroft-Karp algorithm for finding maximum matching in bipartite graphs, a fundamental graph algorithm with O(E√V) time complexity.
-
Test Coverage Improvement: Adds comprehensive doctests to the
manual_accuracy()function inmachine_learning/scoring_functions.py.
Changes
New Algorithm
- Added
graphs/hopcroft_karp.pywith full implementation - Includes detailed docstring and usage examples
- Comprehensive doctests covering various graph scenarios
Enhanced Test Coverage
- Added docstring with detailed function description for
manual_accuracy() - Added 4 doctest examples covering:
- High accuracy (80% correct predictions)
- Perfect accuracy (100% correct)
- Zero accuracy (completely wrong predictions)
- Complete inverse predictions (0% accuracy)
Testing
- All doctests pass successfully for both contributions
- Hopcroft-Karp: Multiple test cases for bipartite matching
- manual_accuracy: 12 doctest lines (4 examples) all passing
- Existing tests for mae, mse, rmse, rmsle, mbd remain passing
Hi! Can you help me by telling why my build test is failing, I want to contribute search_in_a_rotated_sorted_array in search directory and my build test failed. PR: Search in rotated sorted array #13245