linear-sum-assignment

linear sum assignment

Package to perform a linear sum assignment even if the cost matrix is rectangular.

This package is the implementation of Jonker-Volgenant shortest augmenting path algorithm based on the publication On implementing 2D rectangular assignment algorithms

If the number of rows is <= the number of columns, then every row is assigned to one column; otherwise every column is assigned to one row. The assignment minimizes the sum of the assigned elements.

Instalation

$ npm i linear-sum-assignment

Usage

import linearSumAssignment from 'linear-sum-assignment';

/**
 * there is one more value in the experimental values, so one of
 * them will be not assigned.
 **/
const xValueExperimental = [1, 2, 3, 4, 5, 7];
const xValuePredicted = [3.1, 1.1, 1.9, 3.99, 5.2];

/**
 * We will compute a cost matrix where xValueExperimental are
 * rows and xValuePredicted in columns.
 * In this case we will look for the closest peak for each experimental peak value.
 **/
const diff = xValueExperimental.map((experimental) => {
  return xValuePredicted.map((predicted) => {
    return Math.abs(predicted - experimental);
  });
});

const result = linearSumAssignment(diff, { maximaze: false });
console.log(result);
/**
{
  rowAssignments: Float64Array(6) [ 1, 2, 0, 3, 4, -1 ],
  columnAssignments: Float64Array(5) [ 2, 0, 1, 3, 4 ],
  gain: 0.5100000000000002,
  dualVariableForColumns: Float64Array(5) [
    0.0900000000000003,
    0.0900000000000003,
    0.0900000000000003,
    0,
    0.1900000000000004
  ],
  dualVariableForRows: Float64Array(6) [ 0, 0, 0, 0, 0, 0 ]
}
*/ 

rowAssignments contains the index of the column assigned to each element in the rows (xValueExperimental). So the first element in xValueExperimental array is assigned to the second element of xValuePredicted. columnAssignments contains the index of the row assigned to each element in the columns. So the first element in xValuePredicted is assigned to third element in xValueExperimental. dualVariableForColumns and dualVariableForRows are the Lagrange multipliers or dual variables. gain the sum of the elements in the cost matrix.

License

MIT