munkres v2.0.2
Munkres
A lightweight and efficient implementation of the Munkres (Hungarian) algorithm for optimal assignment.
Features
Supports
number
andbigint
matrices.Supports square (NxN) and rectangular (MxN) matrices.
Fast (benchmarks):
O(M2N) when M <= N
O(MN2) when M > N
Efficient: Uses O(M + N) memory.
Accepts any MatrixLike matrix. Use arrays, typed arrays, objects, etc.
Supports
-Infinity
andInfinity
values.Helper methods for creating and modifying matrices.
Getting Started
Install
Using npm:
npm install munkres
Using yarn:
yarn add munkres
Usage
Example 1: Using a cost matrix
import munkres from "munkres";
// Create a cost matrix. Cell [y, x] is the cost
// of assigning the y-th worker to the x-th job.
const costMatrix = [
[1, 2, 3],
[2, 4, 6],
[3, 6, 9],
];
// Find a set of optimal assignments pairs (y, x).
const assignments = munkres(costMatrix);
console.log(assignments);
// Output: [[0, 2], [1, 1], [2, 0]]
Example 2: Using a profit matrix
import { munkres, copyMatrix, invertMatrix } from "munkres";
// Create a profit matrix. Cell [y, x] is the
// profit of assigning the y-th worker to the x-th job.
const profitMatrix = [
[9, 8, 7],
[8, 6, 4],
[7, 4, 1],
];
// Covert the profit matrix into a cost matrix.
const costMatrix = copyMatrix(profitMatrix);
invertMatrix(costMatrix);
// Find a set of optimal assignments pairs (y, x).
const assignments = munkres(costMatrix);
console.log(assignments);
// Output: [[0, 2], [1, 1], [2, 0]]
API
munkres(costMatrix)
: Executes the Munkres algorithm on the given cost matrix and returns a set of optimal assignment pairs. Even if there are multiple optimal assignment sets, only one is returned.
Types
Matrix<T>
: A generic 2D matrix (i.e.T[][]
).MatrixLike<T>
: A generic read-only 2D matrix.- Can be made from any
ArrayLike
objects (i.e. any indexable object with a numericlength
property). This allows for more flexibility, such as matrices made with typed arrays or objects.
- Can be made from any
Pair<A, B = A>
: A generic pair (i.e.[A, B]
).
Helpers
copyMatrix(matrix)
: Creates a copy of the given matrix.createMatrix(workers, jobs, callbackFn)
: Generates a matrix based on the given workers, jobs, and callback function.genMatrix(numRows, numCols, callbackFn)
: Generates a matrix based on the given dimensions and a callback function.getMatrixMax(matrix)
: Finds the maximum value in a given matrix.getMatrixMin(matrix)
: Finds the minimum value in a given matrix.invertMatrix(matrix, bigVal?)
: Inverts the values in the given matrix. Useful for converting between minimizing and maximizing problems. IfbigVal
is not given, the matrix's max value is used instead.negateMatrix(matrix)
: Negates all values in the given matrix. Useful for converting between minimizing and maximizing problems.
Community and Support
Any feedback, bug reports, feature requests, etc. are welcomed!
Feel free to submit an issue, pull request, or reach out via GitHub discussions.
Build
- Clone the project from github
git clone git@github.com:havelessbemore/munkres.git
cd munkres
- Install dependencies
npm install
- Build the project
npm run build
This will build ESM and CommonJS outputs in the dist/ folder.
Format
To run the code linter:
npm run lint
To automatically fix linting issues, run:
npm run format
Test
To run tests:
npm test
To run tests with a coverage report:
npm run test:coverage
A coverage report is generated at ./coverage/index.html
.
Benchmarks
To run benchmarks:
npm run bench
CI / CD
Click here for historical results.
Benchmarks are integrated into our CI/CD pipeline and automatically run with each commit to the main
branch. This helps monitor the performance impacts of development, preventing regressions and verifying changes maintain performance standards.
Specs:
- Package version: latest
- OS: ubuntu-latest
- Runtime: NodeJS v20
- Benchmarking Tool: tinybench v2.6.0
Results
Run benchmarks in your browser.
Below are the latest results from running locally.
Specs:
- Package version: v2.0.1
- OS: M2 Macbook Air, Sonoma v14.4.1
- Runtime: NodeJS v20.12.2
- Benchmarking Tool: tinybench v2.6.0
number[][]
Dimensions | Min (ms) | Max (ms) | Avg (ms) | Samples |
---|---|---|---|---|
2x2 | 0 | 0.92475 | 0.00014 | 3,611,437 |
4x4 | 0.00013 | 0.38683 | 0.00041 | 1,227,622 |
8x8 | 0.00062 | 0.2005 | 0.00134 | 372,763 |
16x16 | 0.002 | 0.26346 | 0.00487 | 102,720 |
32x32 | 0.009 | 0.06462 | 0.01874 | 26,678 |
64x64 | 0.04483 | 0.28279 | 0.07837 | 6,381 |
128x128 | 0.228 | 0.52058 | 0.34338 | 1,457 |
256x256 | 1.07725 | 2.37567 | 1.59139 | 315 |
512x512 | 5.86442 | 9.18546 | 7.71347 | 65 |
1024x1024 | 31.82083 | 45.471 | 38.12961 | 50 |
2048x2048 | 165.45792 | 245.93154 | 205.5154 | 50 |
4096x4096 | 905.25592 | 1,384.78808 | 1,129.78629 | 50 |
8192x8192 | 5,062.63533 | 7,561.39129 | 6,152.11964 | 50 |
bigint[][]
Dimensions | Min (ms) | Max (ms) | Avg (ms) | Samples |
---|---|---|---|---|
2x2 | 0.00004 | 1.45567 | 0.00018 | 2,763,520 |
4x4 | 0.00029 | 0.61792 | 0.00058 | 860,516 |
8x8 | 0.00121 | 0.63829 | 0.00246 | 203,435 |
16x16 | 0.0045 | 0.639 | 0.00994 | 50,320 |
32x32 | 0.02021 | 0.66221 | 0.04299 | 11,633 |
64x64 | 0.11575 | 1.00283 | 0.19514 | 2,563 |
128x128 | 0.53988 | 1.92654 | 0.9169 | 546 |
256x256 | 3.32492 | 6.38088 | 4.51322 | 112 |
512x512 | 15.75375 | 46.94746 | 25.27091 | 50 |
1024x1024 | 107.30771 | 171.37271 | 129.81464 | 50 |
2048x2048 | 546.04767 | 850.22892 | 689.95893 | 50 |
4096x4096 | 2,835.29229 | 4,583.96688 | 3,697.85205 | 50 |
8192x8192 | 18,069.79829 | 24,171.88267 | 21,107.47192 | 10 |
Made with ❤️ by Michael Rojas