1
\$\begingroup\$

This is an extension of Part 1 of this question, which concerns the core part of my Java implementation of the Hungarian algorithm.

To make usage of the classes in that question easier (partially because I know what code is going to use it, see this question which pointed me in the direction of the hungarian algorithm in the first place) I have written that accepts pairs of 'from/agent' types and 'to/task' types, and then converts to and from the matrix form that the hungarian algorithm accepts.

The idea is, taking the example from the Wikipedia page about the algorithm, is instead of using:

Long[][] matrix = new Long[][] {
  {2L,3L,3L},
  {3L,2L,3L},
  {3L,3L,2L}
};

HungarianProblem hp = new HungarianProblem(matrix,HungarianOperationMode.MINIMUM);

...

You can use the slightly more verbose (in this example), but better reading:

TypedHungarianProblem<Worker,Job,Long> problem = TypedHungarianProblem.create();
problem.putEntry(Worker.ARMOND  , Job.CLEAN_BATHROOM, 2L);
problem.putEntry(Worker.ARMOND  , Job.SWEEP_FLOORS  , 3L);
problem.putEntry(Worker.ARMOND  , Job.WASH_WINDOWS  , 3L);
problem.putEntry(Worker.FRANCINE, Job.CLEAN_BATHROOM, 3L);
problem.putEntry(Worker.FRANCINE, Job.SWEEP_FLOORS  , 2L);
problem.putEntry(Worker.FRANCINE, Job.WASH_WINDOWS  , 3L);
problem.putEntry(Worker.HERBERT , Job.CLEAN_BATHROOM, 3L);
problem.putEntry(Worker.HERBERT , Job.SWEEP_FLOORS  , 3L);
problem.putEntry(Worker.HERBERT , Job.WASH_WINDOWS  , 2L);
problem.solve(HungarianOperationMode.MINIMIZE);

// The result is a series of entries of {ARMOND,CLEAN_BATHROOM,2},{FRANCINE,SWEEP_FLOORS,2},{HERBERT,WASH_WINDOWS,2}

Primary Classes

TypedHungarianProblem.java

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

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.function.Function;

/**
 * A typed hungarian algiorithm problem.
 * This is a wrapper around a {@link HungarianProblem} which allows the 'from (agent), 'to' (task) and 'cost' parts to all be java types rather than simply indexes in an array.
 * It also allows for some linkages to easily to omitted.
 * The results from the hungarian solution will then also be translated back to those types, removing the need for interpreting the result array.
 * @author scott.dennison
 * @param <FromType> The type that that is being linked from, or the 'agent'.
 * @param <ToType> The type that is being linked to, or the 'task'.
 * @param <CostType> The type of the cost. Must be convertible into a number.
 */
public class TypedHungarianProblem<FromType,ToType,CostType> {
    private final Set<FromType> fromSet = new HashSet<>();
    private final Set<ToType> toSet = new HashSet<>();
    private final Map<FromType,Map<ToType,CostType>> costs = new HashMap<>();
    private final Function<CostType,Long> costValueGenerator;

    /**
     * Construct a typed hungarian problem.
     *
     * This method is private to allow generic specialisations to be provided as static methods.
     * @param costValueGenerator The function that translates a cost type into its numeric value.
     */
    private TypedHungarianProblem(Function<CostType,Long> costValueGenerator) {
        if (costValueGenerator == null) {
            throw new IllegalArgumentException("The cost value generator is null");
        } else {
            this.costValueGenerator = costValueGenerator;
        }
    }


    /**
     * Create a typed hungarian problem.
     * @param <FromType> The type that that is being linked from, or the 'agent'.
     * @param <ToType> The type that is being linked to, or the 'task'.
     * @param <CostType> The type of the cost. Must be convertible into a number.
     * @param costValueGenerator The function that translates a cost type into its numeric value.
     * @return The typed hungarian problem.
     */
    public static <FromType,ToType,CostType> TypedHungarianProblem<FromType,ToType,CostType> create(Function<CostType,Long> costValueGenerator) {
        return new TypedHungarianProblem<>(costValueGenerator);
    }

    /**
     * Create a typed hungarian problem, where the cost is already of type {@link Long}.
     * @param <FromType> The type that that is being linked from, or the 'agent'.
     * @param <ToType> The type that is being linked to, or the 'task'.
     * @return The typed hungarian problem.
     */
    public static <FromType,ToType> TypedHungarianProblem<FromType,ToType,Long> create() {
        return new TypedHungarianProblem<>(Function.identity());
    }

    /**
     * Put an entry into the problem.
     * @param from The from part.
     * @param to The to part.
     * @param cost The cost part.
     */
    public void putEntry(FromType from, ToType to, CostType cost) {
        this.fromSet.add(from);
        this.toSet.add(to);
        Map<ToType,CostType> costsForFrom = this.costs.get(from);
        if (costsForFrom == null) {
            costsForFrom = new HashMap<>();
            this.costs.put(from,costsForFrom);
        }
        costsForFrom.put(to,cost);
    }

    /**
     * Create a map of items to indexes, from a list.
     * This replicates what can be done with {@link List#indexOf(java.lang.Object) but without having to iterate over each item.
     * @param <T> The type of entry in the list/map.
     * @param list The input list.
     * @return The output map.
     */
    private <T> Map<T,Integer> createMap(List<T> list) {
        Map<T,Integer> map = new HashMap<>();
        int size = list.size();
        for (int index=0; index<size; index++) {
            Integer boxedIndex = index;
            map.put(list.get(boxedIndex),boxedIndex);
        }
        return map;
    }

    /**
     * Solve the hungarian problem.
     * @param hungarianOperationMode The hungarian operation mode.
     * @return The solution.
     */
    public Optional<TypedHungarianSolution<FromType,ToType,CostType>> solve(HungarianOperationMode hungarianOperationMode) {
        // Create the lists/maps from the sets.
        List<FromType> fromList = new ArrayList<>(this.fromSet);
        Map<FromType,Integer> fromMap = this.createMap(fromList);
        List<ToType> toList = new ArrayList<>(this.toSet);
        Map<ToType,Integer> toMap = this.createMap(toList);

        // Create the input matrix.
        int fromSize = fromList.size();
        int toSize = toList.size();
        Long matrix[][] = new Long[fromSize][toSize];

        // Populate the input matrix from the stored entries. Any missing entries will remain as null.
        for (Map.Entry<FromType,Map<ToType,CostType>> fromEntry : this.costs.entrySet()) {
            // Get a reference to the first level of the input matrix.
            Long[] matrixFromView = matrix[fromMap.get(fromEntry.getKey())];
            for (Map.Entry<ToType,CostType> toEntry : fromEntry.getValue().entrySet()) {
                matrixFromView[toMap.get(toEntry.getKey())] = this.costValueGenerator.apply(toEntry.getValue());
            }
        }

        // Create and solve the problem.
        HungarianProblem hungarianProblem = new HungarianProblem(matrix,hungarianOperationMode);
        Optional<HungarianSolution> optionalHungarianSolution = hungarianProblem.solve();

        // Check if there is a possible solution.
        if (optionalHungarianSolution.isPresent()) {
            HungarianSolution hungarianSolution = optionalHungarianSolution.get();
            Integer[] assignments = hungarianSolution.getAssignments();

            // Map the solution back into from/to/cost entries.
            List<TypedHungarianSolutionEntry<FromType,ToType,CostType>> results = new ArrayList<>();
            for (int toIndex=0; toIndex<toSize; toIndex++) {
                Integer fromIndex = assignments[toIndex];
                if (fromIndex != null) {
                    FromType from = fromList.get(fromIndex);
                    ToType to = toList.get(toIndex);
                    CostType cost = null;
                    Map<ToType,CostType> fromCostMap = this.costs.get(from);
                    if (fromCostMap != null) {
                        cost = fromCostMap.get(to);
                    }
                    results.add(new TypedHungarianSolutionEntry<>(from,to,cost));
                }
            }

            // Return the result.
            return Optional.of(new TypedHungarianSolution<>(hungarianSolution.getTotalValue(),results));
        } else {
            return Optional.empty();
        }
    }
}

Supporting Classes

TypedHungarianSolution.java

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

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * A solution to a {@link TypedHungarianProblem}.
 * @author scott.dennison
 * @param <FromType> The type that that is being linked from, or the 'agent'.
 * @param <ToType> The type that is being linked to, or the 'task'.
 * @param <CostType> The type of the cost. Must be convertible into a number.
 */
public class TypedHungarianSolution<FromType,ToType,CostType> {
    private final BigInteger totalValue;
    private final List<TypedHungarianSolutionEntry<FromType,ToType,CostType>> pairings;

    /**
     * Create a hungarian solution
     * @param totalValue The total value of the chosen assignments.
     * @param pairings A list of chosen from/to entries, along with their cost entries.
     */
    public TypedHungarianSolution(BigInteger totalValue, List<TypedHungarianSolutionEntry<FromType,ToType,CostType>> pairings) {
        this.totalValue = totalValue;
        this.pairings = new ArrayList<>(pairings);
    }

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

    /**
     * Get the list of chosen from/to entries, along with their cost entries.
     * @return An unmodifiable view of the pairings.
     */
    public List<TypedHungarianSolutionEntry<FromType,ToType,CostType>> getPairings() {
        return Collections.unmodifiableList(this.pairings);
    }
}

TypedHungarianSolutionEntry.java

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

/**
 * A typed hungarian entry.
 * @author scott.dennison
 * @param <FromType> The type that that is being linked from, or the 'agent'.
 * @param <ToType> The type that is being linked to, or the 'task'.
 * @param <CostType> The type of the cost. Must be convertible into a numbere.
 */
public class TypedHungarianSolutionEntry<FromType,ToType,CostType> {
    private final FromType from;
    private final ToType to;
    private final CostType cost;

    /**
     * Create an entry
     * @param from The from part.
     * @param to The to part.
     * @param cost The cost part.
     */
    public TypedHungarianSolutionEntry(FromType from, ToType to, CostType cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }

    /**
     * Get the from part.
     * @return The from part.
     */
    public FromType getFrom() {
        return this.from;
    }

    /**
     * Get the to part.
     * @return The to part.
     */
    public ToType getTo() {
        return this.to;
    }

    /**
     * Get the cost part.
     * @return The cost part.
     */
    public CostType getCost() {
        return this.cost;
    }
}

Classes from the previous question

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();
        }
    }
}

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 may consider reading more about post formatting on this site. You don't need to use HTML tags for hyperlinks. Also, it may be helpful to wait until your previous question(s) have been reviewed, so that the same review tips won't be repeated. \$\endgroup\$ – Jamal Apr 16 '17 at 19:58

Your Answer

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

Browse other questions tagged or ask your own question.