7
\$\begingroup\$

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;
    private boolean[][] impossibleMatrix;
    private CellState[][] cellStates;
    private boolean[] coveredColumns;
    private boolean[] coveredRows;
    private Point[] path;
    private int pathSize;

    /**
     * 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) {
        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");
                        }
                    }
                }
                // 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);
                    }
                }
            }
        }
    }

    /**
     * The main solve method.
     * @return A solution if one was found.
     */
    public Optional<HungarianSolution> solve() {
        // Reduce the matrix to a simpler form.
        this.reduceMatrix();
        // Populate some starred values to be begin with.
        this.initStars();
        while (true) {
            // Check if the amount of starred zeros is the same as the amount of columns. If so, a solution has been found.
            if (this.coverColumnsOfStarredZeros() >= this.size) {
                return this.produceResult();
            }
            // Loop.
            while (true) {
                // Find an uncovered zero.
                Point uncoveredZero = this.findAnyUncoveredZero();
                if (uncoveredZero == null) {
                    // There are no remaining uncovered zeros, but no solution was found above. Manipulate the matrix and find a new zero.
                    if (!this.createNewZero()) {
                        // Having no change to the matrix at this point will just cause the next iteration of the inner loop to arrive straight back here. Prevent that.
                        // However, don't just return an 'unsolvable' state, as it should not be possible in the first place.
                        throw new IllegalStateException("No new zero created. An infinite loop will result.");
                    }
                } else if (!this.primeUncoveredZero(uncoveredZero)) {
                    // The unocovered zero could not be primed. One or more rows/columns where an arbitary zero was starred has proven to be wrong.
                    // Backtrack changing all zeros that could have lead to this decision.
                    this.findAugmentedPath(uncoveredZero);
                    this.augmentPath();
                    this.resetCovers();
                    this.resetStates(CellState.PRIMED, CellState.NORMAL);
                    break;
                }
            }
        }
    }

    /**
     * Reduce the complexity of the matrix.
     * In most scenarios, no matter which agent is chosen for a task, there will be some minimum cost. E.G: If agent A requires 30, agent B requires 20 and agent C requires 40, then at minimum 20 is going to be spent on that task. Therefore the row can be reduced to 10, 0, 20.
     * The same can be done if there is a minimum cost no matter what task is chosen for an agent.
     */
    private void reduceMatrix() {
        /*
         * Begin big explanation for relativly small method.
         * The below explains why the reduce rows/columns operations may be reversed. This is a deviation from the original source material.
         * ------------------------------------------------------------------------------------------------------------------------------------
         * We don't want to reduce the 'dummy' rows/columns to entirely zeros first, because that would cause the second passthrough. For Example:
         *  01   02   03   04
         *  02   04   06   08
         *  03   06   09   12
         *  12   12   12   12 <-- Dummy row, full of the maximum value of 12, because the input matrix has a larger width than height.
         *
         * If rows were done first:
         *  00   01   02   04
         *  00   02   04   06
         *  00   03   06   09
         *  00   00   00   00
         *
         * Now becaue of the 0s in the bottom row, column reduction results in no change. The maximum possible zeros in inteligentlyInitStars is then 2. Below is one example:
         * [00]  01   02   04
         * /00/  02   04   06
         * /00/  03   06   09
         * /00/ [00] /00/ /00/
         *
         * However, if columns were done first:
         *  00   00   00   00
         *  01   02   03   04
         *  02   04   06   08
         *  11   10   09   08
         *
         * follwed by rows:
         *  00   00   00   00
         *  00   01   02   03
         *  00   02   04   06
         *  03   02   01   00
         *
         * Which then allows a maximum possible zeros of 3. Below is one example:
         * /00/ [00] /00/ /00/
         * [00]  01   02   03
         * /00/  02   04   06
         *  03   02   01  [00]
        */
        if (this.width > this.height) {
            this.reduceColumns();
            this.reduceRows();
        } else {
            this.reduceRows();
            this.reduceColumns();
        }
    }

    /**
     * @see #reduceMatrix().
     * This operations on rows, and is almost identical to {@link #reduceColumns()).
     */
    private void reduceRows() {
        for (int row=0; row<this.size; row++) {
            long minimumValue = this.currentMatrix[row][0];
            for (int column=1; column<this.size; column++) {
                if (this.currentMatrix[row][column] < minimumValue) {
                    minimumValue = this.currentMatrix[row][column];
                }
            }
            if (minimumValue != 0) {
                for (int column=0; column<this.size; column++) {
                    this.currentMatrix[row][column] = Math.subtractExact(this.currentMatrix[row][column], minimumValue);
                }
            }
        }
    }

    /**
     * @see #reduceMatrix().
     * This operations on rows, and is almost identical to {@link #reduceRows()).
     */
    private void reduceColumns() {
        for (int column=0; column<this.size; column++) {
            long minimumValue = this.currentMatrix[0][column];
            for (int row=1; row<this.size; row++) {
                if (this.currentMatrix[row][column] < minimumValue) {
                    minimumValue = this.currentMatrix[row][column];
                }
            }
            if (minimumValue != 0) {
                for (int row=0; row<this.size; row++) {
                    this.currentMatrix[row][column] = Math.subtractExact(this.currentMatrix[row][column], minimumValue);
                }
            }
        }
    }

    /**
     * Initially populate a series of zeros as starred.
     */
    private void initStars() {
        // Use two methods of starring zeros.
        this.initSingularPossibilityStars();
        this.initRemainingStarsGreedily();

        // Reset any covers that were used.
        this.resetCovers();
    }

    /**
     * Repeatedly see if there are any rows for which there is a single uncovered zero. If so, that must be the only possibility, so star it.
     * Then do the same for columns,
     * Then repeat both operations until neither added any stars.
     */
    private void initSingularPossibilityStars() {
        while (this.initSingularPossibilityStarsInRows() | this.initSingularPossibilityStarsInColumns()) {}
    }

    /**
     * @see #initSingularPossibilityStars().
     * This operations on rows, and is almost identical to {@link #initSingularPossibilityStarsInColumns()).
     */
    private boolean initSingularPossibilityStarsInRows() {
        boolean changed = false;
        for (int row=0; row<this.size; row++) {
            if (!this.coveredRows[row]) {
                int zeroCount = 0;
                int zeroColumn = 0;
                // Find if there is only one zero in this row, and if so, what column it is in.
                for (int column=0; column<this.size; column++) {
                    if (!this.coveredColumns[column] && this.currentMatrix[row][column] == 0) {
                        zeroCount++;
                        zeroColumn = column;
                    }
                }
                if (zeroCount == 1) {
                    // Cover both the row and column.
                    this.coveredRows[row] = true;
                    this.coveredColumns[zeroColumn] = true;
                    this.cellStates[row][zeroColumn] = CellState.STARRED;
                    changed = true;
                }
            }
        }
        return changed;
    }

    /**
     * @see #initSingularPossibilityStars().
     * This operations on columns, and is almost identical to {@link #initSingularPossibilityStarsInRows()).
     */
    private boolean initSingularPossibilityStarsInColumns() {
        boolean changed = false;
        for (int column=0; column<this.size; column++) {
            if (!this.coveredColumns[column]) {
                int zeroCount = 0;
                int zeroRow = 0;
                // Find if there is only one zero in this column, and if so, what row it is in.
                for (int row=0; row<this.size; row++) {
                    if (!this.coveredRows[row] && this.currentMatrix[row][column] == 0) {
                        zeroCount++;
                        zeroRow = row;
                    }
                }
                if (zeroCount == 1) {
                    // Cover both the row and column.
                    this.coveredColumns[column] = true;
                    this.coveredRows[zeroRow] = true;
                    this.cellStates[zeroRow][column] = CellState.STARRED;
                    changed = true;
                }
            }
        }
        return changed;
    }

    /**
     * For any remaining uncovered rows/columns with a star, arbitrarily choose a zero and cover it, until no more covers can be made.
     * These may or may not be the correct zeros if there are more than one uncovered zero in a row/zero in question, and there may be a better selection that could be made. This does not matter.
     */
    private void initRemainingStarsGreedily() {
        for (int row=0; row<this.size; row++) {
            for (int column=0; column<this.size; column++) {
                if (this.currentMatrix[row][column] == 0 && !this.coveredRows[row] && !this.coveredColumns[column]) {
                    this.coveredColumns[column] = true;
                    this.coveredRows[row] = true;
                    this.cellStates[row][column] = CellState.STARRED;
                }
            }
        }
    }

    /**
     * Change all cells that have one state into another state.
     * @param oldState The old state that should be changed.
     * @param newState The new state that should be set.
     */
    private void resetStates(CellState oldState, CellState newState) {
        for (int row=0; row<this.size; row++) {
            for (int column=0; column<this.size; column++) {
                if (this.cellStates[row][column] == oldState) {
                    this.cellStates[row][column] = newState;
                }
            }
        }
    }

    /**
     * Uncover all cells.
     */
    private void resetCovers() {
        for (int dimension=0; dimension<this.size; dimension++) {
            this.coveredColumns[dimension] = false;
            this.coveredRows[dimension] = false;
        }
    }

    /**
     * Cover a column if it contains a starred zero.
     * @return The amount of columns that were covered.
     */
    private int coverColumnsOfStarredZeros() {
        int coveredColumnCount = 0;
        for (int column=0; column<this.size; column++) {
            for (int row=0; row<this.size; row++) {
                if (this.cellStates[row][column] == CellState.STARRED) {
                    this.coveredColumns[column] = true;
                    coveredColumnCount++;
                    break;
                }
            }
        }
        return coveredColumnCount;
    }

    /**
     * Find any uncovered zero, no matter which row or column it is on.
     * @return The point that the uncovered zero was found.
     */
    private Point findAnyUncoveredZero() {
        for (int row=0; row<this.size; row++) {
            if (!this.coveredRows[row]) {
                for (int column=0; column<this.size; column++) {
                    if (this.currentMatrix[row][column] == 0 && !this.coveredColumns[column]) {
                        return new Point(row, column);
                    }
                }
            }
        }
        return null;
    }

    /**
     * Find the first cell in a row that has a certain state.
     * This is almost identical to {@link #findCellStateInColumn(int, uk.co.scottdennison.java.lib.algorithms.assignment.hungarian.HungarianProblem.CellState, int))
     * @param row The row to look in.
     * @param cellState The cell state that is desired.
     * @param unwantedColumn A column to ignore. Can be an invalid column number such as -1 to consider all columns as potential candidates.
     * @return The index of the first column in the provided row that matches the criteria, or null if there is no cell matching the criteria.
     */
    private Integer findCellStateInRow(int row, CellState cellState, int unwantedColumn) {
        for (int column=0; column<this.size; column++) {
            if (column != unwantedColumn && this.cellStates[row][column] == cellState) {
                return column;
            }
        }
        return null;
    }

    /**
     * Find the first cell in a column that has a certain state.
     * This is almost identical to {@link #findCellStateInRow(int, uk.co.scottdennison.java.lib.algorithms.assignment.hungarian.HungarianProblem.CellState, int))
     * @param column The column to look in.
     * @param cellState The cell state that is desired.
     * @param unwantedRow A row to ignore. Can be an invalid row number such as -1 to consider all rows as potential candidates.
     * @return The index of the first row in the provided column that matches the criteria, or null if there is no cell matching the criteria.
     */
    private Integer findCellStateInColumn(int column, CellState cellState, int unwantedRow) {
        for (int row=0; row<this.size; row++) {
            if (row != unwantedRow && this.cellStates[row][column] == cellState) {
                return row;
            }
        }
        return null;
    }

    /**
     * Prime an uncovered zero, and return whether it was a valid prime operation.
     * @param uncoveredZeroPoint The point of the uncovered zero to prime.
     * @return true if the uncovered zero shares the same row as another zero that has already been starred and covered. false if not, at which point this priming was not valid.
     */
    private boolean primeUncoveredZero(Point uncoveredZeroPoint) {
        this.cellStates[uncoveredZeroPoint.row][uncoveredZeroPoint.column] = CellState.PRIMED;
        Integer starColumn = this.findCellStateInRow(uncoveredZeroPoint.row,CellState.STARRED,-1);
        if (starColumn != null) {
            this.coveredRows[uncoveredZeroPoint.row] = true;
            this.coveredColumns[starColumn] = false;
            return true;
        }
        else {
            return false;
        }
    }

    /**
     * Starting at the provided point find a path that consists of
     *   * A starred zero in the same column as the previous point.
     *   * A primed zero in the same row as the previous (including the above) point.
     * Continuing until there the first criteria cannot be matched. The second criteria should ALWAYS be able to be matched if the first is.
     * This will find all zeros that possibility badly influenced each other to result in the provided start point being unprimable.
     * @param startPoint The starting point of the path - The zero that could not be primed.
     */
    private void findAugmentedPath(Point startPoint) {
        this.path[0] = startPoint;
        this.pathSize = 1;
        Integer column = startPoint.column;
        Integer row;
        while (true) {
            row = this.findCellStateInColumn(column,CellState.STARRED,-1);
            if (row == null) {
                break;
            } else {
                this.incrementPathSize();
                this.path[this.pathSize-1] = new Point(row,column);
                column = this.findCellStateInRow(row, CellState.PRIMED,-1);
                if (column == null) {
                    throw new IllegalStateException("No prime found.");
                } else {
                    this.incrementPathSize();
                    this.path[this.pathSize-1] = new Point(row,column);
                }
            }
        }
    }

    /**
     * Augment the path that was found by {@link #findAugmentedPath(uk.co.scottdennison.java.lib.algorithms.assignment.hungarian.HungarianProblem.Point))
     * This involves marking all incorrectly starred zeros as unstarred, and all primed zeros and the new path of stars.
     */
    private void augmentPath() {
        for (int pathIndex=0; pathIndex<this.pathSize; pathIndex++) {
            Point point = this.path[pathIndex];
            int row = point.row;
            int column = point.column;
            switch (this.cellStates[row][column]) {
                case STARRED:
                    this.cellStates[row][column] = CellState.NORMAL;
                    break;
                case PRIMED:
                    this.cellStates[row][column] = CellState.STARRED;
                    break;
                default:
                    // Do nothing.
            }
        }
    }

    /**
     * Increment the path size unless this would cause an {@link ArrayIndexOutOfBoundsException).
     * I have guessed how much room the path could be by allowing each row and column to be covered twice, which should never happen.
     * However, as the reference guide does not explain how to correctly size the path array, this is here to make sure.
     */
    private void incrementPathSize() {
        this.pathSize++;
        if (this.pathSize > this.path.length) {
            throw new IllegalStateException("Path size exceeds bounds.");
        }
    }

    /**
     * Create a new zero.
     * This is done by finding the smallest value that is not covered.
     * Then all uncovered cells have this value subtracted from them, creating a new zero, and all cells that are both covered by a column and a row have it added to them, possibly removing an invalid zero.
     */
    private boolean createNewZero() {
        boolean zeroCreated = false;
        long minimumValue = this.findSmallestUncoveredValue();
        if (minimumValue != 0) {
            for (int row=0; row<this.size; row++) {
                for (int column=0; column<this.size; column++) {
                    long currentValue = this.currentMatrix[row][column];
                    long newValue = currentValue;
                    boolean rowCovered = this.coveredRows[row];
                    boolean columnCovered = this.coveredColumns[column];
                    if (rowCovered && columnCovered) {
                        newValue = Math.addExact(newValue, minimumValue);
                    } else if (!rowCovered && !columnCovered) {
                        newValue = Math.subtractExact(newValue, minimumValue);
                    }
                    if (currentValue != newValue) {
                        this.currentMatrix[row][column] = newValue;
                        zeroCreated |= newValue == 0;
                    }
                }
            }
        }
        return zeroCreated;
    }

    /**
     * Loop over the entire matrix and find the smallest value that is not yet covered.
     * @return The smallest value.
     */
    private long findSmallestUncoveredValue() {
        long minimumValue = Long.MAX_VALUE;
        for (int row=0; row<this.size; row++) {
            if (!this.coveredRows[row]) {
                for (int column=0; column<this.size; column++) {
                    if (!this.coveredColumns[column] && this.currentMatrix[row][column] < minimumValue) {
                        minimumValue = this.currentMatrix[row][column];
                    }
                }
            }
        }
        return minimumValue;
    }

    /**
     * Translate the series of starred zeros into a solution.
     * @return The result if there is a valid one.
     */
    private Optional<HungarianSolution> produceResult() {
        Integer[] assignments = new Integer[this.width];
        BigInteger totalValue = BigInteger.ZERO; // So far, we have only ever been dealing with one number at at time. Now we need to sum a large amount, long may not be good enough.
        boolean legal = true;
        for (int column=0; column<this.size; column++) {
            // Find the starred zero for this column.
            // Use an int not an Integer as it is impossible to reach this stage without there being a starred zero.
            int row = this.findCellStateInColumn(column, CellState.STARRED, -1);

            // Preform two sanity checks to make sure that a state has not been reached there there are multiple stars in a row/column.
            Integer secondColumn = this.findCellStateInRow(row, CellState.STARRED, column);
            if (secondColumn != null) {
                throw new IllegalStateException("Non-unique star at position (row=" + row + ",column=" + column + ") detected in column " + secondColumn + ".");
            }
            Integer secondRow = this.findCellStateInColumn(column, CellState.STARRED, row);
            if (secondRow != null) {
                throw new IllegalStateException("Non-unique star at position (row=" + row + ",column=" + column + ") detected in row " + secondRow + ".");
            }

            // Only record the result if both the row/column were not dummy columns.
            if (column < this.width && row < this.height) {
                // Ensure that a possible entry was chosen.
                // Given the value that was assigned to the impossible values in the constructor, the only way for an impossible value to have been used if there was no other solution possible. Therefore mark that there is no solution.
                if (this.impossibleMatrix[row][column]) {
                    legal = false;
                    break;
                }
                assignments[column] = row;
                totalValue = totalValue.add(BigInteger.valueOf(this.originalMatrix[row][column]));
            }
        }
        if (legal) {
            return Optional.of(new HungarianSolution(totalValue, assignments));
        } else {
            return Optional.empty();
        }
    }
}

Supporting classes

HungarianOperationMode.java

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

/**
 * The type of hungarian operation that should be ran.
 * @author scott.dennison
 */
public enum HungarianOperationMode {
    /**
     * Find the minimum valued combination possible.
     */
    MINIMIZE,

    /**
     * Find the maximum valued combination possible.
     */
    MAXIMIZE;
}

HungarianSolution.java

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

import java.math.BigInteger;

/**
 * A solution to a {@link HungarianProblem}.
 * @author scott.dennison
 */
public class HungarianSolution {
    private final BigInteger totalValue;
    private final Integer[] assignments;

    /**
     * Create a hungarian solution
     * @param totalValue The total value of the chosen assignments.
     * @param assignments An array of size {to-entries/tasks} where each entry is the index of the {from-entry/agent) to use for that task.
     */
    public HungarianSolution(BigInteger totalValue, Integer[] assignments) {
        this.totalValue = totalValue;
        this.assignments = this.copyArray(assignments);
    }

    /**
     * Get the total value of the chosen assignments.
     * @return The total value.
     */
    public BigInteger getTotalValue() {
        return this.totalValue;
    }

    /**
     * Get the assignments array.
     * @return An array of size {to-entries/tasks} where each entry is the index of the {from-entry/agent) to use for that task.
     */
    public Integer[] getAssignments() {
        return this.copyArray(assignments);
    }

    /**
     * An internal method that creates a copy of the input integer array.
     * @param input The input array.
     * @return A copy of the input array.
     */
    private Integer[] copyArray(Integer[] input) {
        int count = input.length;
        Integer[] output = new Integer[count];
        System.arraycopy(input, 0, output, 0, count);
        return output;
    }
}
\$\endgroup\$
  • \$\begingroup\$ You are ONLY asking, if all cases are covered, not for better code quality, arent you? \$\endgroup\$ – Do Re May 8 '17 at 7:41
  • \$\begingroup\$ The original version of the question before Jamal edited it did ask for checking all cases are covered and/or code quality improvement suggestions. Either are welcome. \$\endgroup\$ – Scott Dennison May 8 '17 at 17:26
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Are the indentation in your code example as you expect them to be? As it stands you seem to jump in and out seemingly random. \$\endgroup\$ – holroy May 9 '17 at 8:24
  • \$\begingroup\$ @holroy you are right. I improved the identation \$\endgroup\$ – Do Re May 9 '17 at 8:30
  • \$\begingroup\$ A variable whose type is an enum can be null rather than one of the values in the enum. \$\endgroup\$ – Peter Taylor May 9 '17 at 8:39
  • \$\begingroup\$ @PeterTaylor added an edit \$\endgroup\$ – Do Re May 9 '17 at 8:41
  • \$\begingroup\$ A more useful edit changes the incorrect statement rather than correcting it two pages later. The postscript was also incorrect, because Rule validates the matrix and not the other arguments. \$\endgroup\$ – Peter Taylor May 9 '17 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.