IO2

HungarianMethod.js

/* 2 dimension arrays */
 var skillMatrix=null;
 var matrix=null;
 //var stars=null;
 /* Single arrays */
 var rCov=[];
 var cCov=[];
 var rows=0;
 var cols=0;
 var dim=0;
 var solutions=0; // "k"
//var formation=[];
//var squad=[];
//FORBIDDEN_VALUE: -999999;

 
 var formation=new Array();
 var squad=new Array();

var v=[],id="",p=0,area=0,cx=0,cy=0,count=0;

function checnum(as)
{
	  var a = as.value;
	
	  for(var x=0; x<a.length; x++)
	  {
	     var ff = a[x];
	     if(isNaN(a) || ff==" ")
	     {
		  a = a.substring(0,(a.length-1));
		  as.value = a;
	     }	
  	   }	
}

function tqe_perc()
{
          $("#output").val("");
	count=$("#input").val();
	if(count=="")
	{
	alert("Introduzca el tama�o de la matriz");
	}
	  else
	   {
	       count=parseFloat(count);//alert(count);
		
	   }
     v = [[0,7.421,12.215,10.201,17.39,1.388,11.228,20.119,16.789,12.31,16.781,68.616],
[7.146,999,6.977,6.721,12.153,11.313,5.991,11.167,11.552,5.951,8.916,63.379],
[12.383,7.305,999,8.779,8.885,16.23,4.42,11.099,4.732,6.769,10.198,61.424],
[6.88,7.595,10.204,999,15.379,8.856,8.488,10.328,10.708,3.803,8.274,66.605],
[16.9,11.821,7.538,13.296,999,20.747,6.197,17.277,10.909,11.396,16.375,55.397],
[4.63,12.051,16.845,12.972,22.02,999,15.858,22.89,21.985,15.08,19.551,73.246],
[11.07,5.992,4.775,7.467,6.484,14.917,999,16.308,9.941,6.307,10.954,58.382],
[17.664,11.432,12.355,10.783,18.195,19.639,11.676,999,8.589,5.904,3.63,70.734],
[18.289,13.21,6.362,11.537,12.202,22.135,11.229,9.328,999,8.568,8.427,64.742],
[11.266,5.722,6.699,4.385,11.589,13.241,5.773,6.702,7.246,999,4.647,62.815],
[15.729,10.186,11.067,8.849,16.907,17.705,10.277,2.288,7.301,4.505,999,69.447],
[68.005,62.926,60.253,64.401,55.805,71.851,57.259,69.992,63.624,62.5,69.09,999]];
	for(var i=0;i<count;i++)
	{
	formation[i]="M"+(i+1);
	}
	 for(var i=0;i<count;i++)
	{
	squad[i]="J"+(i+1);
	}

	

	matrix=v;
	var result=hungarianAlgortithm(formation,squad);
        $("#output").val(result);
}

//=======================
function clearall()
{
	$("#input").val("");
	$("#matrix1").html("");
}

//=======================

var stars=null;
function tabls_creation()
{
	document.getElementById("matrix1").innerHTML = ""; 
        var count=$("#input").val();
            if(count=="") count=0;
	count = parseFloat(count);
       
        if(count>50	)
           {
           alert("Ingrese valor entre 1 a 12");
            }
           else if(count!=0)
	   {	
	  // Declare variables and create the header, footer, and caption.
	  var oTable = document.createElement("TABLE");
	  var oTHead = document.createElement("THEAD");
	  var oTBody = document.createElement("TBODY");
	  var oRow, oCell;
	  var i, j;
		
	  // Declare stock data that would normally be read in from a stock Web site.
	  var heading = new Array();
			
	  heading[0] = "Empleos/Hombre";
         for(var i=1;i<=count;i++)
          {
	  heading[i] = "J"+i;
	  }
	  // Insert the created elements into oTable.
	  oTable.appendChild(oTHead);
	  oTable.appendChild(oTBody);
	  oTable.setAttribute("class","bg4");
	  oTable.setAttribute("align","center");

	  // Insert a row into the header and set its background color.
	  oRow = document.createElement("TR");
	  oTHead.appendChild(oRow);

	  // Create and insert cells into the header row.
	  for (a=0; a<heading.length; a++)
	  {
	    oCell = document.createElement("TH");
	    oCell.innerHTML = heading[a];
	    oRow.appendChild(oCell);
	  }

  	  var idval;
	  var vali;
	  // Insert rows and cells into bodies.
	  for (i=0; i<count; i++)
	  {
	    oRow = document.createElement("TR");
	    oRow.setAttribute("align","center");
	    oTBody.appendChild(oRow);
            oCell = document.createElement("TD");
	    oCell.innerHTML = "M"+(i+1);
	    oRow.appendChild(oCell);
	    for (j=0;j<heading.length-1; j++)
	    {
	      oCell = document.createElement("TD");
	      oCell.innerHTML = "<input type=text size=4 id=i"+i+j+" class='easynumeric'>";
	      oRow.appendChild(oCell);
	    }
	  }
  
	// Insert the table into the document tree.
	var frtb = document.getElementById("matrix1");
	frtb.appendChild(oTable);
     }
     onkeyupValidationClass();
}

function printMatrix() {
  var finalString = "";
  for (var r = 0; r < matrix.length; r++) {
    finalString += matrix[r].join() + "\n";
  }
  console.log("\n\n"+finalString+"\n\n");
}

 function hungarianAlgortithm(squad,formation) {
   init(formation, squad);   
   // Step 1
   matrix = subtractRowMins(matrix);
   printMatrix();
   // Step 2
   findZeros(matrix);
   printMatrix();
   var done = false;
   while (!done) {
     // Step 3
     var covCols = coverColumns(matrix);
     if (covCols > solutions -1) {
       done = true;
     }
     if (!done) {
    // Step 4 (calls Step 5)
       done = coverZeros(matrix);
       while (done) {
         // Step 6
         var smallest = findSmallestUncoveredVal(matrix);
         matrix = uncoverSmallest(smallest, matrix);
         printMatrix();
         done = coverZeros(matrix);
       }
     }
   }
   return getSolution(formation, squad);
 }
 
 function init(formation, squad) {
   cols = squad.length;
   rows = formation.length;
   dim = Math.max(rows, cols);
   solutions = dim;
   skillMatrix = initMatrix(rows, cols);
   matrix = initMatrix(dim, dim);
   stars = initMatrix(dim, dim);
   matrix = loadMatrix(squad, formation, matrix, false);
   skillMatrix = loadMatrix(squad, formation, skillMatrix, false);
 
   rCov = new Array(dim);
   cCov = new Array(dim);
   initArray(cCov, 0); // Zero it out
   initArray(rCov, 0);
 }
 
 function initMatrix(sizeX, sizeY) {
   var matrix = new Array(sizeX);
   for (var i=0; i<sizeX; i++) {
     matrix[i] = new Array(sizeY);
     initArray(matrix[i], 0);
   }
   return matrix;
 }
 
 // Takes an array of positions as a formation.
 // Takes a squad which contains an array of players
 function loadMatrix(squad, formation, matrix, reverse) {
   matrix =v;//loadYourMatrix(squad, formation, matrix); // I've removed my implementation here. Far too much stuff
   if (reverse) {
   // This reverses the matrix.  We need to to create a cost based solution.
//     matrix = reverseMatrix(findMaxValue(matrix), matrix);
     matrix = (findMaxValue(matrix), matrix);   
   }
   return matrix;
 }
 
 function findMaxValue(matrix) {
   var max = 0.0;
   for (var i = 0; i < matrix.length; i ++) {
     for (var j = 0; j < matrix[i].length; j++) {
       if (matrix[i][j] > max) {
         max = matrix[i][j];
       }
     }
   }
   return Number(max);
 }
 
 function reverseMatrix(max, matrix) {
   for (var i = 0; i < matrix.length; i ++) {
     for (var j = 0; j < matrix[i].length; j++) {
       matrix[i][j] = (Number(max) - Number(matrix[i][j])).toFixed(0);
     }
   }
   return matrix;
 }
 
 function subtractRowMins(matrix) {
   for (var i = 0; i < matrix.length; i ++) {
     var min = Number.MAX_VALUE;
     for (var j = 0; j < matrix[i].length; j++) {
       if (matrix[i][j] < min) {
         min = Number(matrix[i][j]);
       }
     }
     for (var k = 0; k < matrix[i].length; k++) {
       matrix[i][k] = matrix[i][k] - min;
     }
   }
  return matrix;
 }
 
  function subtractColMins(matrix) {
   for (var j = 0; j < matrix[0].length; j ++) {
     var min = Number.MAX_VALUE;
     for (var i = 0; i < matrix.length; i++) {
       if (matrix[i][j] < min) {
         min = Number(matrix[i][j]);
       }
     }
     for (var k = 0; k < matrix[0].length; k++) {
       matrix[k][j] = matrix[k][j] - min;
     }
   }
   return matrix;
 }
 
 function findZeros(matrix) {
   for (var i = 0; i < matrix.length; i++) {
     for (var j = 0; j < matrix[i].length; j++) {
       if (matrix[i][j] == 0) {
         if (rCov[i] == 0 && cCov[j] == 0) {
           stars[i][j] = 1;
           cCov[j] = 1;
           rCov[i] = 1;
         }
       }
     }
   }
   // Clear Covers
   initArray(cCov,0);
   initArray(rCov,0);
 }
 
 function initArray(theArray, initVal) {
   for (var i = 0; i < theArray.length; i++) {
     theArray[i] = Number(initVal);
   }
 }
 
 function coverColumns(matrix) {
   var count = 0;
   for (var i=0; i < matrix.length; i++) {
     for (var j=0; j < matrix[i].length; j++) {
       if (stars[i][j] == 1) {
         cCov[j] = 1;
       }
     }
   }
   for (var k=0; k < cCov.length; k++) {
     count = Number(cCov[k]) + Number(count);
   }
   return count;
 }
 
 
 function coverZeros(matrix) {
   var retVal = true;
  var zero = findUncoveredZero(matrix); // Returns a Coords object..
   
   while (zero.row > -1 && retVal == true) {
     stars[zero.row][zero.col] = 2 //Prime it
     var starCol = foundStarInRow(zero.row, matrix);
     if (starCol > -1) {
       rCov[zero.row] = 1;
       cCov[starCol] = 0;
     } else {
       starZeroInRow(zero); // Step 5
       retVal = false;
     }
     if (retVal == true) {
       zero = findUncoveredZero(matrix);
     }
   }
   return retVal;
 }
 
 function findUncoveredZero(matrix) {
   var coords = new HgCoords();
   for (var i=0; i< matrix.length; i++) {
     for (var j=0; j < matrix[i].length; j++) {
       if (matrix[i][j] == 0 && rCov[i] == 0 && cCov[j] == 0) {
         coords.row = i;
         coords.col = j;
         j = matrix[i].length;
         i = matrix.length - 1;
       }
     }
 
   }
   return coords;
 }
 
 function foundStarInRow(zeroRow, matrix) {
   var retVal = -1;
   for (var j = 0; j < matrix[zeroRow].length; j++) {
     if (stars[zeroRow][j] == 1) {
       retVal = j;
       j = matrix[zeroRow].length;
     }
   }
   return retVal;
 }
 
  
 function starZeroInRow(zero) { // Takes a Coords Object
  // log("Step 5: Uncovered Zero:" + zero.row + "," + zero.col, DEBUG );
   var done = false;
   var count = 0;
   var path = initMatrix(dim*2, 2);
 
   path[count][0] = zero.row;
   path[count][1] = zero.col;
   while (!done) {
     var row = findStarInCol(path[count][1]);
     if (row > -1) {
       count++;
       path[count][0] = row;
       path[count][1] = path[count - 1][1];
     } else {
       done = true;
       
     }
     if (!done) {
       var col = findPrimeInRow(path[count][0]);
       count++;
       path[count][0] = path[count - 1][0];
       path[count][1] = col;
     }
   }
   convertPath(path, count);
 
   // Clear Covers
   initArray(cCov,0);
   initArray(rCov,0);
   erasePrimes();
 }
 
  function findStarInCol(col) {
   var retVal = -1;
   for (var i = 0; i < stars.length; i++) {
     if (stars[i][col] == 1) {
       retVal = i;
       i = stars.length;
     }
   }
   return retVal;
 }
 
  function findPrimeInRow(row) {
   var retVal = -1;
   for (var j=0; j< stars[row].length; j++) {
     if (stars[row][j] == 2) {
       retVal = j;
       j = stars[row].length;
     }
   }
   return retVal;
 }
 
  
 function convertPath(path, count) {
   //logMatrix(path, "Step 5: Converting Path.  Count = " + count);
   for (var i=0; i < count+1; i++) {
     var x = path[i][0];
     var y = path[i][1];
     if (stars[x][y] == 1) {
       stars[x][y] = 0;
     } else if (stars[x][y] == 2) {
       stars[x][y] = 1;
     }
   }
 }
 
 function erasePrimes() {
   for (var i=0; i<stars.length; i++) {
     for (var j=0; j < stars[i].length; j++){
       if (stars[i][j] == 2) {
         stars[i][j] = 0;
       }
     }
   }
 }
 
 function findSmallestUncoveredVal(matrix) {
   var min = Number.MAX_VALUE;
   for (var i = 0; i < matrix.length; i++) {
     for (var j = 0; j < matrix[i].length; j++) {
       if (rCov[i] == 0 && cCov[j] == 0) {
         if (min > matrix[i][j]) {
           min = matrix[i][j];
         }
       }
     }
   }
   return min;
 }
 
  
 function uncoverSmallest(smallest, matrix) {
   //log("Uncover Smallest: "+ smallest);
       //logMatrix(matrix, "B4 Smallest uncovered");
 
   for (var i = 0; i < matrix.length; i++) {
     for (var j = 0; j < matrix[i].length; j++) {
       if (rCov[i] == 1) {
         matrix[i][j] += smallest;
       }
       if (cCov[j] == 0) {
         matrix[i][j] -= smallest;
       }
     }
   }
   //logMatrix(matrix, "Smallest uncovered");
   return matrix;
 }
 
 function getSolution(formation, squad) {
   var total = 0;
   var lineup = '';
    // Changed from length of stars, since we must ignore some rows due to padding.
   for (var i = 0; i < rows; i++) {
     for (var j = 0; j < cols; j++) {
       if (stars[i][j] == 1) {
      
         lineup+=getplayer(i,j)+"\n";
       }
     }
   }
   return lineup;
 }

function getplayer(i,j)
{
return formation[i]+" = "+squad[j];
}
function HgCoords() {
 row = -1;
 col = -1;
}