Munk

Maximum and minimum cost assignments using the Hungarian/Munkres algorithm for n × m cost matrices.

Install

pip install munk

Looking for a JavaScript implementation? Check out @alg/munkres on JSR.

Examples

Munk proves min/max cost and assignment functions.

The cost functions return the cost of a maximum or minimum assignment:

from munk import min_cost, max_cost

cost_matrix = [
    [8, 4, 7],
    [5, 2, 3],
    [9, 4, 8],
]
print(min_cost(cost_matrix))  # 15
print(max_cost(cost_matrix))  # 18

Often, people refer to "minimising cost matrices" and "maximising profit matrices", Munk makes no distinction between profits and costs—a matrix of values is provided and the values in an assignment are either minimised (min_cost) or maximised (max_cost).

The assignment functions return the indices in the cost matrix for a minimum or maximum assignment:

from munk import min_assignment, max_assignment

cost_matrix = [
    [8, 4, 7],
    [5, 2, 3],
    [9, 4, 8],
]
print(min_assignment(cost_matrix))  # [(0, 0), (1, 2), (2, 1)]
print(max_assignment(cost_matrix))  # [(0, 0), (1, 1), (2, 2)]

All cost and assignment functions handle any n × m matrices:

from munk import min_assignment, max_assignment

wide = [
    [4, 5, 8, 7],
    [2, 12, 6, 5],
    [7, 8, 3, 9],
]

long = [
    [11, 13, 13],
    [7, 21, 13],
    [10, 7, 15],
    [17, 11, 13],
    [10, 13, 14],
]

print(min_assignment(wide))  # [(0, 1), (1, 0), (2, 2)]
print(max_assignment(long))  # [(1, 1), (2, 2), (3, 0)]