tdedecko/hungarian-algorithm

Implementation of Hungarian Algorithm with Python and NumPy

hungarian-algorithm's Issues

Unable to find results. Algorithm has failed.

raise HungarianError("Unable to find results. Algorithm has failed.")

When I input :profit_matrix = np.array([[0.47341415,0.50526756,0.5631776 ,0.55596864,0.5414672,0.5414672],
[0.6781792,0.23801588,0.20288624,0.55276686,0.109804,0.109804],
[0.42393875,0.370307,0.37129858,0.5507781,0.2596858,0.2596858],
[0.52666223,0.57174313,0.5873437,0.6438369,0.5166061,0.5166061],
[0.6931475,0.6931475,0.6931475,0.6931475,0.6931475,0.6931475],
[0.6931475,0.6931475,0.6931475,0.6931475,0.6931475,0.6931475]])
a error will appear as follows.
File "models.py", line 41, in minimize_loss
H.calculate(np_loss_mat)
File "hungarian.py", line 151, in calculate
raise HungarianError("Unable to find results. Algorithm has failed.")
I do not know the reasons. Look forward to your reply.

TypeError: cannot cast ufunc

While just running the script as it is I get the following results:

TypeError: Cannot cast ufunc subtract output from dtype('float64') to dtype('int32') with casting rule 'same_kind'

Should only be some dtype setting somewhere, possibly a Python 2 / 3 problem?

update

There seems to be a solution as a PR already:

#3

correct matches not found

The algorithm under some circumstances fails to find the correct solution. The following code demonstrates a correct and an incorrect behaviour on similar matrices. The algorithm should find matches that include the lowest costs [15, 99, 189]. After deleting the first row of the matrix, the algorithm gives the correct solution.

mat = np.array([
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,   15, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000,   99, 1000, 1000, 1000, 1000, 1000,  171, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
   [ 189, 1000, 1000, 1000, 1000,  323, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000]])
hun = hungarian.Hungarian(mat)
hun.calculate()
matches = hun.get_results()
print "wrong"
print matches
print [mat[m[0], m[1]] for m in matches if mat[m[0], m[1]] != 1000]

mat = mat[1:,:]
hun = hungarian.Hungarian(mat)
hun.calculate()
matches = hun.get_results()
print "right"
print matches
print [mat[m[0], m[1]] for m in matches if mat[m[0], m[1]] != 1000]

Code above produces:

wrong
[(5, 3), (10, 12), (11, 2), (14, 1), (0, 0), (1, 4), (2, 5), (3, 6), (4, 7), (6, 8), (7, 9), (8, 10), (9, 11), (12, 13), (13, 14)]
[]
right
[(4, 8), (10, 7), (14, 0), (0, 1), (1, 2), (2, 3), (3, 4), (5, 5), (6, 6), (7, 9), (8, 10), (9, 11), (11, 12), (12, 13), (13, 14)]
[15, 99, 189]

I used munkres.py as a replacement.

Extend hungarian algorithm

Hi author,
Hungarian is a algorithm that divide n jobs for n people. But now, I want divide n jobs for m people and each person is in charge of 1 -> 3 jobs. So this code did it?

the meaning of "cost matrix " and "profit_matrix"

Hi, dear author:
In my perspective, the Hungarian algorithm is to find an optimal alignment during a matrix. We can give a cost square matrix and find the positions of the element .But in your script, you give two matrices named cost matrix and profit matrix. what are their meanings?