Java Implementation of Hungarian Algorithm - part 1

Please review this implementation of the Hungarian Algorithm. Having gone through the code a few days after I wrote it, then having written some randomly generated test cases for it, it seems to work as intended.

Does this solve the assignment problem as intended, or are there edge cases that I have missed?

Primary Classes

HungarianProblem.java

```
package uk.co.scottdennison.java.lib.algorithms.assignment.hungarian;

import java.math.BigInteger;
import java.util.Optional;

/**
* An implementation of https://en.wikipedia.org/wiki/Hungarian_algorithm.
* Based on
* 1.) 'http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html' - Primary reference.
* 2.) 'http://robotics.stanford.edu/~gerkey/tools/Hungarian.java' - A different implementation of the above which has some optimisations.
* 3.) 'https://www.youtube.com/watch?v=BUGIhEecipE' - Inspiration for initSingularPossibilityStars();
* 4.) 'https://www.youtube.com/watch?v=dQDZNHwuuOY&t=10m9s' - Inspiration for the if condition in reduceMatrix();
*/
public class HungarianProblem {
/*
* Internal point class.
* As it is used internally only with no public access. There are no getters and setters, instead direct member access is used.
*/
private static class Point {
private int row;
private int column;

private Point(int row, int column) {
this.row = row;
this.column = column;
}
}

/**
* The current cell state.
*/
private static enum CellState {
/**
* Neither stared nor primed.
*/
NORMAL,
/**
* Starred. Marks a chosen 'zero' entry in the matrix.
*/
STARRED,
/**
* Primed. Used as part of the augmenting path sub-algorithm.
*/
PRIMED
};

private int width;
private int height;
private int size;
private long[][] originalMatrix;
private long[][] currentMatrix

First of all: I am not a well mathematician, so I can not tell you, if all the cases are considered.

I can only make suggestions regarding your code style.

Basics

An enum in java can only have the values you define in it or null. The check

if (hungarianOperationMode != HungarianOperationMode.MAXIMIZE && hungarianOperationMode != HungarianOperationMode.MINIMIZE) 
        throw new IllegalArgumentException("Unexpected hungarian operation mode.");

could be simplified to

if (hungarianOperationMode == null) 
        throw new IllegalArgumentException("Unexpected hungarian operation mode.");

What I think is terrible code style, is this block of if/else:

if (inputMatrix == null) {
   throw new IllegalArgumentException("The input matrix is null");
} else if (hungarianOperationMode != HungarianOperationMode.MAXIMIZE && hungarianOperationMode != HungarianOperationMode.MINIMIZE) {
    throw new IllegalArgumentException("Unexpected hungarian operation mode.");
} else {
    this.height = inputMatrix.length;
    if (this.height < 1) {
        throw new IllegalArgumentException("The input matrix has no height");
    } else {
         for (int row=0; row<this.height; row++) {
            Long[] inputMatrixRow = inputMatrix[row];
            if (inputMatrixRow == null) {
               throw new IllegalArgumentException("The input matrix has null for row " + row);
            } else {
                int inputMatrixRowLength = inputMatrixRow.length;
                if (row == 0) {
                   this.width = inputMatrixRowLength;
                } else if (this.width != inputMatrixRowLength) {
                   throw new IllegalArgumentException("The input matrix is not rectangular");
                }
            }
       }

All these are only for input validation and I suggest you consider transforming those to using a simplyfied intercepting filter pattern as used in this example

Your input validation could look like this:

List rules = new ArrayList<>();
rules.add( new MatrixNotNullRule () );
rules.add( new MatrixHasHeightRule () );
...
for ( Rule rule : rules )
{
  rule.validate( inputMatrix );
}

where each rule implements the Rule interface:

public interface Rule{

void validate( Long[][] inputMatrix ) throws IllegalArgumentException;

}

and performs a single check:

public class MatrixNotNullRule implements Rule{

  @Override
  public void validate( Long[][] inputMatrix ) throws IllegalArgumentException
  {
     if (inputMatrix == null) {
        throw new IllegalArgumentException("The input matrix is null");
  }
}

Good practice

would be throwing a dedicated exception. Write your own exception and name it something like

HungarianException

or

HungarianOperationException

It may inherit from an IllegalArgumentException or whatever, but I should not be one.

Extract your exception messages

into string constants.

public class MatrixNotNullRule implements Rule{

private static final String MATRIX_NULL = "The input matrix is null";

  @Override
  public void validate( Long[][] inputMatrix ) throwsHungarianException
  {
     if (inputMatrix == null) {
        throw new HungarianException(MATRIX_NULL);
  }
}

Doing the above changes would result in this constructor for the HungarianProblem:

```
/**
* Create the hungarian problem.
* @param inputMatrix The input matrix. It has to be rectangular, but not necessarily square. null entries are allowed to represent 'impossible' entries. The first dimension is the from/agent, and the second dimension is the to/task.
* @param hungarianOperationMode The hungarian operation mode.
*/
public HungarianProblem(Long[][] inputMatrix, HungarianOperationMode hungarianOperationMode) throws HungarianException
{
List rules = new ArrayList<>();
rules.add( new MatrixNotNullRule () );
rules.add( new MatrixHasHeightRule () );
rules.add( new NoNullRowRule () );
rules.add( new MatrixRectangularRule () );
for ( Rule rule : rules )
{
rule.validate( inputMatrix );
}
//Now you can be sure that everything is fine

this.heigth = inputMatrix.length(); //the height
this.width = inputMatrix[0].length(); //each row has the same length according to this SO post: http://stackoverflow.com/questions/21363104/getting-rows-and-columns-count-of-a-2d-array-without-iterating-on-it

// Create all the arrays.
// Note that the internal matrixes are square and have the same width and height, which is the maximum of the width and height supplied.
// The extra rows/columns will be filled with dummy values.
this.size = Math.max(this.width,this.height);
this.originalMatrix = new long[this.size][this.size];
this.currentMatrix = new long[this.size][this.size];
this.impossibleMatrix = new boolean[this.size][this.size];
this.cellStates = new CellState[this.size][this.size];
this.coveredColumns = new boolean[this.size];
this

StackExchange Code Review Q#160934, answer score: 2