- a python numpy implementation of hungarian algorithm (also known as Kuhn–Munkres algorithm).
- Rectangular matrix is supported.
- 0.153 second when |X|=100 and |Y|=100,000 on my Mac.
matcher = KMMatcher([ [2., 3., 0., 3.], [0., 4., 4., 0.], [5., 6., 0., 0.], [0., 0., 7., 0.] ]) matcher.solve(verbose=True) result:
match 0 to 3, weight 3.0000 match 1 to 1, weight 4.0000 match 2 to 0, weight 5.0000 match 3 to 2, weight 7.0000 ans: 19.0000 or using default setting
weights = np.random.randn(n, m) matcher = KMMatcher(weights) best = matcher.solve() (only tested on my Mac)
N = |X| M = |Y| | N | M | time(seconds) |
|---|---|---|
| 10 | 100,000 | 0.017 |
| 10 | 1,000,000 | 0.250 |
| 100 | 10,000 | 0.026 |
| 100 | 100,000 | 0.153 |
| 100 | 1,000,000 | 2.004 |
| 1,000 | 1,000 | 1.634 |