Hi @bmc,
thanks for this package!

I noticed that the latest v1.0.9 version that was published to PyPI actually does not contain any distribution files to download:

https://pypi.python.org/pypi/munkres/1.0.9

When I do pip search munkres, 1.0.9 shows up:

munkres (1.0.9)     - munkres algorithm for the Assignment Problem

However, when I do pip install munkres only 1.0.8 gets installed, not 1.0.9.

Could you please upload the source distribution and wheel packages for 1.0.9?

Thanks

Would you mind adding the tests to the sdist, so that they can be used by distro packaging tools. Much appreciated.

c.f. https://build.opensuse.org/package/show/home:jayvdb:coala:python3-bears/python-munkres which has the tests running & passing, using a workaround, which I need to remove before submitting to the central clearinghouse.

Hello :)

I'm working on the "coala" project, that uses your munkres algorithms. Our project is a code checking tool that shall allow to check for various code rules.

One of our main features is a code-clone detection tool that uses munkres.

Coming to the problem:
We encountered a bug when using the apt-get package python3-munkres only (on Ubuntu 14.04 LTS).
The pad_matrix function behaves wrong, we let it pad with 1, but we get a matrix padded with 0. But using the pip-package there's no problem.

We use python version 3.

Steps to reproduce (at least for Ubuntu 14.04):

1. Make sure you don't have installed the pip package munkres
2. Install the apt-get package python3-munkres
3. Clone our git repository at https://github.com/coala-analyzer/coala
4. Run the tests / the fault test: ./run_tests.py -t ClangCloneDetectionBearTest

The test is located in bears/tests/codeclone_detection/ClangCloneDetectionBearTest.py.
This bug is confirmed from our other developers^^

We have already an issue open, see #586.

I am using the following "helper function" to translate one list of clustering algorithm label assignments to best match another (for improved visualization):

import munkres
from sklearn.metrics.cluster import contingency_matrix

def translateLabels(masterList, listToConvert):
    contMatrix = contingency_matrix(masterList, listToConvert)
    labelMatcher = munkres.Munkres()
    labelTranlater = labelMatcher.compute(contMatrix.max() - contMatrix)
    uniqueLabels1 = list(set(masterList))
    uniqueLabels2 = list(set(listToConvert))
    tranlatorDict = {}
    for thisPair in labelTranlater:
        tranlatorDict[uniqueLabels2[thisPair[1]]] = uniqueLabels1[thisPair[0]]
    return [tranlatorDict[label] for label in listToConvert]

Up to now I've only used this on square matrices and it always worked perfectly (thank you!).

Now I've tried it on a rectangular matrix (which is supposed to be supported via padding) but it fails during the padding stage.

  File "...1063961447.py", line 4, in <module>
    nodeDF[thisVar] = translateLabels(masterList, list(nodeDF[thisVar]))

  File "...helperFunctions.py", line 3265, in translateLabels
    labelTranlater = labelMatcher.compute(contMatrix.max() - contMatrix)

  File "...\lib\site-packages\munkres.py", line 136, in compute
    self.C = self.pad_matrix(cost_matrix)

  File "...\lib\site-packages\munkres.py", line 106, in pad_matrix
    new_row += [pad_value] * (total_rows - row_len)

ValueError: operands could not be broadcast together with shapes (132,) (210,) (132,) 

In this case, the masterList has length 342 and the listToConvert has length 132.

I don't know if this is a problem with my use case, or a bug in the code, but I don't have any reason to think it wouldn't work in this case, so I suppose it is a bug.

Aside from fixing it in the package, any advice for an immediate fix?

I want to use the Hungarian assignment algorithm in python on a non-square numpy array.

My input matrix X looks like this:

X = np.array([[0.26, 0.64, 0.16, 0.46, 0.5 , 0.63, 0.29],
              [0.49, 0.12, 0.61, 0.28, 0.74, 0.54, 0.25],
              [0.22, 0.44, 0.25, 0.76, 0.28, 0.49, 0.89],
              [0.56, 0.13, 0.45, 0.6 , 0.53, 0.56, 0.05],
              [0.66, 0.24, 0.61, 0.21, 0.47, 0.31, 0.35],
              [0.4 , 0.85, 0.45, 0.14, 0.26, 0.29, 0.24]])

The desired result is the matrix ordered such as X becomes X_desired_output:

X_desired_output = np.array([[0.63, 0.5 , 0.29, 0.46, 0.26, 0.64, 0.16], 
                             [0.54, 0.74, 0.25, 0.28, 0.49, 0.12, 0.61], 
                             [[0.49, 0.28, 0.89, 0.76, 0.22, 0.44, 0.25], 
                             [[0.56, 0.53, 0.05, 0.6 , 0.56, 0.13, 0.45], 
                             [[0.31, 0.47, 0.35, 0.21, 0.66, 0.24, 0.61], 
                             [[0.29, 0.26, 0.24, 0.14, 0.4 , 0.85, 0.45]])

Here I would like to maximize the cost and not minimize so the input to the algorithm would be in theory either 1-X or simply X.

Using your implementation:

import munkres

m = Munkres()
indices = m.compute(-X)

indices
[(0, 5), (1, 4), (2, 6), (3, 3), (4, 0), (5, 1)]

# getting the indices in list format
ii = [i for (i,j) in indexes]
jj = [j for (i,j) in indexes]

How can I use these to sort X ? jjonly contain 6 elements as opposed to the original 7 columns of X.

I am looking to actually get the matrix sorted.

Right now Python support is only checked for using custom code in setup.py (the if sys.version_info[0:2] < (3, 5): clause). This causes some issues with downstream users as Python 2.7 and 3.5 were dropped with 1.1.x and just asking for "munkres" will install the latest (1.1.2) instead of the latest for the supported Python version (1.1.2 or 1.0.12).

https://packaging.python.org/guides/dropping-older-python-versions/ documents best practices for dropping support for given Python versions. It's too late for the drop of Python 2.7 and 3.5 but should be implemented before Python 3.6 gets dropped.

Hello,

I wanted to use this package to solve an assignment problem. The catch is that I have some particular combinations of assignments which should be forbidden or censored.

For example, say we have matrix:

[ [1 3 5 1]
  [7 5 2 3]
  [3 8 2 3] ]

... but we "know" that we cannot assign row 0 to columns 0 and 3. Replacing the forbidden assignmens by nan values the matrix would be something like:

[ [NaN 3 5 NaN]
  [7 5 2 3]
  [3 8 2 3] ]

How can this be done? I have tried setting the forbidden elements to nan but sometimes I get an infinite loop inside the compute method ...

Setting the forbidden elements to very large values would also not work because I could still get a forbidden assignment if there is no alternative ...

Thanks in advance,

Miguel

When I enter cost values in floating point form inside cost matrix, print_matrix function treats those values as integer and print only integral part of the values. I run this code:

from munkres import Munkres, print_matrix

matrix = [[5.1, 9.6, 1.7],
          [10.2, 3.5, 2.8],
          [8.3, 7.4, 4.9]]
m = Munkres()
indexes = m.compute(matrix)
print_matrix(matrix, msg='Lowest cost through this matrix:')
total = 0
for row, column in indexes:
    value = matrix[row][column]
    total += value
    print(f'({row}, {column}) -> {value}')
print(f'total cost: {total}')

Output is as follows:

Lowest cost through this matrix:
[   5,    9,    1]
[  10,    3,    2]
[   8,    7,    4]
(0, 0) -> 5.1
(1, 1) -> 3.5
(2, 2) -> 4.9
total cost: 13.5

See matrix printed by print_matrix function isn't same matrix as given in code that's it only has integral part with them, although total cost calculation is correct. Is it a expected behavior of print_matrix function? Because it's not always the case, cost matrix would have all value in integral form.

Hi,

I'm facing a discrepancy between np.ndarray and python list. here's a reproducible code.

(Pdb) munkres_inst.compute(cost_matrix)
*** ValueError: non-broadcastable output operand with shape (1,) doesn't match the broadcast shape (2,)
(Pdb) cost_matrix
array([[1.20000000e+20],
       [1.20000000e+20],
       [4.51233041e-01]])
(Pdb) munkres_inst.compute(cost_matrix.tolist())
[(2, 0)]
(Pdb) cost_matrix.tolist()
[[1.2e+20], [1.2e+20], [0.45123304109052526]]

Could you please let me know if this is a mistake on my end or a bug with the library? Thanks!

Regards,

these lines https://github.com/bmc/munkres/blob/master/munkres.py#L463-L465 read:

if self.marked[i][j] == 1:
    self.col_covered[j] = True
    count += 1

but in the tutorial that this was based on, the count is based on the total number of covered columns:

for i in 1..n loop 
  for j in 1..n loop 
    if M(i,j)=1 then 
      C_cov(j):=1; 
    end if; 
  end loop; 
end loop; 
count:=0; 
for j in 1..n loop 
  count:=count + C_cov(j); 
end loop; 

to fix this, i suggest adding a condition and not self.col_covered[j] like this:

if self.marked[i][j] == 1 and not self.col_covered[j]:
    self.col_covered[j] = True
    count += 1

Mypy does not recognize munkres as a typed module due to lack of py.typed marker (empty file named py.typed at package root).

Error:

Skipping analyzing "munkres": module is installed, but missing library stubs or py.typed marker Mypyimport-untyped
See https://mypy.readthedocs.io/en/stable/running_mypy.html#missing-imports Mypynote

However, munkres is distributed as a single-file top-level Python module (munkres.py directly in site-packages).

This PR has discussion of this (apparently unsupported) use case: python/typing#1333

The suggestion currently seems to be to start using a directory and add the marker.

Hi! I am maintaining a JS port of this package, and while I check this repo from time to time for changes that could be applied downstream, it would be helpful if you’d consider doing most of the changes here through a quick pull request (that can be merged instantly) so that the watchers of this repo can get notifications on changes.

It looks like the HTML page described in the documentation (http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html) has been taken down.

Hello.

First, let me write down some thanks. This is a nice, straight forward implementation. This is my first time dipping my toes into the water on linear programming and optimisation, so appreciate how accessible this is to set up and use.

That said, I am finding inconsistent behaviour. I am using the sample code from the project website (https://software.clapper.org/munkres/index.html).

Take these two example matrices. The only value I am changing is in position (1,2).

matrix = [
[10.01,     10.02,  8.03,       11.04],
[9.05,      8.06,   5000.07,     1.08],
[9.09,      7.11,   4.11,       1000.12]
]

Returns (expected)
(0,0) -> 10.01
(1,2) -> 5000.07
(2,3) -> 1000.12

matrix = [
[10.01,     10.02,  8.03,       11.04],
[9.05,      8.06,   500.07,     1.08],
[9.09,      7.11,   4.11,       1000.12]
]

Returns (unexpected):
(0,0) -> 10.01
(1,1) -> 8.06
(2,3) -> 1000.12

Why does the second matrix not return 10.01, 500.07, 1000.12?

I can see this issue at scale if I use a large sample size.

matrix = [
[0.233333333,	0.033333333,	0.013888889,	0.015384615,	0.032258065,	0.022222222,	0.033333333,	0.023255814,	0.01754386,	0.027027027],
[0.041666667,	0.035714286,	0.013888889,	0.015384615,	0.032258065,	0.022222222,	0.035714286,	0.023255814,	0.01754386,	0.027027027],
[0.021276596,	0.021276596,	0.013888889,	0.246153846,	0.212765957,	0.744680851,	0.021276596,	0.085106383,	0.105263158,	0.106382979],
[0.041666667,	0.035714286,	0.013888889,	0.030769231,	0.032258065,	0.2,	        0.428571429,	0.209302326,	0.01754386,	0.108108108],
[0.02173913,	0.02173913,	0.013888889,	0.030769231,	0.02173913,	0.043478261,	0.043478261,	0.760869565,	0.140350877,	0.043478261]
]

This simply default to returning locations (0,0), (1,1), (2,2), (3,3), (4,4). This is what I see when running my much larger sample, everything just incrementing through the matrix until the end.

To experiment, I ran the same larger data set but modified to multiple all values by 10,000 and round to nearest integer. That worked and didn't return the (0,0),(1,1), (2,2) result. Hence why I think it may be something to do with floats.

Hopefully not missing something silly at my end.

Thanks
Lummers

from munkres import Munkres, print_matrix
import sys

m = Munkres()

matrix = [
[10.01, 10.02,  8.03, 11.04],
[9.05,  8.06,  500.07, 1.08],
[9.09,  7.11,  4.11, 10.12]
]

cost_matrix = []

for row in matrix:
    cost_row = []
    for col in row:
        cost_row += [sys.maxsize - col]
    cost_matrix += [cost_row]

m = Munkres()


indexes = m.compute(cost_matrix)
# print_matrix(matrix, msg="hello")
total = 0

for row, column in indexes:
    value = matrix[row][column]
    total += value
    print(f'({row},{column}) -> {value}')

Here is my version info:

import sys
import munkres
print (munkres.__version__)
print(sys.version)
print(sys.version_info)

1.1.4
3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 23:11:46) [MSC v.1916 64 bit (AMD64)]
sys.version_info(major=3, minor=8, micro=1, releaselevel='final', serial=0)

With munkres3 (Python 3 port) I get infinite loop when using sys.float_info.max values in the matrix.

The current Munkres.compute(cost_matrix) alters cost_matrix, in contrast with what is written in the docstring.
Example:

import numpy as np
from munkres import Munkres
cost_matrix = np.random.rand(10, 10)
cost_matrix_copy = cost_matrix.copy()
m = Munkres()
print(cost_matrix == cost_matrix_copy)
result = m.compute(cost_matrix)
print(cost_matrix == cost_matrix_copy)

$ python test.py
Traceback (most recent call last):
File "test.py", line 3, in
print_matrix(matrix)
File "/home/chayant/projects/solvers/munkres/munkres.py", line 730, in print_matrix
width = max(width, int(math.log10(val)) + 1)
ValueError: math domain error

$ cat test.py

from munkres import Munkres, print_matrix
matrix = [[0]]
print_matrix(matrix)

Hi there,
I am working on multiple-hypothesis tracking (mht) for object tracking. Maintaining multiple hypothesis tree requires to find not only least cost but also second least cost, third least cost and up to the number of allowed hypothesizes. I need to find is there any way to get second best (or in general kth-best solution) with this package?

Thanks!

d9fefe3 introduced test_profit_float, which passes on 64bit platforms, but not 32bit. At least in my testing on i386 and Debian armhf:

======================================================================
FAIL: test.test_munkres.test_profit_float
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/usr/lib/python3/dist-packages/nose/case.py", line 197, in runTest
    self.test(*self.arg)
  File "/home/stefanor/git/munkres/test/test_munkres.py", line 171, in test_profit_float
    assert_almost_equal(profit, 362.65)
AssertionError: 392.65000000000003 != 362.65 within 7 places (30.000000000000057 difference)

As this example problem demonstrates, the Munkres algorithm can be applied to cost matrices with disallowed assignments (in the example, by simply ignoring non-numeric cost values).

Example use case:
I'm currently treating match pairings for an Elo-rated ladder as a variation on the assignment problem, but this entails creating a symmetric cost matrix where participating players are treated as both assignees and assignments. Since that could yield pairings where a player is paired with themselves, it would be very beneficial if I were able to simply disallow that pairing.

I'm using a lot of DISALLOWED elements, so I'm not sure if that's the issue. I've provided the cost matrix I've generated.

test.txt

It's unsolvable but I doubt that should result in an infinite loop, no? I'd like to be able to return "this was unsolvable" so I can tinker with the constraints in real time.

Hi @bmc,

Could you upload an sdist for the latest munkres version to PyPI? There's a wheel there, but for completeness' sake (and, in my case, being able to build Homebrew packages) It'd be useful to see an sdist too.

Thanks!!

Multiple versions of this algorithm exist, some of which run in O(n^4), and some of which run in O(n^3). Could you please prominently document the time bound for this version?

Hi, is this meant to fail or is this a bug?

Munkres().compute(Munkres().compute( np.array([[2],[3]])))

python3.5/site-packages/munkres.py in __step1(self)
428 # from every element in the row.
429 for j in range(n):
--> 430 self.C[i][j] -= minval
431
432 return 2

IndexError: index 1 is out of bounds for axis 0 with size 1