mayorx/hungarian-algorithm

(Kuhn-Munkres) numpy implementation, rectangular matrix is supported (|X| <= |Y|). 100x100000 in 0.153 s.

hungarian algorithm

Description

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

Example

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()

Performance

(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

Reference

topcoder c++ implementation

hungarian-algorithm's Issues

Doesn't work

kbriggs@Z230-work:~/Downloads/hungarian-algorithm-master> python3 demo.py 
Traceback (most recent call last):
  File "demo.py", line 24, in <module>
    matcher = KMMatcher([
  File "/home/kbriggs/Downloads/hungarian-algorithm-master/km_matcher.py", line 21, in __init__
    self.xy = -np.ones((self.n,), dtype=np.int)
  File "/home/kbriggs/.local/lib/python3.8/site-packages/numpy/__init__.py", line 305, in __getattr__
    raise AttributeError(__former_attrs__[attr])
AttributeError: module 'numpy' has no attribute 'int'.
`np.int` was a deprecated alias for the builtin `int`. To avoid this error in existing code, use `int` by itself. Doing this will not modify any behavior and is safe. When replacing `np.int`, you may wish to use e.g. `np.int64` or `np.int32` to specify the precision. If you wish to review your current use, check the release note link for additional information.
The aliases was originally deprecated in NumPy 1.20; for more details and guidance see the original release note at:
    https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations

bad English

time consuming of size

makes no sense. Should it be maybe

time consumed for size

?