🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more
Socket
DemoInstallSign in
Socket

hungarian-on3

Package Overview
Dependencies
Maintainers
1
Versions
4
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

hungarian-on3

A hungarian algorithm that runs in O(n^3)

0.3.1
latest
Source
npm
Version published
Weekly downloads
13
-23.53%
Maintainers
1
Weekly downloads
 
Created
Source

hungarian-on3

The hungarian (Kuhn-Munkres) algorithm solved in O(n^3) time Algorithm based on: https://github.com/KevinStern/software-and-algorithms/blob/master/src/main/java/blogspot/software_and_algorithms/stern_library/optimization/HungarianAlgorithm.java

Solves an assignment problem really fast. Benchmarked against other JS solutions, a 1000x1000 matrix took about 26 seconds. With this, it takes 2 seconds.

  • The primary speed up comes from using the O(n^3) algorithm instead of the O(n^4) algorithm that you probably use when you solve by hand.
  • Additionally, it reduces the search space by removing rows that have no feasible column match.
  • For max speed, make sure your BIG_M is <= 2^30 (otherwise the optimizing compiler bails out because it has to rewrap the function in a double)

##Installation npm install hungarian-on3

##How to use

var hungarian = require('./hungarian-on3');
var data = [[400, 150, 400],[400, 450, 600],[300, 225, 300]];
var results = hungarian(data);
//results: [[0, 1], [1, 0], [2, 2]]

##License MIT

Keywords

Hungarian

FAQs

Package last updated on 19 Sep 2015

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts