Broken algo, tests

[canyone2015]

How I use it:

from munkres import Munkres

def munkres(cost_matrix):
    return Munkres().compute(cost_matrix)

Failed test cases:

Test 1.

# test_irregular
[[12, 26, 17],
 [49, 43, 36, 10, 5],
 [97, 9, 66, 34],
 [52, 42, 19, 36],
 [15, 93, 55, 80]]

Expected: [(0, 2), (1, 4), (2, 1), (3, 3), (4, 0)] → 82
Actual: [(2, 1), (3, 2), (4, 0)] → 43

Test 2.

# test_irregular_float
[[12.01, 26.02, 17.03],
 [49.04, 43.05, 36.06, 10.07, 5.08],
 [97.09, 9.1, 66.11, 34.12],
 [52.13, 42.14, 19.15, 36.16],
 [15.17, 93.18, 55.19, 80.2]]

Expected: [(0, 2), (1, 4), (2, 1), (3, 3), (4, 0)] → 82.54
Actual: [(2, 1), (3, 2), (4, 0)] → 43.42

Test 3.

# test_20_x_20_float
[[5.0001, 4.0002, 3.0003, 9.0004, 8.0005, 9.0006, 3.0007, 5.0008, 6.0009, 9.001, 4.0011, 10.0012, 3.0013, 5.0014, 6.0015, 6.0016, 1.0017, 8.0018, 10.0019, 2.002],
 [10.0021, 9.0022, 9.0023, 2.0024, 8.0025, 3.0026, 9.0027, 9.0028, 10.0029, 1.003, 7.0031, 10.0032, 8.0033, 4.0034, 2.0035, 1.0036, 4.0037, 8.0038, 4.0039, 8.004],
 [10.0041, 4.0042, 4.0043, 3.0044, 1.0045, 3.0046, 5.0047, 10.0048, 6.0049, 8.005, 6.0051, 8.0052, 4.0053, 10.0054, 7.0055, 2.0056, 4.0057, 5.0058, 1.0059, 8.006],
 [2.0061, 1.0062, 4.0063, 2.0064, 3.0065, 9.0066, 3.0067, 4.0068, 7.0069, 3.007, 4.0071, 1.0072, 3.0073, 2.0074, 9.0075, 8.0076, 6.0077, 5.0078, 7.0079, 8.008],
 [3.0081, 4.0082, 4.0083, 1.0084, 4.0085, 10.0086, 1.0087, 2.0088, 6.0089, 4.009, 5.0091, 10.0092, 2.0093, 2.0094, 3.0095, 9.0096, 10.0097, 9.0098, 9.0099, 10.01],
 [1.0101, 10.0102, 1.0103, 8.0104, 1.0105, 3.0106, 1.0107, 7.0108, 1.0109, 1.011, 2.0111, 1.0112, 2.0113, 6.0114, 3.0115, 3.0116, 4.0117, 4.0118, 8.0119, 6.012],
 [1.0121, 8.0122, 7.0123, 10.0124, 10.0125, 3.0126, 4.0127, 6.0128, 1.0129, 6.013, 6.0131, 4.0132, 9.0133, 6.0134, 9.0135, 6.0136, 4.0137, 5.0138, 4.0139, 7.014],
 [8.0141, 10.0142, 3.0143, 9.0144, 4.0145, 9.0146, 3.0147, 3.0148, 4.0149, 6.015, 4.0151, 2.0152, 6.0153, 7.0154, 7.0155, 4.0156, 4.0157, 3.0158, 4.0159, 7.016],
 [1.0161, 3.0162, 8.0163, 2.0164, 6.0165, 9.0166, 2.0167, 7.0168, 4.0169, 8.017, 10.0171, 8.0172, 10.0173, 5.0174, 1.0175, 3.0176, 10.0177, 10.0178, 2.0179, 9.018],
 [2.0181, 4.0182, 1.0183, 9.0184, 2.0185, 9.0186, 7.0187, 8.0188, 2.0189, 1.019, 4.0191, 10.0192, 5.0193, 2.0194, 7.0195, 6.0196, 5.0197, 7.0198, 2.0199, 6.02],
 [4.0201, 5.0202, 1.0203, 4.0204, 2.0205, 3.0206, 3.0207, 4.0208, 1.0209, 8.021, 8.0211, 2.0212, 6.0213, 9.0214, 5.0215, 9.0216, 6.0217, 3.0218, 9.0219, 3.022],
 [3.0221, 1.0222, 1.0223, 8.0224, 6.0225, 8.0226, 8.0227, 7.0228, 9.0229, 3.023, 2.0231, 1.0232, 8.0233, 2.0234, 4.0235, 7.0236, 3.0237, 1.0238, 2.0239, 4.024],
 [5.0241, 9.0242, 8.0243, 6.0244, 10.0245, 4.0246, 10.0247, 3.0248, 4.0249, 10.025, 10.0251, 10.0252, 1.0253, 7.0254, 8.0255, 8.0256, 7.0257, 7.0258, 8.0259, 8.026],
 [1.0261, 4.0262, 6.0263, 1.0264, 6.0265, 1.0266, 2.0267, 10.0268, 5.0269, 10.027, 2.0271, 6.0272, 2.0273, 4.0274, 5.0275, 5.0276, 3.0277, 5.0278, 1.0279, 5.028],
 [5.0281, 6.0282, 9.0283, 10.0284, 6.0285, 6.0286, 10.0287, 6.0288, 4.0289, 1.029, 5.0291, 3.0292, 9.0293, 5.0294, 2.0295, 10.0296, 9.0297, 9.0298, 5.0299, 1.03],
 [10.0301, 9.0302, 4.0303, 6.0304, 9.0305, 5.0306, 3.0307, 7.0308, 10.0309, 1.031, 6.0311, 8, 1.0312, 1.0313, 10.0314, 9.0315, 5.0316, 7.0317, 7.0318, 5.0319, 1.032],
 [2.0321, 6.0322, 6.0323, 6.0324, 6.0325, 2.0326, 9.0327, 4.0328, 7.0329, 5.033, 3.0331, 2.0332, 10.0333, 3.0334, 4.0335, 5.0336, 10.0337, 9.0338, 1.0339, 7.034],
 [5.0341, 2.0342, 4.0343, 9.0344, 8.0345, 4.0346, 8.0347, 2.0348, 4.0349, 1.035, 3.0351, 7.0352, 6.0353, 8.0354, 1.0355, 6.0356, 8.0357, 8.0358, 10.0359, 10.036],
 [9.0361, 6.0362, 3.0363, 1.0364, 8.0365, 5.0366, 7.0367, 8.0368, 7.0369, 2.037, 1.0371, 8.0372, 2.0373, 8.0374, 3.0375, 7.0376, 4.0377, 8.0378, 7.0379, 7.038],
 [8.0381, 4.0382, 4.0383, 9.0384, 7.0385, 10.0386, 6.0387, 2.0388, 1.0389, 5.039, 8.0391, 5.0392, 1.0393, 1.0394, 1.0395, 9.0396, 1.0397, 3.0398, 5.0399, 3.04]]

Expected: [(0, 16), (1, 15), (2, 4), (3, 1), (4, 3), (5, 6), (6, 8), (7, 11), (8, 0), (9, 9), (10, 2), (11, 17), (12, 12), (13, 5), (14, 19), (15, 20), (16, 18), (17, 14), (18, 10), (19, 13)] → 21.4022
Actual: [(0, 16), (1, 15), (2, 4), (3, 1), (4, 3), (5, 6), (6, 8), (7, 11), (8, 0), (9, 9), (10, 2), (11, 17), (12, 12), (13, 5), (14, 19), (15, 13), (16, 18), (17, 14), (18, 10)] → 20.362

[canyone2015]

That's not all the problems. There are cases that make the algorithm does not finish its work.

Test 4.

[[DISALLOWED, 161., DISALLOWED],
 [DISALLOWED, 1., DISALLOWED],
 [DISALLOWED, 157., DISALLOWED],
 [37., DISALLOWED, 5.]]

Expected: unsolvable
Actual: infinite loop

[canyone2015]

This version (not yours) partially works, but it still needs to be tested.

Based on scipy.optimize.linear_sum_assignment: rectangular_lsap.cpp

munkres 2

import math


class UnsolvableMatrix(Exception):
    pass


class DisallowedObject:
    pass


def _augmenting_path(nc, cost, u, v, path, row4col,
                     shortest_path_costs, i, sr_list, sc_list, remaining, min_val):
    """
    Finds the shortest augmenting path in the bipartite graph.
    """
    # Initialize 'remaining' in reverse order.
    # This ensures that the solution of a constant cost matrix is the identity matrix.
    num_remaining = nc
    for it in range(nc):
        remaining[it] = nc - it - 1
    # Reset state arrays
    for k in range(len(sr_list)):
        sr_list[k] = False
    for k in range(len(sc_list)):
        sc_list[k] = False
    for k in range(len(shortest_path_costs)):
        shortest_path_costs[k] = math.inf
    sink = -1
    while sink == -1:
        index = -1
        lowest = math.inf
        sr_list[i] = True
        # Iterate over remaining nodes
        for it in range(num_remaining):
            j = remaining[it]
            r = min_val + cost[i][j] - u[i] - v[j]
            if r < shortest_path_costs[j]:
                path[j] = i
                shortest_path_costs[j] = r
            # When multiple nodes have the minimum cost, we select one which
            # gives us a new sink node. This is particularly important for
            # integer cost matrices with small coefficients.
            if (shortest_path_costs[j] < lowest or
                    (shortest_path_costs[j] == lowest and row4col[j] == -1)):
                lowest = shortest_path_costs[j]
                index = it
        min_val = lowest
        if min_val == math.inf:  # Infeasible cost matrix (disconnected graph)
            return -1, min_val
        j = remaining[index]
        if row4col[j] == -1:
            sink = j
        else:
            i = row4col[j]
        sc_list[j] = True
        # Remove the processed node from 'remaining' by swapping it with the last one
        num_remaining -= 1
        remaining[index] = remaining[num_remaining]
    return sink, min_val


def munkres(
    cost_matrix: list[list[int | float | DisallowedObject]],
    maximize: bool = False
) -> list[tuple[int, int]]:
    """
    Solve the rectangular linear sum assignment problem.
    :param cost_matrix: The cost matrix. Entries can be numbers or "DisallowedObject".
    :param maximize: Calculates a maximum weight matching if True.
    :return: list[(row_index, col_index)]. An array of row and col indices giving the optimal assignment.
    """
    max_columns = max(map(len, cost_matrix))
    cost_matrix = [row + [DisallowedObject()] * (max_columns - len(row)) for row in cost_matrix]
    # 1. Validate Dimensions
    nr = len(cost_matrix)
    if nr == 0:
        return []
    nc = len(cost_matrix[0])
    if nc == 0:
        return []
    # 2. Handle Transposition
    # The algorithm assumes nr <= nc. If not, we transpose the matrix.
    transpose = nc < nr
    # Determine effective dimensions for the internal solver
    eff_nr = nc if transpose else nr
    eff_nc = nr if transpose else nc
    # 3. Preprocess Matrix (Handle Transpose, Maximize, and DisallowedObject)
    # We build the internal 'cost' matrix here.
    cost = [[0.0] * eff_nc for _ in range(eff_nr)]
    for r in range(eff_nr):
        for c in range(eff_nc):
            # Map coordinates based on transposition
            if transpose:
                val = cost_matrix[c][r]
            else:
                val = cost_matrix[r][c]
            if isinstance(val, (int, float)):
                if maximize:
                    cost[r][c] = -val
                else:
                    cost[r][c] = val
            else:
                cost[r][c] = math.inf
            val = cost[r][c]
            if math.isnan(val) or val == -math.inf:
                raise ValueError("Matrix contains invalid numeric entries (NaN or -inf)")
    # 4. Initialize Solver Variables
    u = [0.0] * eff_nr
    v = [0.0] * eff_nc
    shortest_path_costs = [0.0] * eff_nc
    path = [-1] * eff_nc
    col4row = [-1] * eff_nr
    row4col = [-1] * eff_nc
    sr_list = [False] * eff_nr
    sc_list = [False] * eff_nc
    remaining = [0] * eff_nc
    # 5. Iteratively Build Solution
    for cur_row in range(eff_nr):
        min_val = 0.0
        sink, min_val = _augmenting_path(
            eff_nc, cost, u, v, path, row4col,
            shortest_path_costs, cur_row, sr_list, sc_list,
            remaining, min_val
        )
        if sink < 0:
            raise UnsolvableMatrix()
        # Update dual variables
        u[cur_row] += min_val
        for i in range(eff_nr):
            if sr_list[i] and i != cur_row:
                u[i] += min_val - shortest_path_costs[col4row[i]]
        for j in range(eff_nc):
            if sc_list[j]:
                v[j] -= min_val - shortest_path_costs[j]
        # Augment previous solution
        j = sink
        while True:
            i = path[j]
            row4col[j] = i
            col4row[i], j = j, col4row[i]  # swap
            if i == cur_row:
                break
    # 6. Format Output
    if transpose:
        # If we transposed the input, we must sort the results to match original rows
        v_sorted_indices = sorted(range(len(col4row)), key=lambda k: col4row[k])
        a = [col4row[i] for i in v_sorted_indices]
        b = v_sorted_indices
    else:
        a = list(range(eff_nr))
        b = col4row
    return list(zip(a, b))

[bmc]

I haven't actually maintained this thing for years, and I'm probably not going to start digging into it again any time soon. I'm happy for someone to fork it and continue forward with it. Meanwhile, I have too much else going on to make this a priority. Sorry.

[canyone2015]

Okay.
This issue must stay open until the repo's code is completely fixed.

[canyone2015]

If anyone is interested, there are test cases:

Test cases

# munkres(cost_matrix)
# UnsolvableMatrix

def run_examples():
    DISALLOWED = DisallowedObject()

    matrices = [
        ('min', '#1-int-min', 12,
         [[5, 9, 1],
          [10, 3, 2],
          [8, 7, 4]]),

        ('min', '#2-int-min', 18,
         [[10, 10, 8],
          [9, 8, 1],
          [9, 7, 4]]),

        ('min', '#3-int-min', 15,
         [[10, 10, 8, 11],
          [9, 8, 1, 1],
          [9, 7, 4, 10]]),

        ('min', '#4-int-min', 850,
         [[400, 150, 400],
          [400, 450, 600],
          [300, 225, 300]]),

        ('min', '#5-int-min', 452,
         [[400, 150, 400, 1],
          [400, 450, 600, 2],
          [300, 225, 300, 3]]),

        ('min', '#6-int-min', 70,
         [[34, 26, 17, 12],
          [43, 43, 36, 10],
          [97, 47, 66, 34],
          [52, 42, 19, 36],
          [15, 93, 55, 80]]),

        ('min', '#7-int-min', 51,
         [[12, 9, 27, 10, 23],
          [7, 13, 13, 30, 19],
          [25, 18, 26, 11, 26],
          [9, 28, 26, 23, 13],
          [16, 16, 24, 6, 9]]),

        ('min', '#8-int-min', 82,
         [[12, 26, 17],
          [49, 43, 36, 10, 5],
          [97, 9, 66, 34],
          [52, 42, 19, 36],
          [15, 93, 55, 80]]),

        ('max', '#9-int-max', 392,
         [[94, 66, 100, 18, 48],
          [51, 63, 97, 79, 11],
          [37, 53, 57, 78, 28],
          [59, 43, 97, 88, 48],
          [52, 19, 89, 60, 60]]),

        ('min', '#10-int-min-complex', 66,
         [[37, 34, 29, 26, 19, 8, 9, 23, 19, 29],
          [9, 28, 20, 8, 18, 20, 14, 33, 23, 14],
          [15, 26, 12, 28, 6, 17, 9, 13, 21, 7],
          [2, 8, 38, 36, 39, 5, 36, 2, 38, 27],
          [30, 3, 33, 16, 21, 39, 7, 23, 28, 36],
          [7, 5, 19, 22, 36, 36, 24, 19, 30, 2],
          [34, 20, 13, 36, 12, 33, 9, 10, 23, 5],
          [7, 37, 22, 39, 33, 39, 10, 3, 13, 26],
          [21, 25, 23, 39, 31, 37, 32, 33, 38, 1],
          [17, 34, 40, 10, 29, 37, 40, 3, 25, 3]]),

        ('min', '#11-int-min-complex', 22,
         [[5, 4, 3, 9, 8, 9, 3, 5, 6, 9, 4, 10, 3, 5, 6, 6, 1, 8, 10, 2],
          [10, 9, 9, 2, 8, 3, 9, 9, 10, 1, 7, 10, 8, 4, 2, 1, 4, 8, 4, 8],
          [10, 4, 4, 3, 1, 3, 5, 10, 6, 8, 6, 8, 4, 10, 7, 2, 4, 5, 1, 8],
          [2, 1, 4, 2, 3, 9, 3, 4, 7, 3, 4, 1, 3, 2, 9, 8, 6, 5, 7, 8],
          [3, 4, 4, 1, 4, 10, 1, 2, 6, 4, 5, 10, 2, 2, 3, 9, 10, 9, 9, 10],
          [1, 10, 1, 8, 1, 3, 1, 7, 1, 1, 2, 1, 2, 6, 3, 3, 4, 4, 8, 6],
          [1, 8, 7, 10, 10, 3, 4, 6, 1, 6, 6, 4, 9, 6, 9, 6, 4, 5, 4, 7],
          [8, 10, 3, 9, 4, 9, 3, 3, 4, 6, 4, 2, 6, 7, 7, 4, 4, 3, 4, 7],
          [1, 3, 8, 2, 6, 9, 2, 7, 4, 8, 10, 8, 10, 5, 1, 3, 10, 10, 2, 9],
          [2, 4, 1, 9, 2, 9, 7, 8, 2, 1, 4, 10, 5, 2, 7, 6, 5, 7, 2, 6],
          [4, 5, 1, 4, 2, 3, 3, 4, 1, 8, 8, 2, 6, 9, 5, 9, 6, 3, 9, 3],
          [3, 1, 1, 8, 6, 8, 8, 7, 9, 3, 2, 1, 8, 2, 4, 7, 3, 1, 2, 4],
          [5, 9, 8, 6, 10, 4, 10, 3, 4, 10, 10, 10, 1, 7, 8, 8, 7, 7, 8, 8],
          [1, 4, 6, 1, 6, 1, 2, 10, 5, 10, 2, 6, 2, 4, 5, 5, 3, 5, 1, 5],
          [5, 6, 9, 10, 6, 6, 10, 6, 4, 1, 5, 3, 9, 5, 2, 10, 9, 9, 5, 1],
          [10, 9, 4, 6, 9, 5, 3, 7, 10, 1, 6, 8, 1, 1, 10, 9, 5, 7, 7, 5],
          [2, 6, 6, 6, 6, 2, 9, 4, 7, 5, 3, 2, 10, 3, 4, 5, 10, 9, 1, 7],
          [5, 2, 4, 9, 8, 4, 8, 2, 4, 1, 3, 7, 6, 8, 1, 6, 8, 8, 10, 10],
          [9, 6, 3, 1, 8, 5, 7, 8, 7, 2, 1, 8, 2, 8, 3, 7, 4, 8, 7, 7],
          [8, 4, 4, 9, 7, 10, 6, 2, 1, 5, 8, 5, 1, 1, 1, 9, 1, 3, 5, 3]]),

        ('min', '#12-float-min', 13.5,
         [[5.1, 9.2, 1.3],
          [10.4, 3.5, 2.6],
          [8.7, 7.8, 4.9]]),

        ('min', '#13-float-min', 19.5,
         [[10.1, 10.2, 8.3],
          [9.4, 8.5, 1.6],
          [9.7, 7.8, 4.9]]),

        ('min', '#14-float-min', 15.2,
         [[10.01, 10.02, 8.03, 11.04],
          [9.05, 8.06, 1.07, 1.08],
          [9.09, 7.1, 4.11, 10.12]]),

        ('min', '#15-float-min', 70.42,
         [[34.01, 26.02, 17.03, 12.04],
          [43.05, 43.06, 36.07, 10.08],
          [97.09, 47.1, 66.11, 34.12],
          [52.13, 42.14, 19.15, 36.16],
          [15.17, 93.18, 55.19, 80.2]]),

        ('min', '#16-float-min', 51.65,
         [[12.01, 9.02, 27.03, 10.04, 23.05],
          [7.06, 13.07, 13.08, 30.09, 19.1],
          [25.11, 18.12, 26.13, 11.14, 26.15],
          [9.16, 28.17, 26.18, 23.19, 13.2],
          [16.21, 16.22, 24.23, 6.24, 9.25]]),

        ('min', '#17-float-min', 82.54,
         [[12.01, 26.02, 17.03],
          [49.04, 43.05, 36.06, 10.07, 5.08],
          [97.09, 9.1, 66.11, 34.12],
          [52.13, 42.14, 19.15, 36.16],
          [15.17, 93.18, 55.19, 80.2]]),

        ('max', '#18-float-max', 392.65,
         [[94.01, 66.02, 100.03, 18.04, 48.05],
          [51.06, 63.07, 97.08, 79.09, 11.1],
          [37.11, 53.12, 57.13, 78.14, 28.15],
          [59.16, 43.17, 97.18, 88.19, 48.2],
          [52.21, 19.22, 89.23, 60.24, 60.25]]),

        ('min', '#19-float-min-complex', 66.505,
         [[37.001, 34.002, 29.003, 26.004, 19.005, 8.006, 9.007, 23.008, 19.009, 29.01],
          [9.011, 28.012, 20.013, 8.014, 18.015, 20.016, 14.017, 33.018, 23.019, 14.02],
          [15.021, 26.022, 12.023, 28.024, 6.025, 17.026, 9.027, 13.028, 21.029, 7.03],
          [2.031, 8.032, 38.033, 36.034, 39.035, 5.036, 36.037, 2.038, 38.039, 27.04],
          [30.041, 3.042, 33.043, 16.044, 21.045, 39.046, 7.047, 23.048, 28.049, 36.05],
          [7.051, 5.052, 19.053, 22.054, 36.055, 36.056, 24.057, 19.058, 30.059, 2.06],
          [34.061, 20.062, 13.063, 36.064, 12.065, 33.066, 9.067, 10.068, 23.069, 5.07],
          [7.071, 37.072, 22.073, 39.074, 33.075, 39.076, 10.077, 3.078, 13.079, 26.08],
          [21.081, 25.082, 23.083, 39.084, 31.085, 37.086, 32.087, 33.088, 38.089, 1.09],
          [17.091, 34.092, 40.093, 10.094, 29.095, 37.096, 40.097, 3.098, 25.099, 3.1]]),

        ('min', '#20-float-min-complex', 21.4022,
         [[5.0001, 4.0002, 3.0003, 9.0004, 8.0005, 9.0006, 3.0007, 5.0008, 6.0009, 9.001, 4.0011, 10.0012, 3.0013, 5.0014, 6.0015, 6.0016, 1.0017, 8.0018, 10.0019, 2.002],
          [10.0021, 9.0022, 9.0023, 2.0024, 8.0025, 3.0026, 9.0027, 9.0028, 10.0029, 1.003, 7.0031, 10.0032, 8.0033, 4.0034, 2.0035, 1.0036, 4.0037, 8.0038, 4.0039, 8.004],
          [10.0041, 4.0042, 4.0043, 3.0044, 1.0045, 3.0046, 5.0047, 10.0048, 6.0049, 8.005, 6.0051, 8.0052, 4.0053, 10.0054, 7.0055, 2.0056, 4.0057, 5.0058, 1.0059, 8.006],
          [2.0061, 1.0062, 4.0063, 2.0064, 3.0065, 9.0066, 3.0067, 4.0068, 7.0069, 3.007, 4.0071, 1.0072, 3.0073, 2.0074, 9.0075, 8.0076, 6.0077, 5.0078, 7.0079, 8.008],
          [3.0081, 4.0082, 4.0083, 1.0084, 4.0085, 10.0086, 1.0087, 2.0088, 6.0089, 4.009, 5.0091, 10.0092, 2.0093, 2.0094, 3.0095, 9.0096, 10.0097, 9.0098, 9.0099, 10.01],
          [1.0101, 10.0102, 1.0103, 8.0104, 1.0105, 3.0106, 1.0107, 7.0108, 1.0109, 1.011, 2.0111, 1.0112, 2.0113, 6.0114, 3.0115, 3.0116, 4.0117, 4.0118, 8.0119, 6.012],
          [1.0121, 8.0122, 7.0123, 10.0124, 10.0125, 3.0126, 4.0127, 6.0128, 1.0129, 6.013, 6.0131, 4.0132, 9.0133, 6.0134, 9.0135, 6.0136, 4.0137, 5.0138, 4.0139, 7.014],
          [8.0141, 10.0142, 3.0143, 9.0144, 4.0145, 9.0146, 3.0147, 3.0148, 4.0149, 6.015, 4.0151, 2.0152, 6.0153, 7.0154, 7.0155, 4.0156, 4.0157, 3.0158, 4.0159, 7.016],
          [1.0161, 3.0162, 8.0163, 2.0164, 6.0165, 9.0166, 2.0167, 7.0168, 4.0169, 8.017, 10.0171, 8.0172, 10.0173, 5.0174, 1.0175, 3.0176, 10.0177, 10.0178, 2.0179, 9.018],
          [2.0181, 4.0182, 1.0183, 9.0184, 2.0185, 9.0186, 7.0187, 8.0188, 2.0189, 1.019, 4.0191, 10.0192, 5.0193, 2.0194, 7.0195, 6.0196, 5.0197, 7.0198, 2.0199, 6.02],
          [4.0201, 5.0202, 1.0203, 4.0204, 2.0205, 3.0206, 3.0207, 4.0208, 1.0209, 8.021, 8.0211, 2.0212, 6.0213, 9.0214, 5.0215, 9.0216, 6.0217, 3.0218, 9.0219, 3.022],
          [3.0221, 1.0222, 1.0223, 8.0224, 6.0225, 8.0226, 8.0227, 7.0228, 9.0229, 3.023, 2.0231, 1.0232, 8.0233, 2.0234, 4.0235, 7.0236, 3.0237, 1.0238, 2.0239, 4.024],
          [5.0241, 9.0242, 8.0243, 6.0244, 10.0245, 4.0246, 10.0247, 3.0248, 4.0249, 10.025, 10.0251, 10.0252, 1.0253, 7.0254, 8.0255, 8.0256, 7.0257, 7.0258, 8.0259, 8.026],
          [1.0261, 4.0262, 6.0263, 1.0264, 6.0265, 1.0266, 2.0267, 10.0268, 5.0269, 10.027, 2.0271, 6.0272, 2.0273, 4.0274, 5.0275, 5.0276, 3.0277, 5.0278, 1.0279, 5.028],
          [5.0281, 6.0282, 9.0283, 10.0284, 6.0285, 6.0286, 10.0287, 6.0288, 4.0289, 1.029, 5.0291, 3.0292, 9.0293, 5.0294, 2.0295, 10.0296, 9.0297, 9.0298, 5.0299, 1.03],
          [10.0301, 9.0302, 4.0303, 6.0304, 9.0305, 5.0306, 3.0307, 7.0308, 10.0309, 1.031, 6.0311, 8, 1.0312, 1.0313, 10.0314, 9.0315, 5.0316, 7.0317, 7.0318, 5.0319, 1.032],
          [2.0321, 6.0322, 6.0323, 6.0324, 6.0325, 2.0326, 9.0327, 4.0328, 7.0329, 5.033, 3.0331, 2.0332, 10.0333, 3.0334, 4.0335, 5.0336, 10.0337, 9.0338, 1.0339, 7.034],
          [5.0341, 2.0342, 4.0343, 9.0344, 8.0345, 4.0346, 8.0347, 2.0348, 4.0349, 1.035, 3.0351, 7.0352, 6.0353, 8.0354, 1.0355, 6.0356, 8.0357, 8.0358, 10.0359, 10.036],
          [9.0361, 6.0362, 3.0363, 1.0364, 8.0365, 5.0366, 7.0367, 8.0368, 7.0369, 2.037, 1.0371, 8.0372, 2.0373, 8.0374, 3.0375, 7.0376, 4.0377, 8.0378, 7.0379, 7.038],
          [8.0381, 4.0382, 4.0383, 9.0384, 7.0385, 10.0386, 6.0387, 2.0388, 1.0389, 5.039, 8.0391, 5.0392, 1.0393, 1.0394, 1.0395, 9.0396, 1.0397, 3.0398, 5.0399, 3.04]]),

        ('min', '#21-int-disallowed-min', 10,
         [[1, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, 2, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, 3, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, 4]]),

        ('min', '#22-int-disallowed-min', 20,
         [[4, 5, 6, DISALLOWED],
          [1, 9, 12, 11],
          [DISALLOWED, 5, 4, DISALLOWED],
          [12, 12, 12, 10]]),

        ('min', '#23-int-disallowed-min', 19,
         [[5, 9, DISALLOWED],
          [10, DISALLOWED, 2],
          [8, DISALLOWED, 4]]),

        ('min', '#24-int-disallowed-unsolvable-min', UnsolvableMatrix,
         [[5, 9, DISALLOWED],
          [10, DISALLOWED, 2],
          [DISALLOWED, DISALLOWED, DISALLOWED]]),

        ('min', '#25-float-disallowed-min', 11.0,
         [[1.1, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, 2.2, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, 3.3, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, 4.4]]),

        ('min', '#26-float-disallowed-min', 20.028,
         [[4.001, 5.002, 6.003, DISALLOWED],
          [1.004, 9.005, 12.006, 11.007],
          [DISALLOWED, 5.008, 4.009, DISALLOWED],
          [12.01, 12.011, 12.012, 10.013]]),

        ('min', '#27-float-disallowed-min', 20.1,
         [[5.1, 9.2, DISALLOWED],
          [10.3, DISALLOWED, 2.4],
          [8.5, DISALLOWED, 4.6]]),

        ('min', '#28-float-disallowed-unsolvable-min', UnsolvableMatrix,
         [[5.1, 9.2, DISALLOWED],
          [10.3, DISALLOWED, 2.4],
          [DISALLOWED, DISALLOWED, DISALLOWED]]),

        ('min', '#29-float-disallowed-unsolvable-min', UnsolvableMatrix,
         [[DISALLOWED, 161., DISALLOWED],
          [DISALLOWED, 1., DISALLOWED],
          [DISALLOWED, 157., DISALLOWED],
          [37., DISALLOWED, 5.]]),

        ('min', '#30-float-unsolvable-min-complex', UnsolvableMatrix,
         [[DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.001, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.001, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.001, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.001, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.001, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.001, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.001, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.001, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.001],
          [DISALLOWED, 0.11687445, DISALLOWED, DISALLOWED, 0.01319788, 0.07509257, DISALLOWED, DISALLOWED, DISALLOWED, 0.74228317, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, 0.81087935, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.8408466, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.01194389, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, 0.82994211, DISALLOWED, DISALLOWED, DISALLOWED, 0.11468516, DISALLOWED, DISALLOWED, DISALLOWED, 0.11173505, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [0.18796507, DISALLOWED, 0.04002318, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.75883335, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, 0.71545464, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.02748488, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [0.78470564, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.14829198, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, 0.10870609, DISALLOWED, DISALLOWED, DISALLOWED, 0.8918677, DISALLOWED, DISALLOWED, DISALLOWED, 0.06306644, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.63844085, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.7442354, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.09850549, DISALLOWED, DISALLOWED, 0.18638258, 0.2769244, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.73182464, DISALLOWED, DISALLOWED, 0.46443561, 0.38589284, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED],
          [0.29510278, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, 0.09666032, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED, DISALLOWED]]),

        ('min', '#31-float-inf-min', 18,
         [[10.0, float("inf"), float("inf")],
          [float("inf"), float("inf"), 1.0],
          [float("inf"), 7.0, float("inf")]]),
    ]

    print(f"{'Test Name':<35} | {'Expected':<10} | {'Actual':<10} | {'Status'}")
    print("-" * 75)

    big_value = 2 ** 32
    for task_type, title, expected_value, matrix in matrices:
        matrix_copy = (
            [row.copy() for row in matrix]
            if task_type == 'min' else
            [
                [
                    big_value - matrix[i][j]
                    if isinstance(matrix[i][j], (int, float)) else
                    matrix[i][j]
                    for j in range(len(matrix[i]))
                ] for i in range(len(matrix))
            ]
        )

        expected_value_string = 'unsolvable' if expected_value is UnsolvableMatrix else f"{expected_value:<10}"
        try:
            indexes = []
            is_correct = False
            actual_value_string = ''
            if expected_value is UnsolvableMatrix:
                try:
                    indexes = munkres(matrix_copy)
                except UnsolvableMatrix:
                    is_correct = True
                    actual_value_string = 'unsolvable'
            else:
                try:
                    indexes = munkres(matrix_copy)
                    actual_value = sum(matrix[i][j] for i, j in indexes)
                    actual_value_string = f"{actual_value:<10.4g}"
                    is_correct = abs(actual_value - expected_value) <= 1e-3
                except UnsolvableMatrix:
                    is_correct = False
                    actual_value_string = 'unsolvable'

            print(f"{title:<35} | {expected_value_string:<10} | {actual_value_string:<10} | {'PASS' if is_correct else 'FAIL'}")
            if not is_correct:
                print(f"{' ':<10} -> Indexes found: {indexes}")
        except BaseException as e:
            print(f"{title:<35} | {expected_value_string:<10} | {'ERROR':<10} | {e}")
            import traceback
            traceback.print_exc()

    # ['maximize' parameter testing]
    # print("-" * 75)
    # print(f"{'Test Name':<35} | {'Expected':<10} | {'Actual':<10} | {'Status'}")
    # print("-" * 75)
    #
    # big_value = 2 ** 32
    # for task_type, title, expected_value, matrix in matrices:
    #     matrix_copy = (
    #         [row.copy() for row in matrix]
    #         if task_type == 'max' else
    #         [
    #             [
    #                 big_value - matrix[i][j]
    #                 if isinstance(matrix[i][j], (int, float)) else
    #                 matrix[i][j]
    #                 for j in range(len(matrix[i]))
    #             ] for i in range(len(matrix))
    #         ]
    #     )
    #
    #     expected_value_string = 'unsolvable' if expected_value is UnsolvableMatrix else f"{expected_value:<10}"
    #     try:
    #         indexes = []
    #         is_correct = False
    #         actual_value_string = ''
    #         if expected_value is UnsolvableMatrix:
    #             try:
    #                 indexes = munkres(matrix_copy, maximize=True)
    #             except UnsolvableMatrix:
    #                 is_correct = True
    #                 actual_value_string = 'unsolvable'
    #         else:
    #             try:
    #                 indexes = munkres(matrix_copy, maximize=True)
    #                 actual_value = sum(matrix[i][j] for i, j in indexes)
    #                 actual_value_string = f"{actual_value:<10.4g}"
    #                 is_correct = abs(actual_value - expected_value) <= 1e-3
    #             except UnsolvableMatrix:
    #                 is_correct = False
    #                 actual_value_string = 'unsolvable'
    #
    #         print(f"{title:<35} | {expected_value_string:<10} | {actual_value_string:<10} | {'PASS' if is_correct else 'FAIL'}")
    #         if not is_correct:
    #             print(f"{' ':<10} -> Indexes found: {indexes}")
    #     except BaseException as e:
    #         print(f"{title:<35} | {expected_value_string:<10} | {'ERROR':<10} | {e}")
    #         import traceback
    #         traceback.print_exc()


if __name__ == '__main__':
    run_examples()

[st1vms]

@canyone2015

In case you'd like to contribute, there is this new implementation I published here: https://github.com/st1vms/py-munkres

It still need extra testing against edge cases before going into production, but hopefully we could then migrate the python munkres implementation there if the original maintainer and the community approves...

[canyone2015]

@st1vms

You wrote your comment too early.
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.

Note that I'm not asking you to do extra work.
I've already done all of the above myself:

• code: Broken algo, tests #51 (comment)
• tests: Broken algo, tests #51 (comment)