Hungarian Algorithm

http://www.wikihow.com/Use-the-Hungarian-Algorithm

by Jessie James Cosare

JavaScript

// http://www.wikihow.com/Use-the-Hungarian-Algorithm

var matrix = [
    [0, 1, 0, 1, 1]
    ,[1, 1, 0, 1, 1]
    ,[1, 0, 0, 0, 1]
    ,[1, 1, 0, 1, 1]
    ,[1, 0, 0, 1, 0]
];

//var matrix = [
//      [10, 19, 8, 15],
//      [10, 18, 7, 17],
//      [13, 16, 9, 14],
//      [12, 19, 8, 18],
//      [14, 17, 10, 19]
//    ];

var HungarianAlgorithm = {};

HungarianAlgorithm.step1 = function(stepNumber){
    
    console.log("Step "+ stepNumber +": Matrix");
    
    var currentNumber = 0;
    for(var i = 0; i < matrix.length; i++){
        var sb = "";
        for(var j = 0; j < matrix[i].length; j++){
            currentNumber = matrix[i][j];
            sb += currentNumber + "  ";
        }
        console.log(sb);
    }
}

HungarianAlgorithm.step2 = function(){
    var largestNumberInMatrix = getLargestNumberInMatrix(matrix);
    var rowLength = matrix.length;
    var columnLength = matrix[0].length;
    var dummyMatrixToAdd = 0;
    var isAddColumn = rowLength > columnLength;
    var isAddRow = columnLength > rowLength;
    
    if(isAddColumn){
        dummyMatrixToAdd = rowLength - columnLength;
        for(var i = 0; i < rowLength; i++){
            for(var j = columnLength; j < (columnLength+dummyMatrixToAdd); j++){
                matrix[i][j] = largestNumberInMatrix;
            }
        }
    }else if(isAddRow){
        dummyMatrixToAdd = columnLength - rowLength;
        for(var i = rowLength; i < (rowLength+dummyMatrixToAdd); i++){
            matrix[i] = [];
            for(var j = 0; j < columnLength; j++){
                matrix[i][j] = largestNumberInMatrix;
            }
        }
    }
    
    HungarianAlgorithm.step1(2);
    console.log("Largest number in matrix: "+ largestNumberInMatrix);  
    
    function getLargestNumberInMatrix(matrix){
        var largestNumberInMatrix = 0;
        var currentNumber = 0;
        for(var i = 0; i < matrix.length; i++){
            for(var j = 0; j < matrix[i].length; j++){
               ...