Hungarian Algorithm: finding minimum number of lines to cover zeroes?

Question

I am trying to implement the Hungarian Algorithm but I am stuck on the step 5. Basically, given a n X n matrix of numbers, how can I find minimum number of vertical+horizontal lines such that the zeroes in the matrix are covered?

Before someone marks this question as a duplicate of this, the solution mentioned there is incorrect and someone else also ran into the bug in the code posted there.

I am not looking for code but rather the concept by which I can draw these lines...

EDIT: Please do not post the simple (but wrong) greedy algorithm: Given this input:

(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) 

I select, column 2 obviously (0-indexed):

(0, 1, x, 1, 1) (1, 1, x, 1, 1) (1, 0, x, 0, 1) (1, 1, x, 1, 1) (1, 0, x, 1, 0) 

Now I can either select row 2 or col 1 both of which have two "remaining" zeroes. If I select col2, I end up with incorrect solution down this path:

(0, x, x, 1, 1) (1, x, x, 1, 1) (1, x, x, 0, 1) (1, x, x, 1, 1) (1, x, x, 1, 0) 

The correct solution is using 4 lines:

(x, x, x, x, x) (1, 1, x, 1, 1) (x, x, x, x, x) (1, 1, x, 1, 1) (x, x, x, x, x) 

Answer 1

Update

I have implemented the Hungarian Algorithm in the same steps provided by the link you posted: Hungarian algorithm

Here's the files with comments: Github

Algorithm (Improved greedy) for step 3: (This code is very detailed and good for understanding the concept of choosing line to draw: horizontal vs Vertical. But note that this step code is improved in my code in Github)

• Calculate the max number of zeros vertically vs horizontally for each xy position in the input matrix and store the result in a separate array called m2.
• While calculating, if horizontal zeros > vertical zeroes, then the calculated number is converted to negative. (just to distinguish which direction we chose for later use)
• Loop through all elements in the m2 array. If the value is positive, draw a vertical line in array m3, if value is negative, draw an horizontal line in m3

Follow the below example + code to understand more the algorithm:

Create 3 arrays:

• m1: First array, holds the input values
• m2: Second array, holds maxZeroes(vertical,horizontal) at each x,y position
• m3: Third array, holds the final lines (0 index uncovered, 1 index covered)

Create 2 functions:

• hvMax(m1,row,col); returns maximum number of zeroes horizontal or vertical. (Positive number means vertical, negative number means horizontal)
• clearNeighbours(m2, m3,row,col); void method, it will clear the horizontal neighbors if the value at row col indexes is negative, or clear vertical neighbors if positive. Moreover, it will set the line in the m3 array, by flipping the zero bit to 1.

Code

public class Hungarian {     public static void main(String[] args) {         // m1 input values         int[][] m1 = { { 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 } };          // int[][] m1 = { {13,14,0,8},         // {40,0,12,40},         // {6,64,0,66},         // {0,1,90,0}};          // int[][] m1 = { {0,0,100},         // {50,100,0},         // {0,50,50}};          // m2 max(horizontal,vertical) values, with negative number for         // horizontal, positive for vertical         int[][] m2 = new int[m1.length][m1.length];          // m3 where the line are drawen         int[][] m3 = new int[m1.length][m1.length];          // loop on zeroes from the input array, and sotre the max num of zeroes         // in the m2 array         for (int row = 0; row < m1.length; row++) {             for (int col = 0; col < m1.length; col++) {                 if (m1[row][col] == 0)                     m2[row][col] = hvMax(m1, row, col);             }         }          // print m1 array (Given input array)         System.out.println("Given input array");         for (int row = 0; row < m1.length; row++) {             for (int col = 0; col < m1.length; col++) {                 System.out.print(m1[row][col] + "\t");             }             System.out.println();         }          // print m2 array          System.out                 .println("\nm2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical)");         for (int row = 0; row < m1.length; row++) {             for (int col = 0; col < m1.length; col++) {                 System.out.print(m2[row][col] + "\t");             }             System.out.println();         }          // Loop on m2 elements, clear neighbours and draw the lines         for (int row = 0; row < m1.length; row++) {             for (int col = 0; col < m1.length; col++) {                 if (Math.abs(m2[row][col]) > 0) {                     clearNeighbours(m2, m3, row, col);                 }             }         }          // prinit m3 array (Lines array)         System.out.println("\nLines array");         for (int row = 0; row < m1.length; row++) {             for (int col = 0; col < m1.length; col++) {                 System.out.print(m3[row][col] + "\t");             }             System.out.println();         }     }      // max of vertical vs horizontal at index row col     public static int hvMax(int[][] m1, int row, int col) {         int vertical = 0;         int horizontal = 0;          // check horizontal         for (int i = 0; i < m1.length; i++) {             if (m1[row][i] == 0)                 horizontal++;         }          // check vertical         for (int i = 0; i < m1.length; i++) {             if (m1[i][col] == 0)                 vertical++;         }          // negative for horizontal, positive for vertical         return vertical > horizontal ? vertical : horizontal * -1;     }      // clear the neighbors of the picked largest value, the sign will let the     // app decide which direction to clear     public static void clearNeighbours(int[][] m2, int[][] m3, int row, int col) {         // if vertical         if (m2[row][col] > 0) {             for (int i = 0; i < m2.length; i++) {                 if (m2[i][col] > 0)                     m2[i][col] = 0; // clear neigbor                 m3[i][col] = 1; // draw line             }         } else {             for (int i = 0; i < m2.length; i++) {                 if (m2[row][i] < 0)                     m2[row][i] = 0; // clear neigbor                 m3[row][i] = 1; // draw line             }         }          m2[row][col] = 0;         m3[row][col] = 1;     } } 

Output

Given input array 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     m2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical) -2  0   5   0   0    0   0   5   0   0    0   -3  5   -3  0    0   0   5   0   0    0   -3  5   0   -3    Lines array 1   1   1   1   1    0   0   1   0   0    1   1   1   1   1    0   0   1   0   0    1   1   1   1   1    

PS: Your example that you pointed to, will never occur because as you can see the first loop do the calculations by taking the max(horizontal,vertical) and save them in m2. So col1 will not be selected because -3 means draw horizontal line, and -3 was calculated by taking the max between horizontal vs vertical zeros. So at the first iteration at the elements, the program has checked how to draw the lines, on the second iteration, the program draw the lines.

Answer 2

Greedy algorithms may not work for some cases.

Firstly, it is possible reformulate your problem as following: given a bipartite graph, find a minimum vertex cover. In this problem there are 2n nodes, n for rows and n for columns. There is an edge between two nodes if element at the intersection of corresponding column and row is zero. Vertex cover is a set of nodes (rows and columns) such that each edge is incident to some node from that set (each zero is covered by row or column).

This is a well known problem and can be solved in O(n^3) by finding a maximum matching. Check wikipedia for details