bmc
infinite loop, flips between step 4 and step 6
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.
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.
Another cost matrix that exhibits the infinite loop between steps 4 and 6...
same problem with this matrix: [D, 161., D], [D, 1., D], [D, 157., D], [37., D, 5.],
where D stands for DISALLOWED. It ends up in infinite loop
well, Python 3 has no limit on int value, so maybe setting the DISALLOWED to just a "really high" number would do the trick. Anyway it is not "good practise" at all
I'm utterly swamped at the moment. I will gladly take a pull request from someone who wants to have a go at fixing the issue.
@bmc now I'm working on my bachelor thesis, so I have no much time left to look deeply into the code. Now I'll test the workaround I mentioned earlier ^^. But I'll put it to my TODO list and hopefully, I'm going to be able to solve it later on :)
anyway, thanks for the reply.
I've run into this problem too, using v1.1.4 of the package.
I'm thinking that the following catches the edge condition:
def __check_unsolvability(matrix):
"""Checks additional conditions to see if an input Munkres cost matrix is unsolvable.
Munkres v1.1.4 suffers from an infinite loop given some edge conditions, when it should,
instead, emit a ``munkres.UnsolvableMatrix`` error. This function attempts to identify those
conditions.
Args:
matrix (list): of lists of numbers, representing a cost matrix (or a profit matrix) suitable
for Munkres optimization.
Raises:
munkres.UnsolvableMatrix: if the matrix is unsolvable.
"""
from munkres import DISALLOWED
from munkres import UnsolvableMatrix
non_disallowed_indices = [] # (in possibly-offending rows)
for row in matrix:
## check to see if all but 1 cell in the row are DISALLOWED
indices = [i for i in range(len(row)) if type(row[i]) != type(DISALLOWED)]
if len(indices) == 1:
if indices[0] in non_disallowed_indices:
raise UnsolvableMatrix(
"Encountered edge condition that the Munkres library doesn't check for!"
)
non_disallowed_indices.append(indices[0])
# ...
try:
__check_unsolvability(matrix)
index_pairs = Munkres().compute(matrix)
except UnsolvableMatrix:
pass # handle as needed
My logic is this: if there exists more than 1 row where all of the values are DISALLOWED except for one, and the one non-DISALLOWED value has the same index in at least two of those rows, then it's unsolvable. I don't know if the same is true column-wise. I may try that as well, if I run into similar problems with columns. If I do, I could simply transpose the matrix and recurse once. Maybe.
I'm new to this algorithm though, so if I've misinterpreted something, let me know.
If nobody's picked this up yet, I'll raise a PR today, as the solution above seems to work
@emjabs do you remember what software you used to output those example text files? I want to convert them back to lists to use as test cases
For others with the same issue, I found that using scipy.optimize.linear_sum_assignment (see here: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html) as a replacement for the munkres library works well, and solves this issue. It raises a ValueError instead of an infinite loop if the matrix is infeasible to solve.
For me, at least, it was very straightforward to switch from munkres to scipy's implementation.
