Ayrton Senna
Reputation: 3835
Hungarian Algorithm: How to cover 0 elements with minimum lines?
I am trying to implement the Hungarian algorithm in Java. I have an NxN cost matrix. I am following this guide step by step. So I have the costMatrix[N][N] and 2 arrays to track covered rows and covered cols - rowCover[N], rowColumn[N] (1 means covered, 0 means uncovered)
How can I cover the 0s with the minimum number of lines? Can anyone point me in the right direction?
Any help/suggestion would be appreciated.
Upvotes: 14
Views: 8438
Answers (3)
ToxicAbe
Reputation: 303
This is an improvement on @higuaro's answer, but in Swift (works for
[[0,94,2,91,57,0,115,2,99],[113,19,7,32,42,13,0,35,16],[109,11,31,56,38,29,16,31,0],[81,51,39,0,10,37,24,67,40],[94,0,34,59,23,42,27,30,11],[71,37,39,0,0,47,32,71,48],[71,41,43,4,0,43,28,71,44],[80,110,0,153,137,0,113,0,97],[0,94,0,89,57,8,121,0,105]]
):
func modifiedGetMinLines(_ matrix: [[Int]]) -> Set<Line> { // O(N^4)
// Using the algorithm found here - https://www.youtube.com/watch?v=rrfFTdO2Z7I
func drawLinesWhileIsolatedZerosExist(_ matrix: inout [[Int]]) -> Set<Line> { // O(N^3)
let N = matrix.count
var lines: Set<Line> = []
var unprocessedTableChange = true
while unprocessedTableChange { // While loop occurs 2N-1 times max!...each time a line in a matrix must be crossed out to continue
unprocessedTableChange = false
for i in 0..<N { // rows
var zeroCount = 0
var columnOfLastZero = -1
for j in 0..<N {
if matrix[i][j] == 0 {
zeroCount += 1
columnOfLastZero = j
}
}
if zeroCount == 1 {
unprocessedTableChange = true
var selectedCol = Line(columnOfLastZero, .VERTICAL)
for i in 0..<N {
if matrix[i][columnOfLastZero] == 0 {
selectedCol.coord.insert(i)
}
matrix[i][columnOfLastZero] = -1 // Cross line out
}
lines.insert(selectedCol)
}
}
for i in 0..<N { // columns
var zeroCount = 0
var rowOfLastZero = -1
for j in 0..<N {
if matrix[j][i] == 0 {
zeroCount += 1
rowOfLastZero = j
}
}
if zeroCount == 1 {
unprocessedTableChange = true
var selectedRow = Line(rowOfLastZero, .HORIZONTAL)
for i in 0..<N {
if matrix[rowOfLastZero][i] == 0 {
selectedRow.coord.insert(i)
}
matrix[rowOfLastZero][i] = -1 // Cross line out
}
lines.insert(selectedRow)
}
}
}
return lines
}
func zerosToProcessExist(_ array: [Int]) -> Bool { // O(N)
for e in array {
if e > 0 { return true }
}
return false
}
var matrix = matrix
let N = matrix.count
var lines: Set<Line> = drawLinesWhileIsolatedZerosExist(&matrix) // O(N^3)
var zerosPerRow = Array(repeating: 0, count: N)
var zerosPerCol = Array(repeating: 0, count: N)
for i in 0..<N { // O(N^2)
for j in 0..<N {
if matrix[i][j] == 0 {
zerosPerRow[i] += 1
zerosPerCol[j] += 1
}
}
}
while zerosToProcessExist(zerosPerRow) || zerosToProcessExist(zerosPerCol) { // While loop occurs 2N-1 times max!...each time a line in a matrix must be crossed out to continue
var max = 0
var lineWithMostZeros: Line?
var linesWithMaxZeros: Set<Line> = []
for i in 0..<N { // O(N)
if zerosPerRow[i] > max {
linesWithMaxZeros = []
linesWithMaxZeros.insert(Line(i, LineType.HORIZONTAL))
max = zerosPerRow[i]
} else if zerosPerRow[i] == max && max > 0 {
linesWithMaxZeros.insert(Line(i, LineType.HORIZONTAL))
}
if zerosPerCol[i] > max {
linesWithMaxZeros = []
linesWithMaxZeros.insert(Line(i, LineType.VERTICAL))
max = zerosPerCol[i]
} else if zerosPerCol[i] == max && max > 0 {
linesWithMaxZeros.insert(Line(i, LineType.VERTICAL))
}
}
if linesWithMaxZeros.count == 1 {
lineWithMostZeros = linesWithMaxZeros.first
} else {
var minScore = Int.max
var minScoreLine: Line?
for l in linesWithMaxZeros {
var score = 0
if l.isHorizontal() {
for j in 0..<N {
if matrix[l.lineIndex][j] == 0 {
for k in 0..<N {
if matrix[k][j] == 0 { score += 1 }
}
}
}
} else {
for j in 0..<N {
if matrix[j][l.lineIndex] == 0 {
for k in 0..<N {
if matrix[j][k] == 0 { score += 1 }
}
}
}
}
if score < minScore {
minScore = score
minScoreLine = l
}
}
lineWithMostZeros = minScoreLine
}
let index = lineWithMostZeros!.lineIndex
var temp: Set<Int> = []
if lineWithMostZeros!.isHorizontal() { // O(N)
zerosPerRow[index] = 0
for j in 0..<N {
if matrix[index][j] == 0 {
zerosPerCol[j] -= 1
temp.insert(j)
}
matrix[index][j] = -1
}
} else {
zerosPerCol[index] = 0
for j in 0..<N {
if matrix[j][index] == 0 {
zerosPerRow[j] -= 1
temp.insert(j)
}
matrix[j][index] = -1
}
}
lineWithMostZeros!.coord = temp
lines.insert(lineWithMostZeros!)
}
return lines
}
Upvotes: 0
CMPS
Reputation: 7769
I know this question has been solved long time ago, but I would like to share my implementation for the step 3 where minimum lines should be drawn in a way that all zeros are covered.
Here's a brief explanation on how my algorithm for this step works:
- Loop on all cells, the cell that has a value zero, we need to draw a line passing by it, and its neighbours
- To know in which direction the line should be drawn, I created a method called maxVH() that will count the zeros vertically vs horizontally, and returns an integer. If the integer is positive, draw a vertical line, else if zero or negative, draw a horizontal line.
- colorNeighbors() method will draw the lines and will count them as well. Moreover, it will place 1 on the elements where the line passes vertically. -1 on the elements where the line passes horizontally. 2 on the elements where 2 intersecting lines passes (horizontal and vertical).
The advantage of having those 3 methods is that we know the elements that are covered twice, we know which elements are covered, and which are not covered. In addition, while drawing the lines, we increment the number of line counter.
For the full implementation of the Hungarian Algorithm + Example: Github
Code + Detailed Comments for step 3:
/**
* Step 3.1
* Loop through all elements, and run colorNeighbors when the element visited is equal to zero
* */
public void coverZeros(){
numLines = 0;
lines = new int[values.length][values.length];
for(int row=0; row<values.length;row++){
for(int col=0; col<values.length;col++){
if(values[row][col] == 0)
colorNeighbors(row, col, maxVH(row, col));
}
}
}
/**
* Step 3.2
* Checks which direction (vertical,horizontal) contains more zeros, every time a zero is found vertically, we increment the result
* and every time a zero is found horizontally, we decrement the result. At the end, result will be negative, zero or positive
* @param row Row index for the target cell
* @param col Column index for the target cell
* @return Positive integer means that the line passing by indexes [row][col] should be vertical, Zero or Negative means that the line passing by indexes [row][col] should be horizontal
* */
private int maxVH(int row, int col){
int result = 0;
for(int i=0; i<values.length;i++){
if(values[i][col] == 0)
result++;
if(values[row][i] == 0)
result--;
}
return result;
}
/**
* Step 3.3
* Color the neighbors of the cell at index [row][col]. To know which direction to draw the lines, we pass maxVH value.
* @param row Row index for the target cell
* @param col Column index for the target cell
* @param maxVH Value return by the maxVH method, positive means the line to draw passing by indexes [row][col] is vertical, negative or zero means the line to draw passing by indexes [row][col] is horizontal
* */
private void colorNeighbors(int row, int col, int maxVH){
if(lines[row][col] == 2) // if cell is colored twice before (intersection cell), don't color it again
return;
if(maxVH > 0 && lines[row][col] == 1) // if cell colored vertically and needs to be recolored vertically, don't color it again (Allowing this step, will color the same line (result won't change), but the num of line will be incremented (wrong value for the num of line drawn))
return;
if(maxVH <= 0 && lines[row][col] == -1) // if cell colored horizontally and needs to be recolored horizontally, don't color it again (Allowing this step, will color the same line (result won't change), but the num of line will be incremented (wrong value for the num of line drawn))
return;
for(int i=0; i<values.length;i++){ // Loop on cell at indexes [row][col] and its neighbors
if(maxVH > 0) // if value of maxVH is positive, color vertically
lines[i][col] = lines[i][col] == -1 || lines[i][col] == 2 ? 2 : 1; // if cell was colored before as horizontal (-1), and now needs to be colored vertical (1), so this cell is an intersection (2). Else if this value was not colored before, color it vertically
else // if value of maxVH is zero or negative color horizontally
lines[row][i] = lines[row][i] == 1 || lines[row][i] == 2 ? 2 : -1; // if cell was colored before as vertical (1), and now needs to be colored horizontal (-1), so this cell is an intersection (2). Else if this value was not colored before, color it horizontally
}
// increment line number
numLines++;
// printMatrix(lines); // Monitor the line draw steps
}//End step 3
Upvotes: 0
dinox0r
Reputation: 16039
Check the 3rd step of the algorithm in the Wikipedia article (section Matrix Interpretation) , they explain a way to compute the minimal amount of lines to cover all the 0's
Update: The following is another way to obtain the minimum number of lines that cover the 0's:
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() {
return rowType;
}
int getLineIndex() {
return lineIndex;
}
boolean isHorizontal() {
return rowType == LineType.HORIZONTAL;
}
}
private static boolean isZero(int[] array) {
for (int e : array) {
if (e != 0) {
return false;
}
}
return true;
}
public static List<Line> getMinLines(int[][] matrix) {
if (matrix.length != matrix[0].length) {
throw new IllegalArgumentException("Matrix should be square!");
}
final int SIZE = matrix.length;
int[] zerosPerRow = new int[SIZE];
int[] zerosPerCol = new int[SIZE];
// Count the number of 0's per row and the number of 0's per column
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (matrix[i][j] == 0) {
zerosPerRow[i]++;
zerosPerCol[j]++;
}
}
}
// There should be at must SIZE lines,
// initialize the list with an initial capacity of SIZE
List<Line> lines = new ArrayList<Line>(SIZE);
LineType lastInsertedLineType = LineType.NONE;
// While there are 0's to count in either rows or colums...
while (!isZero(zerosPerRow) && !isZero(zerosPerCol)) {
// Search the largest count of 0's in both arrays
int max = -1;
Line lineWithMostZeros = null;
for (int i = 0; i < SIZE; i++) {
// If exists another count of 0's equal to "max" but in this one has
// the same direction as the last added line, then replace it with this
//
// The heuristic "fixes" the problem reported by @JustinWyss-Gallifent and @hkrish
if (zerosPerRow[i] > max || (zerosPerRow[i] == max && lastInsertedLineType == LineType.HORIZONTAL)) {
lineWithMostZeros = new Line(i, LineType.HORIZONTAL);
max = zerosPerRow[i];
}
}
for (int i = 0; i < SIZE; i++) {
// Same as above
if (zerosPerCol[i] > max || (zerosPerCol[i] == max && lastInsertedLineType == LineType.VERTICAL)) {
lineWithMostZeros = new Line(i, LineType.VERTICAL);
max = zerosPerCol[i];
}
}
// Delete the 0 count from the line
if (lineWithMostZeros.isHorizontal()) {
zerosPerRow[lineWithMostZeros.getLineIndex()] = 0;
} else {
zerosPerCol[lineWithMostZeros.getLineIndex()] = 0;
}
// Once you've found the line (either horizontal or vertical) with the greater 0's count
// iterate over it's elements and substract the 0's from the 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()) {
for (int j = 0; j < SIZE; j++) {
if (matrix[index][j] == 0) {
zerosPerCol[j]--;
}
}
} else {
for (int j = 0; j < SIZE; j++) {
if (matrix[j][index] == 0) {
zerosPerRow[j]--;
}
}
}
// Add the line to the list of lines
lines.add(lineWithMostZeros);
lastInsertedLineType = lineWithMostZeros.getLineType();
}
return 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);
for (int[][] example : examples) {
List<Line> minLines = getMinLines(example);
System.out.printf("Min num of lines for example 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 be square!");
}
final int SIZE = matrix.length;
System.out.println("Before:");
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
System.out.printf("%d ", matrix[i][j]);
}
System.out.println();
}
for (Line line : lines) {
for (int i = 0; i < 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:");
for (int i = 0; i < SIZE; i++) {
for (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 important part is the getMinLines method, it returns a List with the lines that cover the matrix 0's entries. For the example matrices prints:
Min num of lines for example 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 for example 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 for example 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 this give you a boost, the rest of the Hungarian algorithm shouldn't be hard to implement
Upvotes: 6
Related Questions
- Hungarian Algorithm: finding minimum number of lines to cover zeroes?
- Hungarian algorithm - Last step of selecting 0s from such that each row and column has only one selected
- Hungarian algorithm matching one set to itself
- Minimum number of line segments to cover a bigger line
- Hungarian algorithm dead end
- Hungarian algorithm with multiple assignments
- Cannot solve Hungarian Algorithm
- How can I find the minimum number of lines needed to cover all the zeros in a 2 dimensional array?
- Hungarian Algorithm
- Hungarian algorithm - assign systematically