Python icon indicating copy to clipboard operation
Python copied to clipboard

Add Hopcroft-Karp algorithm and doctests for manual_accuracy function

Open G26karthik opened this issue 2 months ago • 1 comments

Contributes to #9943

Description

This PR includes two contributions:

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

  2. Test Coverage Improvement: Adds comprehensive doctests to the manual_accuracy() function in machine_learning/scoring_functions.py.

Changes

New Algorithm

  • Added graphs/hopcroft_karp.py with 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

G26karthik avatar Oct 05 '25 16:10 G26karthik

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

Tarannum9623 avatar Oct 06 '25 14:10 Tarannum9623