I am trying to learn various implementations of the Hungarian Algorithm. Specifically, I want to maximise and get the highest score.
I have found two solutions from various packages: (1) the munkres package, and (2) Linear Sum Assignment in Scipy
(1) http://software.clapper.org/munkres/ (2) https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html
I was able to get something together with #1 but was finding issues in my implementation (https://github.com/bmc/munkres/issues/39). So, I am now trying to work with option #2.
Here is what I have so far:
import numpy as np
from scipy.optimize import linear_sum_assignment
matrix = np.array([
[10.01, 10.02, 8.03, 11.04],
[9.05, 8.06, 500.07, 1.08],
[9.09, 7.11, 4.11, 1000.12]
])
row_ind, col_ind = linear_sum_assignment(matrix, maximize=True)
print('\nSolution:', matrix[row_ind, col_ind].sum())
It returns the correct solution of 1510.21.
Help I would appreciate:
I have been struggling to display the workings. Ideally, what I want to see is the matching row and column pair and the score. In this example, it would be:
(0,1) (10.02)
(1,2) (500.07)
(2,3) (1000.12)
This was straight forward enough to do with the munkres package (#1 detailed above) but struggling to get my head around how to make this work with the scipy implementation.
Thanks for any help
I was able to get what I was after using something like this:-
This will return the position in the matrix along with the value.