A client required a Python implementation of a matrix permutation algorithm from a research paper — one that their own attempt had been unable to pass on several edge-case test matrices. I implemented the complete bipartite matching algorithm, including all auxiliary data structures, and validated results against MATLAB's `equilibrate` function.
Highlights
- Implemented `BipartiteMatching`, `AlternatingPathTree`, and `BipartitePath` classes to manage the core bipartite graph structures for the shortest augmenting path algorithm.
- Built logarithmic cost matrix construction for numerical stability, handling matrix values ranging from 10⁻²³ to 10¹⁴ without overflow/underflow.
- Implemented dual variable (u, v) updates per the research paper specification, with an initial heuristic matching to reduce overall runtime.
- Created a 172-test pytest suite including edge-case matrices with extreme numerical ranges, validated against MATLAB's equilibrate function output.
- Implemented matplotlib-based bipartite graph visualization and matrix sparsity plots for algorithm debugging and validation.
- Delivered within a 3-week timeline despite 17+ hours of unexpected complexity; client provided a bonus doubling the agreed contract amount.
Technology
- Python
- NumPy
- networkx
- matplotlib (graph visualization)
- pytest (172 test cases)
- Jupyter notebooks