Munkres-Algorithm

An implementation of (Kuhn-)Munkres algorithm. This implementation solves linear assignment problem in $O(n^3)$.

Features

• 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.

Install

Npm

npm install munkres-algorithm

Yarn

yarn add munkres-algorithm

Usages

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.

Examples

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 }

Other Implementations

This implementation is inspired by the followings.

• hungarian-on3
• munkres-js