Package detail

Munkres implementation for Javascript

Introduction

The Munkres module provides an O(n³) implementation of the Munkres algorithm (also called the Hungarian algorithm or the Kuhn-Munkres algorithm). The algorithm models an assignment problem as an N×M cost matrix, where each element represents the cost of assigning the ith worker to the jth job, and it figures out the least-cost solution, choosing a single item from each row and column in the matrix, such that no row and no column are used more than once.

Usage

var munkres = require('munkres-js');

munkres([
  [400, 150, 400],
  [400, 450, 600],
  [300, 225, 300]
])
// => [ [ 0, 1 ], [ 1, 0 ], [ 2, 2 ] ]

Returns the list of matrix indices corresponding to the optimal assignment.

When used in the browser, the global computeMunkres function is exposed.

See the docs in munkres.js for more details.

Meta

This module is a translation of a Python implementation by Brian Clapper.

The original implementation is based on http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html.

It is available via bower and npm as munkres-js.

Copyright

© 2014 Anna Henningsen (Conversion to JS)

© 2008 Brian M. Clapper

License

Apache License 2.0. See accompanying LICENSE file.

1.1.0 (6 November, 2014)

• Port to JS

Original Python Changelog:

1.0.5.3 (2 August, 2009)

• Fixed documentation of print_matrix() in module docs.

1.0.5.2 (30 June, 2008):

• Incorporated some suggestions optimizations from Mark Summerfield (mark /at/ qtrac.eu)
• Munkres.make_cost_matrix() is now deprecated, in favor of a module-level function.
• The module now provides a print_matrix() convenience function.
• Fixed some bugs related to the padding of non-square matrics.

1.0.5.1 (26 June, 2008):

• Some minor doc changes.

1.0.5 (26 June, 2008):

• Now handles non-square cost matrices by padding them with zeros.
• Converted Epydocs to use reStructuredText.

1.0.4 (13 June, 2008)

• Minor bug fix in main (tester) program in munkres.py

1.0.3 (16 March, 2008)

• Minor change to prevent shadowing of built-in min() function. Thanks to Nelson Castillo (nelson /at/ emqbit.com) for pointing it out.

1.0.2 (21 February, 2008)

• Fixed an overindexing bug reported by Chris Willmore (willmc <at> rpi.edu)

1.0.1 (16 February, 2008)

• Documentation now processed by Epydoc.

1.0 (January, 2008)

• Initial release.