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.