java - Hungarian Algorithm: How to cover 0 elements with minimum lines? -

java - Hungarian Algorithm: How to cover 0 elements with minimum lines? -

i trying implement hungarian algorithm in java. have nxn cost matrix. next this guide step step. have costmatrix[n][n] , 2 arrays track covered rows , covered cols - rowcover[n], rowcolumn[n] (1 means covered, 0 means uncovered)

how can cover 0s minimum number of lines? can point me in right direction?

any help/suggestion appreciated.

check 3rd step of algorithm in wikipedia article (section matrix interpretation) , explain way compute minimal amount of lines cover 0's

update: next way obtain minimum number of lines cover 0's:

class="lang-java prettyprint-override">import java.util.arraylist; import java.util.list; public class minlines { enum linetype { none, horizontal, vertical } private static class line { int lineindex; linetype rowtype; line(int lineindex, linetype rowtype) { this.lineindex = lineindex; this.rowtype = rowtype; } linetype getlinetype() { homecoming rowtype; } int getlineindex() { homecoming lineindex; } boolean ishorizontal() { homecoming rowtype == linetype.horizontal; } } private static boolean iszero(int[] array) { (int e : array) { if (e != 0) { homecoming false; } } homecoming true; } public static list<line> getminlines(int[][] matrix) { if (matrix.length != matrix[0].length) { throw new illegalargumentexception("matrix should square!"); } final int size = matrix.length; int[] zerosperrow = new int[size]; int[] zerospercol = new int[size]; // count number of 0's per row , number of 0's per column (int = 0; < size; i++) { (int j = 0; j < size; j++) { if (matrix[i][j] == 0) { zerosperrow[i]++; zerospercol[j]++; } } } // there should @ must size lines, // initialize list initial capacity of size list<line> lines = new arraylist<line>(size); linetype lastinsertedlinetype = linetype.none; // while there 0's count in either rows or colums... while (!iszero(zerosperrow) && !iszero(zerospercol)) { // search largest count of 0's in both arrays int max = -1; line linewithmostzeros = null; (int = 0; < size; i++) { // if exists count of 0's equal "max" in 1 has // same direction lastly added line, replace // // heuristic "fixes" problem reported @justinwyss-gallifent , @hkrish if (zerosperrow[i] > max || (zerosperrow[i] == max && lastinsertedlinetype == linetype.horizontal)) { linewithmostzeros = new line(i, linetype.horizontal); max = zerosperrow[i]; } } (int = 0; < size; i++) { // same above if (zerospercol[i] > max || (zerospercol[i] == max && lastinsertedlinetype == linetype.vertical)) { linewithmostzeros = new line(i, linetype.vertical); max = zerospercol[i]; } } // delete 0 count line if (linewithmostzeros.ishorizontal()) { zerosperrow[linewithmostzeros.getlineindex()] = 0; } else { zerospercol[linewithmostzeros.getlineindex()] = 0; } // 1 time you've found line (either horizontal or vertical) greater 0's count // iterate on it's elements , substract 0's other lines // example: // 0's x col: // [ 0 1 2 3 ] -> 1 // [ 0 2 0 1 ] -> 2 // [ 0 4 3 5 ] -> 1 // [ 0 0 0 7 ] -> 3 // | | | | // v v v v // 0's x row: {4} 1 2 0 // [ x 1 2 3 ] -> 0 // [ x 2 0 1 ] -> 1 // [ x 4 3 5 ] -> 0 // [ x 0 0 7 ] -> 2 // | | | | // v v v v // {0} 1 2 0 int index = linewithmostzeros.getlineindex(); if (linewithmostzeros.ishorizontal()) { (int j = 0; j < size; j++) { if (matrix[index][j] == 0) { zerospercol[j]--; } } } else { (int j = 0; j < size; j++) { if (matrix[j][index] == 0) { zerosperrow[j]--; } } } // add together line list of lines lines.add(linewithmostzeros); lastinsertedlinetype = linewithmostzeros.getlinetype(); } homecoming lines; } public static void main(string... args) { int[][] example1 = { {0, 1, 0, 0, 5}, {1, 0, 3, 4, 5}, {7, 0, 0, 4, 5}, {9, 0, 3, 4, 5}, {3, 0, 3, 4, 5} }; int[][] example2 = { {0, 0, 1, 0}, {0, 1, 1, 0}, {1, 1, 0, 0}, {1, 0, 0, 0}, }; int[][] example3 = { {0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 1, 1, 0, 0}, {0, 1, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0} }; list<int[][]> examples = new arraylist<int[][]>(); examples.add(example1); examples.add(example2); examples.add(example3); (int[][] illustration : examples) { list<line> minlines = getminlines(example); system.out.printf("min num of lines illustration matrix is: %d\n", minlines.size()); printresult(example, minlines); system.out.println(); } } private static void printresult(int[][] matrix, list<line> lines) { if (matrix.length != matrix[0].length) { throw new illegalargumentexception("matrix should square!"); } final int size = matrix.length; system.out.println("before:"); (int = 0; < size; i++) { (int j = 0; j < size; j++) { system.out.printf("%d ", matrix[i][j]); } system.out.println(); } (line line : lines) { (int = 0; < size; i++) { int index = line.getlineindex(); if (line.ishorizontal()) { matrix[index][i] = matrix[index][i] < 0 ? -3 : -1; } else { matrix[i][index] = matrix[i][index] < 0 ? -3 : -2; } } } system.out.println("\nafter:"); (int = 0; < size; i++) { (int j = 0; j < size; j++) { system.out.printf("%s ", matrix[i][j] == -1 ? "-" : (matrix[i][j] == -2 ? "|" : (matrix[i][j] == -3 ? "+" : integer.tostring(matrix[i][j])))); } system.out.println(); } } }

the of import part getminlines method, returns list lines cover matrix 0's entries. illustration matrices prints:

class="lang-none prettyprint-override">min num of lines illustration matrix is: 3 before: 0 1 0 0 5 1 0 3 4 5 7 0 0 4 5 9 0 3 4 5 3 0 3 4 5 after: - + - - - 1 | 3 4 5 - + - - - 9 | 3 4 5 3 | 3 4 5 min num of lines illustration matrix is: 4 before: 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 after: | | | | | | | | | | | | | | | | min num of lines illustration matrix is: 6 before: 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 after: - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

i hopes give boost, rest of hungarian algorithm shouldn't hard implement

java algorithm logic hungarian-algorithm