An implementation of (Kuhn-)Munkres algorithm.
An implementation of (Kuhn-)Munkres algorithm. This implementation solves linear assignment problem in $O(n^3)$.
- Support both array of arrays and typed array input.
- Support +Infinity and -Infinity edge weights.
- Include TypeScript type declaration.
> Note:
> For minimum(maximum) weight assignment,
> edge with +Infinity(-Infinity) weight means "non-existing" edge. It is never in the assignments.
``
npm install munkres-algorithm
`
yarn add munkres-algorithm
This package exports two functions, minWeightAssign and maxWeightAssign. As their name suggested, they solve minimum weight and maximum weight assignment problem respectively. The result object contains two fields, assignments and assignmentsWeight. If col j is assigned to row i, then assignments[i] = j. If row i has no assignment, then assignments[i] = null. assignmentsWeight is the sum of all weights in assignments.
These functions only give _ONE solution no matter how many possible solutions do exist_.
`ts
import { minWeightAssign, maxWeightAssign } from 'munkres-algorithm';
// Finite Edge Weights
minWeightAssign([
[400, 150, 400],
[400, 450, 600],
[300, 225, 300],
]);
// result:
// { assignments: [1, 0, 2], assignmentsWeight: 850 }
maxWeightAssign([
[400, 150, 400],
[400, 450, 600],
[300, 225, 300],
]);
// result:
// { assignments: [0, 2, 1], assignmentsWeight: 1225 }
// Infinite Edge Weights
minWeightAssign([
[5, 10, Infinity],
[6, Infinity, Infinity],
[Infinity, 0, 10],
[4, Infinity, Infinity],
]);
// result:
// { assignment: [1, null, 2, 0], assignmentsWeight: 24 }
maxWeightAssign([
[5, 10, Infinity],
[6, Infinity, Infinity],
[Infinity, 0, 10],
[4, Infinity, Infinity],
]);
// result:
// { assignment: [2, 1, 0, null], assignmentsWeight: Infinity }
``
This implementation is inspired by the followings.