py-munkres repository

[st1vms]

Hi, I recently published my implementation of the Munkres algorithm: https://github.com/st1vms/py-munkres, which I'm willing to maintain and accept contributions. Feel free to reference it in this repository if you like.

It still needs some testing, as it's not compatible with rectangular matrices by default, although padding the matrix with zeros works in most cases.

I've tested some edge cases I've found in issues, but I'm sure there are more to discover. 🧐

[canyone2015]

First:

• add support for rectangular matrices;
• fix all the issues with float;
• add support for values of type DisallowedObject (to distinguish from int/float);
• add all the correct tests that exist in this repository.

[st1vms]

Thanks for the suggestions @canyone2015.

The roadmap for py-munkres includes the auto padding logic for supporting rectangular matrices and irregular matrices out of the box, I will also add the logic for disallowing specific assignments.

The float calculations should already work as soon as I added the tolerance value, but I will include more tests for verification and reproducibility purposes. I already included tests from scipy's linear_sum_assignment test suite:

https://github.com/scipy/scipy/blob/7d117511aded88e49ee22a8d4a54adf439bafe51/scipy/sparse/csgraph/tests/test_matching.py#L269

I will also add all the tests from this repository.

[st1vms]

@canyone2015 thanks again for your suggestions.

I’d like to invite you to test the new out-of-the-box support for rectangular matrices.
I have also added all the tests from bmc/munkres, and they confirm correctness and optimality for all computed assignments.

The logic for disallowing specific assignments is not implemented yet, but I already have a clear approach that avoids modifying the cost matrix. I will work on that next.

Any feedback on the current behavior or edge cases you think are worth adding is welcome.

[canyone2015]

I don't see the need for:

total_cost = sum(
    cost_matrix[i][j] if j != -1 else 0 for i, j in enumerate(assignments)
)

disallowment_map/argument

inversions/return value

[st1vms]

I don't see the need for:

total_cost = sum(
cost_matrix[i][j] if j != -1 else 0 for i, j in enumerate(assignments)
)
disallowment_map/argument

inversions/return value

I added total_cost just for demonstration purposes in the README.

The purpose of the inversions vector's return value is to provide additional information; this vector allows for the reverse assignment, job -> worker and since linear_sum_assignment doesn't provide it, I decided to include it, it's already a key component of the algorithm, so returning it doesn't actually harm.

In order to create the disallowance logic, I wanted to leave the cost matrix intact so that any problem could be readapted by starting from the same cost matrix. I also didn't want to mix costs with different objects, which could impact the search for the optimal solution; instead I decided to leave the disallowed assignments with a infinite fixed cost, which in turn allows the algorithm to give lowest priority to the disallowed assignments during the augmented path search. However, if some disallowed assignments are ultimately made, we convert them to unassignments during post-processing before returning the results.

But in theory we could avoid all these disallowance_map lookups by simply turning the disallowed costs into either (-inf or +inf) costs in the cost matrix by supplying disallowance_map to make_cost_matrix (or a method called disallow_costs), and then filtering out the disallowed assignments in munkres post-processing.

Looking forward for your opinions.

[canyone2015]

For this test case: Square 6 (5x5).
You initially use zero (0), so it will be in the answer initially. I don't see the goal.

For this test case: Floating Square 4 (20x20).
Expected: 21.4022 (assigments: [16, 15, 4, 1, 3, 6, 8, 11, 0, 9, 2, 17, 12, 5, 19, 20, 18, 14, 10, 13]).
Actual: 22.4009 (assigments: [16, 15, 4, 1, 3, 6, 0, 11, 14, 2, 8, 17, 12, 5, 19, 13, 18, 9, 10, 7]).
Because: [20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 20, 20, 20, 20].

[canyone2015]

I see the rest in the roadmap... Okay.

[st1vms]

@canyone2015

Regarding the Square 6 (5x5) test case, I must first point out that the munkres algorithm never deals with irregular matrices; the problem always expects a square (or a padded rectangular) matrix.

I decided to include that irregular test as a square test, trying to eliminate the cost of those "unreal" assignments, but you correctly identified some mistakes: I used 0 costs to fill those spaces. If I had used float('inf') instead, the resulting solution would not include those assignments, even though it would incur in a higher cost. It's up to the programmer to choose appropriate default costs (for padding or disallowment) in order to avoid specific assignments.

That Floating Square 4 (20x20) matrix is actually an irregular matrix, nice catch! This means I had to fill those empty cells in the last column with infinite costs (-inf for maximization, +inf for minimization). Now the expected result matches the one in bmc/munkres (21.4022).

Thanks again for your help, before moving to optimizations I really need to make sure this implementation works as expected. Once the code is extensively tested and optimized, it will be published to PyPi.