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

Answer 3

There are cases where Amir's code fails.

Consider the following m1:

 0  0  1

 0  1  1

 1  0  1

The best solution is to draw vertical lines in the first two columns.

Amir's code would give the following m2:

-2 -2  0

 2  0  0

 0  2  0

And the result would draw the two vertical lines AS WELL AS a line in the first row.

It seems to me the problem is the tie-breaking case:

return vertical > horizontal ? vertical : horizontal * -1;

Because of the way the code is written, the very similar m1 will NOT fail:

 0  1  1

 1  0  1

 0  0  1

Where the first row is moved to the bottom, because the clearing function will clear the -2 values from m2 before those cells are reached. In the first case, the -2 values are hit first, so a horizontal line is drawn through the first row.

I've been working a little through this, and this is what I have. In the case of a tie, do not set any value and do not draw a line through those cells. This covers the case of the matrix I mentioned above, we are done at this step.

Clearly, there are situations where there will remain 0s that are uncovered. Below is another example of a matrix that will fail in Amir's method (m1):

 0 0 1 1 1
 0 1 0 1 1
 0 1 1 0 1
 1 1 0 0 1
 1 1 1 1 1

The optimal solution is four lines, e.g. the first four columns.

Amir's method gives m2:

 3 -2  0  0  0
 3  0 -2  0  0
 3  0  0 -2  0
 0  0 -2 -2  0
 0  0  0  0  0

Which will draw lines at the first four rows and the first column (an incorrect solution, giving 5 lines). Again, the tie-breaker case is the issue. We solve this by not setting a value for the ties, and iterating the procedure.

If we ignore the ties we get an m2:

 3 -2  0  0  0
 3  0  0  0  0
 3  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

This leads to covering only the first row and the first column. We then take out the 0s that are covered to give new m1:

 1 1 1 1 1
 1 1 0 1 1
 1 1 1 0 1
 1 1 0 0 1
 1 1 1 1 1

Then we keep repeating the procedure (ignoring ties) until we reach a solution. Repeat for a new m2:

 0  0  0  0  0
 0  0  2  0  0
 0  0  0  2  0
 0  0  0  0  0
 0  0  0  0  0

Which leads to two vertical lines through the second and third columns. All 0s are now covered, needing only four lines (this is an alternative to lining the first four columns). The above matrix only needs 2 iterations, and I imagine most of these cases will need only two iterations unless there are sets of ties nested within sets of ties. I tried to come up with one, but it became difficult to manage.

Sadly, this is not good enough, because there will be cases that will remain tied forever. Particularly, in cases where there is a 'disjoint set of tied cells'. Not sure how else to describe this except to draw the following two examples:

 0 0 1 1
 0 1 1 1
 1 0 1 1
 1 1 1 0

or

 0 0 1 1 1
 0 1 1 1 1
 1 0 1 1 1
 1 1 1 0 0
 1 1 1 0 0

The upper-left 3x3 sub-matrices in these two examples are identical to my original example, I have added 1 or 2 rows/cols to that example at the bottom and right. The only newly added zeros are where the new rows and columns cross. Describing for clarity.

With the iterative method I described, these matrices will be caught in an infinite loop. The zeros will always remain tied (col-count vs row-count). At this point, it does make sense to just arbitrarily choose a direction in the case of a tie, at least from what I can imagine.

The only issue I'm running into is setting up the stopping criteria for the loop. I can't assume that 2 iterations is enough (or any n), but I also can't figure out how to detect if a matrix has only infinite loops left within it. I'm still not sure how to describe these disjoint-tied-sets computationally.

Here is the code to do what I have come up with so far (in MATLAB script):

function [Lines, AllRows, AllCols] = FindMinLines(InMat)

%The following code finds the minimum set of lines (rows and columns)
%required to cover all of the true-valued cells in a matrix. If using for
%the Hungarian problem where 'true-values' are equal to zero, make the
%necessary changes. This code is not complete, since it will be caught in 
%an infinite loop in the case of disjoint-tied-sets

%If passing in a matrix where 0s are the cells of interest, uncomment the
%next line
%InMat = InMat == 0;

%Assume square matrix
Count = length(InMat);
Lines = zeros(Count);

%while there are any 'true' values not covered by lines

while any(any(~Lines & InMat))
    %Calculate row-wise and col-wise totals of 'trues' not-already-covered
    HorzCount = repmat(sum(~Lines & InMat, 2), 1, Count).*(~Lines & InMat);
    VertCount = repmat(sum(~Lines & InMat, 1), Count, 1).*(~Lines & InMat);

    %Calculate for each cell the difference between row-wise and col-wise
    %counts. I.e. row-oriented cells will have a negative number, col-oriented
    %cells will have a positive numbers, ties and 'non-trues' will be 0.
    %Non-zero values indicate lines to be drawn where orientation is determined
    %by sign. 
    DiffCounts = VertCount - HorzCount;

    %find the row and col indices of the lines
    HorzIdx = any(DiffCounts < 0, 2);
    VertIdx = any(DiffCounts > 0, 1);

    %Set the horizontal and vertical indices of the Lines matrix to true
    Lines(HorzIdx, :) = true;
    Lines(:, VertIdx) = true;
end

%compute index numbers to be returned. 
AllRows = [find(HorzIdx); find(DisjTiedRows)];
AllCols = find(VertIdx);

end

Answer 4

Step 5: The drawing of line in the matrix is evaluated diagonally with a maximum evaluations of the length of the matrix.

Based on http://www.wikihow.com/Use-the-Hungarian-Algorithm with Steps 1 - 8 only.

Run code snippet and see results in console

Console Output

horizontal line (row): {"0":0,"2":2,"4":4}
vertical line (column): {"2":2}

Step 5: 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  

Smallest number in uncovered matrix: 1
Step 6: Matrix
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

JSFiddle: http://jsfiddle.net/jjcosare/6Lpz5gt9/2/

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

var inputMatrix = [
  [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 inputMatrix = [
//      [10, 19, 8, 15],
//      [10, 18, 7, 17],
//      [13, 16, 9, 14],
//      [12, 19, 8, 18],
//      [14, 17, 10, 19]
//    ];

var matrix = inputMatrix;
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++) {
        currentNumber = matrix[i][j];
        largestNumberInMatrix = (largestNumberInMatrix > currentNumber) ?
          largestNumberInMatrix : currentNumber;
      }
    }
    return largestNumberInMatrix;
  }
}

HungarianAlgorithm.step3 = function() {
  var smallestNumberInRow = 0;
  var currentNumber = 0;

  for (var i = 0; i < matrix.length; i++) {
    smallestNumberInRow = getSmallestNumberInRow(matrix, i);
    console.log("Smallest number in row[" + i + "]: " + smallestNumberInRow);
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[i][j];
      matrix[i][j] = currentNumber - smallestNumberInRow;
    }
  }

  HungarianAlgorithm.step1(3);

  function getSmallestNumberInRow(matrix, rowIndex) {
    var smallestNumberInRow = matrix[rowIndex][0];
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      smallestNumberInRow = (smallestNumberInRow < currentNumber) ?
        smallestNumberInRow : currentNumber;
    }
    return smallestNumberInRow;
  }
}

HungarianAlgorithm.step4 = function() {
  var smallestNumberInColumn = 0;
  var currentNumber = 0;

  for (var i = 0; i < matrix.length; i++) {
    smallestNumberInColumn = getSmallestNumberInColumn(matrix, i);
    console.log("Smallest number in column[" + i + "]: " + smallestNumberInColumn);
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[j][i];
      matrix[j][i] = currentNumber - smallestNumberInColumn;
    }
  }

  HungarianAlgorithm.step1(4);

  function getSmallestNumberInColumn(matrix, columnIndex) {
    var smallestNumberInColumn = matrix[0][columnIndex];
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      smallestNumberInColumn = (smallestNumberInColumn < currentNumber) ?
        smallestNumberInColumn : currentNumber;
    }
    return smallestNumberInColumn;
  }
}

var rowLine = {};
var columnLine = {};
HungarianAlgorithm.step5 = function() {
  var zeroNumberCountRow = 0;
  var zeroNumberCountColumn = 0;

  rowLine = {};
  columnLine = {};
  for (var i = 0; i < matrix.length; i++) {
    zeroNumberCountRow = getZeroNumberCountInRow(matrix, i);
    zeroNumberCountColumn = getZeroNumberCountInColumn(matrix, i);
    if (zeroNumberCountRow > zeroNumberCountColumn) {
      rowLine[i] = i;
      if (zeroNumberCountColumn > 1) {
        columnLine[i] = i;
      }
    } else if (zeroNumberCountRow < zeroNumberCountColumn) {
      columnLine[i] = i;
      if (zeroNumberCountRow > 1) {
        rowLine[i] = i;
      }
    } else {
      if ((zeroNumberCountRow + zeroNumberCountColumn) > 2) {
        rowLine[i] = i;
        columnLine[i] = i;
      }
    }
  }

  var zeroCount = 0;
  for (var i in columnLine) {
    zeroCount = getZeroNumberCountInColumnLine(matrix, columnLine[i], rowLine);
    if (zeroCount == 0) {
      delete columnLine[i];
    }
  }
  for (var i in rowLine) {
    zeroCount = getZeroNumberCountInRowLine(matrix, rowLine[i], columnLine);
    if (zeroCount == 0) {
      delete rowLine[i];
    }
  }

  console.log("horizontal line (row): " + JSON.stringify(rowLine));
  console.log("vertical line (column): " + JSON.stringify(columnLine));

  HungarianAlgorithm.step1(5);

  //if ((Object.keys(rowLine).length + Object.keys(columnLine).length) == matrix.length) {
    // TODO:
    // HungarianAlgorithm.step9();
  //} else {
  //  HungarianAlgorithm.step6();
  //  HungarianAlgorithm.step7();
  //  HungarianAlgorithm.step8();
  //}

  function getZeroNumberCountInColumnLine(matrix, columnIndex, rowLine) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      if (currentNumber == 0 && !(rowLine[i] == i)) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }

  function getZeroNumberCountInRowLine(matrix, rowIndex, columnLine) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      if (currentNumber == 0 && !(columnLine[i] == i)) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }

  function getZeroNumberCountInColumn(matrix, columnIndex) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      if (currentNumber == 0) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }

  function getZeroNumberCountInRow(matrix, rowIndex) {
    var zeroNumberCount = 0;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      if (currentNumber == 0) {
        zeroNumberCount++
      }
    }
    return zeroNumberCount;
  }
}

HungarianAlgorithm.step6 = function() {
  var smallestNumberInUncoveredMatrix = getSmallestNumberInUncoveredMatrix(matrix, rowLine, columnLine);
  console.log("Smallest number in uncovered matrix: " + smallestNumberInUncoveredMatrix);

  var columnIndex = 0;
  for (var i in columnLine) {
    columnIndex = columnLine[i];
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[i][columnIndex];
      //matrix[i][columnIndex] = currentNumber + smallestNumberInUncoveredMatrix;
      matrix[i][columnIndex] = "x";
    }
  }

  var rowIndex = 0;
  for (var i in rowLine) {
    rowIndex = rowLine[i];
    for (var i = 0; i < matrix.length; i++) {
      currentNumber = matrix[rowIndex][i];
      //matrix[rowIndex][i] = currentNumber + smallestNumberInUncoveredMatrix;
      matrix[rowIndex][i] = "x";
    }
  }

  HungarianAlgorithm.step1(6);

  function getSmallestNumberInUncoveredMatrix(matrix, rowLine, columnLine) {
    var smallestNumberInUncoveredMatrix = null;;
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      if (rowLine[i]) {
        continue;
      }
      for (var j = 0; j < matrix[i].length; j++) {
        if (columnLine[j]) {
          continue;
        }

        currentNumber = matrix[i][j];
        if (!smallestNumberInUncoveredMatrix) {
          smallestNumberInUncoveredMatrix = currentNumber;
        }

        smallestNumberInUncoveredMatrix =
          (smallestNumberInUncoveredMatrix < currentNumber) ?
          smallestNumberInUncoveredMatrix : currentNumber;
      }
    }
    return smallestNumberInUncoveredMatrix;
  }
}

HungarianAlgorithm.step7 = function() {
  var smallestNumberInMatrix = getSmallestNumberInMatrix(matrix);
  console.log("Smallest number in matrix: " + smallestNumberInMatrix);

  var currentNumber = 0;
  for (var i = 0; i < matrix.length; i++) {
    for (var j = 0; j < matrix[i].length; j++) {
      currentNumber = matrix[j][i];
      matrix[j][i] = currentNumber - smallestNumberInMatrix;
    }
  }

  HungarianAlgorithm.step1(7);

  function getSmallestNumberInMatrix(matrix) {
    var smallestNumberInMatrix = matrix[0][0];
    var currentNumber = 0;
    for (var i = 0; i < matrix.length; i++) {
      for (var j = 0; j < matrix[i].length; j++) {
        currentNumber = matrix[i][j];
        smallestNumberInMatrix = (smallestNumberInMatrix < currentNumber) ?
          smallestNumberInMatrix : currentNumber;
      }
    }
    return smallestNumberInMatrix;
  }
}

HungarianAlgorithm.step8 = function() {
  console.log("Step 8: Covering zeroes with Step 5 - 8 until Step 9 is reached");
  HungarianAlgorithm.step5();
}

HungarianAlgorithm.step9 = function(){
  console.log("Step 9...");
}


HungarianAlgorithm.step1(1);
HungarianAlgorithm.step2();
HungarianAlgorithm.step3();
HungarianAlgorithm.step4();
HungarianAlgorithm.step5();
HungarianAlgorithm.step6();

Answer 5

Do the assignment using the steps mentioned below:

• assign a row if it has only one 0, else skip the row temporarily
• cross out the 0's in the assigned column
• Do the same for every column

---

After doing the assignment using the above steps, follow the steps below to get the minimum number of lines which cover all the 0's

• step 1 - Tick an unassigned row
• step 2 - If a ticked row has a 0, then tick the corresponding column
• step 3 - If a ticked column has an assignment, then tick the corresponding row
• step 4 - Repeat steps 2 and 3, till no more ticking is possible
• step 5 - Draw lines through un-ticked rows and ticked columns

---

For your case: (0-indexing for rows and columns)

• skip row 0, as it has two 0's
• assign row 1, and cross out all the 0's in column 2
• skip row 2, as it has two uncrossed 0's
• skip row 3, as it has no uncrossed 0
• skip row 4, as it has 2 uncrossed 0's

---

• assign column 0
• skip column 1 as it has two uncrossed 0's (in row-2 and row-4)
• skip column 2, as it has an already assigned 0
• assign column 3,and cross out the 0 in row 2
• assign column 4, and cross out the 0 in row 4
• assigned 0's are shown by '_' and 'x' shows crossed out 0's

---

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

• The matrix looks like the one shown above after doing the assignments

---

Now follow the 5 steps mentioned above to get the minimum number of lines that cover all the 0's

• Tick row 3 as it is not assigned yet
• Since row 3 has a 0 in column 2, tick column 2
• Since column 2 has an assignment in row 1, tick row 1
• Now draw lines through un-ticked rows (i.e. row 0,2,4) and ticked columns(i.e. column 2)
• These 4 lines will cover all the 0's

---

Hope this helps:)

---

PS : For cases where no initial assignment is possible due to multiple 0's in each row and column, this could be handled by taking one arbitrary assignment (For the cases where multiple 0's are present in each row and column, it is very likely that more than one possible assignment would result in an optimal solution)

Answer 6

@CMPS answer fails on quite a few graphs. I think I have implemented a solution which solves the problem.

I followed the Wikipedia article on the Hungarian algorithm and I made an implementation that seems to work all the time. From Wikipedia, here is a the method to draw the minimum number of lines:

First, assign as many tasks as possible. Mark all rows having no assignments. Mark all (unmarked) columns having zeros in newly marked row(s). Mark all rows having assignments in newly marked columns. Repeat for all non-assigned rows.

Here is my Ruby implementation:

def draw_lines grid
    #copies the array    
    marking_grid = grid.map { |a| a.dup }

    marked_rows = Array.new
    marked_cols = Array.new

    while there_is_zero(marking_grid) do 
        marking_grid = grid.map { |a| a.dup }

        marked_cols.each do |col|
            cross_out(marking_grid,nil, col)
        end

        marked = assignment(grid, marking_grid)    
        marked_rows = marked[0]
        marked_cols.concat(marked[1]).uniq!

        marking_grid = grid.map { |a| a.dup }

        marking_grid.length.times do |row|
            if !(marked_rows.include? row) then
                cross_out(marking_grid,row, nil)
            end
        end

        marked_cols.each do |col|
            cross_out(marking_grid,nil, col)
        end

    end


    lines = Array.new

    marked_cols.each do |index|
        lines.push(["column", index])
    end
    grid.each_index do |index|
        if !(marked_rows.include? index) then
            lines.push(["row", index])
        end
    end
    return lines
end


def there_is_zero grid
    grid.each_with_index do |row|
        row.each_with_index do |value|
            if value == 0 then
                return true
            end
        end
    end
    return false
end

def assignment grid, marking_grid 
    marking_grid.each_index do |row_index|
        first_zero = marking_grid[row_index].index(0)
        #if there is no zero go to next row
        if first_zero.nil? then
            next        
        else
            cross_out(marking_grid, row_index, first_zero)
            marking_grid[row_index][first_zero] = "*"
        end
    end

    return mark(grid, marking_grid)
end


def mark grid, marking_grid, marked_rows = Array.new, marked_cols = Array.new
    marking_grid.each_with_index do |row, row_index|
        selected_assignment = row.index("*")
        if selected_assignment.nil? then
            marked_rows.push(row_index)
        end
    end

    marked_rows.each do |index|
        grid[index].each_with_index do |cost, col_index|
            if cost == 0 then
                marked_cols.push(col_index)    
            end
        end
    end
    marked_cols = marked_cols.uniq

    marked_cols.each do |col_index|
        marking_grid.each_with_index do |row, row_index|
            if row[col_index] == "*" then
                marked_rows.push(row_index)    
            end
        end
    end

    return [marked_rows, marked_cols]
end


def cross_out(marking_grid, row, col)
    if col != nil then
        marking_grid.each_index do |i|
            marking_grid[i][col] = "X"    
        end
    end
    if row != nil then
        marking_grid[row].map! {|i| "X"} 
    end
end

grid = [
    [0,0,1,0],
    [0,0,1,0],
    [0,1,1,1],
    [0,1,1,1],
]

p draw_lines(grid)

Answer 7

Best Option

I found a performant and optimized algorithm. I specifically created a Github repository about this. You can find Info, Codes, Documentations, Benchmarks and there. I implemented it in C++, JavaScript and going to implement other versions.

It's rather complex yet. but I can elaborate a little.

As I said in readme of the repository:

This algorithm doesn't have anything to do about Hungarian Algorithm. It's just an algorithm to find the minimum amount of lines in a 2-Dimensional matrix!

Step 1

Loop through input matrix and count the zeros and collect necessary information about it.

• The power matrix is a helper which indicates the number of zeros in each column or row.
• The line matrix is a helper which indicates where lines are and where not.
• The crosses matrix is a helper which contains every cross lines on a specific line.
• The sides is a pair of numbers that indicates the count of rows and columns which contain a zero!

Step 2

In the next step we loop through matrix but from both directions (horizontal and vertical). Using a for main axis can be 0: row and 1:column.

first we need to find two weakest cross lines. Weak means containing less zeros!

Now we have to choose!

1. If the weakest cross power was 1 or sum of weakest pair cross is less than current line: Draw Current Line
2. If power of current line is 1 so probably the cross line is better:Draw Cross Line
3. If we are in second axis which means we don't get back and should not leave any zeros without line:

Draw the line in direction which less lines are needed!

In every step just check and end the progress if:

• The lines count reach the shortest direction power!
• Any of sides shrinks to zero!

Notice: When a column crosses a row on a zero the power would be at least 1 because of the zero in the cross!

Note: matrix is the variable which contains your matrix!

long len[2];
len[0] = matrix.size();
len[1] = matrix[0].size();
powers[0] = iVec(matrix.size(), 0);
powers[1] = iVec(matrix.size(), 1);

crosses[0] = Matrix::create(len[0], 0, 0);
crosses[1] = Matrix::create(len[1], 0, 0);

crosses[0] = Matrix::create(len[0], 0, 0);
crosses[1] = Matrix::create(len[1], 0, 0);

lines[0] = bVec(len[0], false);
lines[1] = bVec(len[1], false);

minimum = 0;

auto lastRow = len[0] - 1;
sides[0] = 0;
sides[1] = 1;

// Step 1
for (auto row = 0; row < len[0]; row++) {
    for (auto col = 0; col < len[1]; col++) {
        if (matrix[row][col] == 0) {
            powers[0][row]++;
            powers[1][col]++;
            crosses[0][row].push_back(col);
            crosses[1][col].push_back(row);
        }
        if (row == lastRow) {
            if (powers[1][col])
                sides[1]++;
        }
    }
    if (powers[0][row])
        sides[0]++;
}
// LongSide
int ls = (sides[1] > sides[0]);
// ShortSide
int ss = !ls;
// Maximum Output
int maximum = sides[ss];
// OppositeMinimum: a pair of minimum cross powers in a line
int om[2];
// OppositePower: Sum of opposite power
int op;
// LineCrosses: crosses in a line
iVec &lc = crosses[0][0];
// Cross axis ID
int cross;
// CrossPower: power of the current cross
int cp;
// MainPower: power of the current cross
int mp;
// Determines if more zeros available
bool more = true;
for (int main = 0; main < 2 && more; main++) {
    cross = !main;
    for (int i = 0; i < len[main] && more; i++) {
        mp = powers[main][i];
        if (mp == 0) continue;
        lc = crosses[main][i];
        om[0] = maximum;
        om[1] = maximum;
        op = 0;
        if (mp > 1) {
            for (int j = 0; j < lc.size(); j++) {
                if (!lines[cross][lc[j]]) {
                    cp = powers[cross][lc[j]];
                    op += cp;
                    if (om[0] >= cp) {
                        om[1] = om[0];
                        om[0] = cp;
                    } else if (om[1] >= cp) {
                        om[1] = cp;
                    }
                }
            }
        }
        if (om[0] == 1 || (om[0] + om[1]) <= mp) {
            more = line(main, i);
        } else if (mp == 1) {
            more = crossLines(main, i);
        } else if (main == 1) {
            if (sides[main] < sides[cross]) {
                more = line(main, i);
            } else {
                more = crossLines(main, i);
            }
        }
        if (minimum >= maximum) {
            minimum = maximum;
            more = false;
        }
    }
}
if (minimum == 0) minimum = maximum;
std::cout << minimum;

I tested the algorithm against an optimized brute force and find amazing results. You can check benchmark results in repository.

Answer 8

You can find a step-by-step algorithm, complete with proof that it works, in Munkres's paper Algorithms for the assignment and transportation problems . In particular look at page 33, steps 1-3. Each zero of the matrix can be starred or primed, as well as being covered by a horizontal or vertical line.

To initialize, go through each zero in some order. If a zero has no other starred zero in its row or column, star it. In your example, going through the zeroes in the natural order we get

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

Then cover every column containing a starred zero. This will cover columns 1,2,3 and 5 in the above matrix (indexing from 1). Next comes the main loop.

1. Step 1: Choose a non-covered zero and prime it. If there is no starred zero in its row, go to step 2. Otherwise, let Z be the starred zero in its row. Cover the row and uncover the column of Z. [In the above example, this would remove the vertical cover of the second row and add a horizontal cover to the fourth row.] Repeat for all uncovered zeroes. [In our example, we are done. The algorithm produced vertical lines covering columns 1,3,5 and a horizontal line covering row 3.]
2. Step 2: This is the most complicated step, but it's actually not that hard. Let Z0 be the unique uncovered primed zero. There is a sequence of starred and primed zeroes (possibly with only one element) starting from Z0 defined as follows. Z1 is a starred 0 in Z0's column (if there isn't one, the sequence stops here.) Then Z2 is a primed 0 in Z1's row, etc. Continue until the sequence stops at a primed zero Z_2k. Now unstar each starred zero of this sequence, and star each primed zero of the sequence. Erase all the primes, uncover every row, and cover every column containing a starred zero. If all columns are covered, we are done. Otherwise return to step 1.