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<Rule> 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<Rule> 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.coveredRows = new boolean[this.size];
this.path = new Point[(this.size*4)+1];
long maximumValue = Long.MIN_VALUE;
long minimumValue = Long.MAX_VALUE;
// A maximum mode problem can be turned into a minimum mode problem just by negating all the values in the matrix. A lower step will then make sure all values are positive.
long valueModifier = hungarianOperationMode == HungarianOperationMode.MAXIMIZE ? -1 : 1;
// Populate the original and current amtrix
for (int row=0; row<this.size; row++) {
for (int column=0; column<this.size; column++) {
Long value;
if (row < this.height && column < this.width) {
value = inputMatrix[row][column];
} else {
value = null;
}
this.cellStates[row][column] = CellState.NORMAL;
if (value == null) {
this.impossibleMatrix[row][column] = true;
} else {
this.originalMatrix[row][column] = value;
value = Math.multiplyExact(value, valueModifier);
this.currentMatrix[row][column] = value;
if (value > maximumValue) {
maximumValue = value;
}
if (value < minimumValue) {
minimumValue = value;
}
}
}
}
// The convention for the hungarian algorithm is to use the maximum value for dummy values.
// However, in the case where may be missing impossible values in the matrix, this is no longer enough, as it might be possible that the maximum valued entry needs to be used.
// For that valid choice to happen, instead of one of the dummy values being chosen instead, there needs to be a difference between valid maximum values and invalid values.
// Then, to make sure the matrix is fully positive, add one the minimum value.
// Use this newly calculated value and fill in the relevant matrix entries.
long missingValueCurrent = Math.addExact(maximumValue, 1);
long missingValueOriginal = Math.multiplyExact(missingValueCurrent, valueModifier);
for (int row=0; row<this.size; row++) {
for (int column=0; column<this.size; column++) {
if (this.impossibleMatrix[row][column]) {
this.originalMatrix[row][column] = missingValueOriginal;
this.currentMatrix[row][column] = missingValueCurrent;
}
this.currentMatrix[row][column] = Math.subtractExact(this.currentMatrix[row][column], minimumValue);
}
}
}
So far, so good. Next: extract your initialization from the constructor:
/** 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.
* @param size the size of the matrixes
*/
private void init ( int size )
{
this.originalMatrix = new long[size ][size ];
this.currentMatrix = new long[size ][size ];
this.impossibleMatrix = new boolean[size ][size ] ;
this.cellStates = new CellState[size ][size ];
this.coveredColumns = new boolean[size ];
this.coveredRows = new boolean[size ];
this.path = new Point[(size * 4)+1];
}
... and call it in your constructor:
/**
* 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
{
...
this.init( Math.max( this.height, this.width ) );
...
}
Extract some more functionalities into functions, just the same way I did with the init () method and your code will be a lot easier to understand.
Next: extend your HungarianOperationMode to have a private int modifier
/**
* The type of hungarian operation that should be ran.
* @author scott.dennison
*/
public enum HungarianOperationMode {
/**
* Find the minimum valued combination possible.
*/
MINIMIZE( -1l ),
/**
* Find the maximum valued combination possible.
*/
MAXIMIZE( 1l );
private long modifier;
private HungarianOperationMode ( long modifier )
{
this.modifier = modifier;
}
public long getModifier ()
{
return this.modifier;
}
}
so you dont need to write
// A maximum mode problem can be turned into a minimum mode problem just by negating all the values in the matrix. A lower step will then make sure all values are positive.
long valueModifier = hungarianOperationMode == ungarianOperationMode.MAXIMIZE ? -1 : 1;
but can write
hungarianOperationMode.getModifier();
instead, whenever needed.
The new constructor would look something like this:
/**
* 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<Rule> 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
this.init();
// A maximum mode problem can be turned into a minimum mode problem just by negating all the values in the matrix. A lower step will then make sure all values are positive.
long valueModifier = hungarianOperationMode.getModifier();
// Populate the original and current amtrix
for (int row=0; row<this.size; row++) {
for (int column=0; column<this.size; column++) {
Long value;
if (row < this.height && column < this.width) {
value = inputMatrix[row][column];
} else {
value = null;
}
this.cellStates[row][column] = CellState.NORMAL;
if (value == null) {
this.impossibleMatrix[row][column] = true;
} else {
this.originalMatrix[row][column] = value;
value = Math.multiplyExact(value, valueModifier);
this.currentMatrix[row][column] = value;
if (value > maximumValue) {
maximumValue = value;
}
if (value < minimumValue) {
minimumValue = value;
}
}
}
}
// The convention for the hungarian algorithm is to use the maximum value for dummy values.
// However, in the case where may be missing impossible values in the matrix, this is no longer enough, as it might be possible that the maximum valued entry needs to be used.
// For that valid choice to happen, instead of one of the dummy values being chosen instead, there needs to be a difference between valid maximum values and invalid values.
// Then, to make sure the matrix is fully positive, add one the minimum value.
// Use this newly calculated value and fill in the relevant matrix entries.
long missingValueCurrent = Math.addExact(maximumValue, 1);
long missingValueOriginal = Math.multiplyExact(missingValueCurrent, valueModifier);
for (int row=0; row<this.size; row++) {
for (int column=0; column<this.size; column++) {
if (this.impossibleMatrix[row][column]) {
this.originalMatrix[row][column] = missingValueOriginal;
this.currentMatrix[row][column] = missingValueCurrent;
}
this.currentMatrix[row][column] = Math.subtractExact(this.currentMatrix[row][column], minimumValue);
}
}
}
Maybe someone will be able to tell you something about the edge cases then.
Edit:
Of course these tips do apply to all of your code. Extracting code into functions improves your general code quality and should be applied whereever possible.
Dominik Reinert
- 228
- 1
- 9
default