Hungarian algorithm for optimal assignment

Question

The assignment problem is about assigning tasks to workers, where each pair (worker, task) has a cost. The Hungarian algorithm builds an optimal solution for this problem. It has two variants, depending on the representation of the cost relationships: one with bipartite graphs, and one with cost matrices. I have implemented the latter form as described here because I had trouble making Wikipedia's step 3 example into an algorithm. The goal is to produce a library that I can use in another project in which I intend to assign mentors to students based on their likelihood of getting along.

In short, the algorithm modifies the cost matrix to make zeroes appear and selects some of them to build an optimal solution. It uses two types of marks, stars (for zeroes belonging to the candidate solution) and primes (for zeroes that could replace starred zeroes in the solution). It moves between 6 steps:

1. The matrix is preprocessed (validity checks, optional rotation to have at least as many columns than rows, subtraction of the minimum value of each row to all values of the same row and then the same for columns)
2. Greedily prepare a candidate solution by starring zeroes
3. Check if the candidate solution is complete; if yes, return it; else, go to the next step
4. Try to find a zero that could replace a starred one in the candidate solution; if one is found, go to the next step; else, go to step 6
5. Follow an alternating path of primed and starred zeroes to modify the candidate solution, and go back to step 3
6. Modify some values in the matrix to make more zeroes appear, and go back to step 4.

For example, take the following cost matrix.

	0	1	2	3
0	1	2	25	13
1	5	7	25	15
2	10	13	16	13
3	17	21	11	18
4	15	15	15	14

The algorithm must output the following solution, with a total cost of 2 + 5 + 13 + 11 = 31 (and the last row is not assigned any task because the worker is too expensive).

	0	1	2	3
0		X
1	X
2				X
3			X
4

My code in Java 11 works as intended on several hand-made examples and standard edge cases (null input, non-square cost matrix, worst-case matrix for this algorithm). If you find any case that is poorly handled, I would be happy to know but that is not my main concern here.

I used junit5 to write unit tests and I feel that the test framework I wrote might be needlessly complex. I wanted to get a separate test result for each run of a test method on each of its input, and several test methods will have the same input. I wrote the TestFrameWork and TestArguments interfaces as a way to use junit5's streams of tests, and each test class must implement the TestFrameWork interface with a utility class implementing the TestArguments interface. Then, most tests only need writing a simple lambda function performing only the actual verification. I wonder if that is a good idea or a terrible one.

Additionally, I made three methods package-private rather than private because I wanted to test them specifically, which smells fishy as well: the constructor, reduceInitialMatrix and getState (which only exist to test reduceInitialMatrix, and that seems even worse). I have a bit of trouble setting the balance between encapsulation and testing, I'll gladly take any advice on this point too.

All the original code base can be found on my github. For this question, I have edited it a bit: instead of making HungarianSolver extend the abstract Solver and inherit the javadoc, I made the HungarianSolver stand-alone and put the javadoc directly in it. I built and ran the tests on the modified version to make sure that I didn't break anything.

HungarianSolver.java

package AssignmentProblem;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Implementation of the HungarianAlgorithm.
 */
class HungarianSolver {

    final private int[][] costMatrix;
    final private int[][] assignments;
    final private int[] rowAssignments;
    final private int[] colAssignments;
    final private int nRows;
    final private int nCols;
    final private boolean[] coveredRows;
    final private boolean[] coveredCols;
    final private int[] starredRows;
    final private int[] starredCols;
    final private int[] primedRows;
    final private int[] primedCols;
    private int numberCoveredCols;
    final private boolean transposed;

    /**
     * Instantiates a new solver on the given cost matrix. The proper way to get
     * the solution of the assignment problem with a {@link HungarianSolver} is
     * to call {@link #initialise(int[][])} rather than directly the constructor.
     *
     * @param costMatrix
     */
    HungarianSolver(int[][] costMatrix) {
        checkMatrixValidity(costMatrix);
        if (costMatrix.length > costMatrix[0].length){
            //flip matrix to have more columns than rows
            transposed = true;
            nRows = costMatrix[0].length;
            nCols = costMatrix.length;
            this.costMatrix = new int[nRows][nCols];
            for (int i = 0; i < nRows; i++) {
                for (int j = 0; j < nCols; j++) {
                    this.costMatrix[i][j] = costMatrix[j][i];
                }
            }
        } else {
            this.costMatrix = costMatrix;
            nRows = costMatrix.length;
            nCols = costMatrix[0].length;
            transposed = false;
        }
        assignments = new int[nRows][2];
        rowAssignments = new int[transposed ? nCols : nRows];
        colAssignments = new int[transposed ? nRows : nCols];
        coveredRows = new boolean[nRows];
        coveredCols = new boolean[nCols];
        starredRows = new int[nRows];
        starredCols = new int[nCols];
        primedRows = new int[nRows];
        primedCols = new int[nCols];
        Arrays.fill(starredRows, -1);
        Arrays.fill(starredCols, -1);
        Arrays.fill(primedRows, -1);
        Arrays.fill(primedCols, -1);
        Arrays.fill(rowAssignments, -1);
        Arrays.fill(colAssignments, -1);
        for (int[] assignment : assignments) {
            Arrays.fill(assignment, -1);
        }
    }

    protected static HungarianSolver initialise(int[][] costMatrix) {
        HungarianSolver result = new HungarianSolver(costMatrix);
        result.reduceInitialMatrix();
        result.solveReducedMatrix();
        return result;
    }

    /**
     * Returns the column index assigned to each row.
     * @return The result of the assignment problem from the row perspective.
     * The i-th element of the output is the index of the column assigned to the
     * i-th row, or -1 if the row has not been assigned.
     */
    public int[] getRowAssignments() {
        return this.rowAssignments;
    }

    public int[] getColumnAssignemnts() {
        return this.colAssignments;
    }

    /**
     * Returns the pairs of row and column indices of the assignments.
     * @return The result of the assignment problem as pairs. Each element of 
     * the output is an assigned pair whose first element is the index of the 
     * row and the second element is the index of the column. Unassigned rows
     * and columns are not included.
     */
    public int[][] getAssignments() {
        return this.assignments;
    }

    /**
     * Reduces the values of the matrix to make zeroes appear. This
     * corresponds to the first step of the Hungarian Algorithm.
     */
    void reduceInitialMatrix() {
        //first part: reduce all rows
        for (int[] row : costMatrix) {
            int min = row[0];
            for (int val : row) {
                if (val < min) {
                    min = val;
                }
            }
            for (int j = 0; j < row.length; j++) {
                row[j] -= min;
            }
        }
        //second part: reduce all columns
        for (int j = 0; j < nCols; j++) {
            int min = costMatrix[0][j];
            for (int[] row : costMatrix) {
                if (row[j] < min) {
                    min = row[j];
                }
            }
            for (int[] row : costMatrix) {
                row[j] -= min;
            }
        }
    }

    /**
     * Performs the main loop of the Hungarian algorithm.
     */
    private void solveReducedMatrix() {
        //Steps 0 and 1 have been preprocessed
        //Step 2 : initial zero starring
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (costMatrix[i][j] == 0 && starredCols[j] == -1) {
                    coveredCols[j] = true;
                    numberCoveredCols++;
                    starredRows[i] = j;
                    starredCols[j] = i;
                    break;
                }
            }
        }
        while (numberCoveredCols < nRows) {
            int[] position = primeZero();
            while (position == null){
                //Perform step 6
                //Get minimal unmarked value
                int min = Integer.MAX_VALUE;
                for (int i = 0; i < nRows; i++) {
                    if (coveredRows[i]) {
                        continue;
                    }
                    for (int j = 0; j < nCols; j++) {
                        if (coveredCols[j]) {
                            continue;
                        }
                        if (costMatrix[i][j] < min) {
                            min = costMatrix[i][j];
                            if (min == 1){
                                break;
                            }
                        }
                        if (min == 1){
                            break;
                        }
                    }
                }
                //modify the matrix
                for (int i = 0; i < nRows; i++) {
                    for (int j = 0; j < nCols; j++) {
                        if (!coveredRows[i]) {
                            /* If the row is uncovered and the column is covered, 
                        then it's a no-op: add and subtract the same value.
                             */
                            if (!coveredCols[j]) {
                                costMatrix[i][j] -= min;
                            }
                        } else if (coveredCols[j]) {
                            costMatrix[i][j] += min;
                        }
                    }
                }
                //go back to step 4
                position = primeZero();
            }
            //perform step 5
            invertPrimedAndStarred(position);
        }
        //format the result
        int assignmentIndex = 0;
        if (transposed){
            for (int i = 0; i < nCols; i++){
                rowAssignments[i] = starredCols[i];
                if (starredCols[i] != -1){
                    assignments[assignmentIndex][0] = starredCols[i];
                    assignments[assignmentIndex][1] = i;
                    assignmentIndex++;
                }
            }
            System.arraycopy(starredRows, 0, colAssignments, 0, nRows);
        } else {
        for (int i = 0; i < nRows; i++){
                rowAssignments[i] = starredRows[i];
                if (starredRows[i] != -1) {
                    assignments[assignmentIndex][0] = i;
                    assignments[assignmentIndex][1] = starredRows[i];
                    assignmentIndex++;
                }
            }
            System.arraycopy(starredCols, 0, colAssignments, 0, nCols);
        }
    }

    /**
     * Primes uncovered zeroes in the cost matrix.
     * Performs the fourth step of the Hungarian Algorithm.
     * @return the (rowIndex,colIndex) coordinates of the primed zero to star 
     * that has been found, or null if no such zero has been found.
     */
    private int[] primeZero() {
        Queue<Integer> uncoveredColumnQueue = new LinkedList<>();
        for (int i = 0; i < nRows; i++) {
            if (coveredRows[i]) {
                continue;
            }
            for (int j = 0; j < nCols; j++) {
                if (coveredCols[j] || costMatrix[i][j] > 0) {
                    continue;
                }
                //Found a non-covered zero
                primedRows[i] = j;
                primedCols[j] = i;
                if (starredRows[i] == -1) {
                    return new int[]{i,j};
                } else {
                    coveredRows[i] = true;
                    coveredCols[starredRows[i]] = false;
                    numberCoveredCols -= 1;
                    //ignore the rest of the row but handle the uncovered column
                    uncoveredColumnQueue.add(starredRows[i]);
                    break;
                }
            }
        }
        while (!uncoveredColumnQueue.isEmpty()){
            int j = uncoveredColumnQueue.remove();
            for (int i = 0; i < nRows; i++){
                if(coveredRows[i] || costMatrix[i][j] > 0) {
                    continue;
                }
                primedRows[i] = j;
                primedCols[j] = i;
                if (starredRows[i] == -1){
                    return new int[]{i,j};
                } else {
                    coveredRows[i] = true;
                    coveredCols[starredRows[i]] = false;
                    numberCoveredCols -= 1;
                    uncoveredColumnQueue.add(starredRows[i]);
                }
            }
        }
        return null;
    }
    
    /**
     * Stars selected primed zeroes to increase the line coverage of the matrix.
     * Performs the fifth step of the Hungarian Algorithm.
     * @param position array of size 2 containing the row and column indices of 
     * the first primed zero in the alternating series to modify.
     */
    private void invertPrimedAndStarred(int[] position){
        int currentRow = position[0];
        int currentCol = position[1];
        int tmp;
        starredRows[currentRow] = currentCol;
        while (starredCols[currentCol] != -1){
            //Move star to its new row in the column of the primed zero
            tmp = starredCols[currentCol];
            starredCols[currentCol] = currentRow;
            currentRow = tmp;
            //Move star to its new column in the column of the previously 
            //starred zero
            tmp = primedRows[currentRow];
            starredRows[currentRow] = tmp;
            currentCol = tmp;
        }
        //set starredCols of last changed zero and reset primes and lines covering
        starredCols[currentCol] = currentRow;
        for (int i = 0; i < coveredRows.length; i++){
            coveredRows[i] = false;
            primedRows[i] = -1;
        }
        //in next step, all columns containing a starred zero will be marked
        //--> do it right away
        for (int j = 0; j < nCols; j++){
            if(!coveredCols[j] && starredCols[j] != -1){
                numberCoveredCols++;
                coveredCols[j] = true;
            }
            //if a column contained a prime zero, it will still contain one
            //after the inversion, so the case where a column needs to be 
            //uncovered does not arise
            primedCols[j] = -1;
        }
    }

    /**
     * @return The internal state of the cost matrix.
     */
    int[][] getState() {
        return this.costMatrix;
    }

    /**
     * Checks the validity of the input cost matrix.
     * @param costMatrix the matrix to solve.
     * @throws IllegalArgumentException if {@code costMatrix } is not 
     * rectangular (e.g. rows do not all have the same length).
     */
    static void checkMatrixValidity(int[][] costMatrix)
            throws IllegalArgumentException{
        if (costMatrix == null){
            throw new IllegalArgumentException("input matrix was null");
        }
        if (costMatrix.length == 0){
            throw new IllegalArgumentException("input matrix was of length 0");
        }
        for (int[] row : costMatrix){
            if (row.length != costMatrix[0].length){
                throw new IllegalArgumentException("input matrix was not rectangular");
            }
        }
    }
}

TestArguments.java

package test.tools;

/**
 * Interface defining the general contract that inner classes should implement
 * to ease the unit testing.
 * 
 * Concrete classes implementing it should provide a unique constructor similar
 * to the main one of the class parameter, and override the toString object 
 * method.
 *
 * @param <T>   class under test: the arguments will be used to generate 
 * instances of that class.
 */
public interface TestArguments<T> {
    /**
     * Initialises an object to use in a test.
     * @return
     */
    T convert();
}

TestFrameWork.java

package test.tools;

import static org.junit.jupiter.api.DynamicContainer.dynamicContainer;
import static org.junit.jupiter.api.DynamicTest.dynamicTest;

import java.util.Map;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Stream;

import org.junit.jupiter.api.DynamicNode;
import org.junit.jupiter.api.DynamicTest;
import org.junit.jupiter.api.function.Executable;

public interface TestFrameWork<T, S extends TestArguments<T>> {
    /**
     * @return a {@link Stream} of arguments to initialise an object to test.
     */
    Stream<S> argumentsSupplier();
    
    default String testName(String methodName, S args){
        return String.format("%s.%s on %s", 
                this.getClass().getCanonicalName(), methodName, args);
    }
    /**
     * Forges a {@link DynamicTest} to run the input test for each element 
     * returned by the implementation of 
     * {@link TestFrameWork#argumentsSupplier()}.
     * @param methodName    to set as the test name.
     * @param tester        to run as the test.
     * @return  a stream of nodes running the test.
     */
    default Stream<DynamicTest> test(String methodName, Consumer<S> tester){
        return test(argumentsSupplier(), methodName, tester);
    }

    /**
     * Forges a {@link Stream} of {@link DynamicNode} that runs in independent
     * {@link DynamicTest} instances each {@link Executable} returned by the 
     * input {@link Function} on each element returned by the implementation of
     * {@link TestFrameWork#argumentsSupplier()}.
     * @param methodName    to set as the test container's name.
     * @param testerStream  to generate the {@link Stream} of test using for 
     * each element the {@link String} as a suffix in the test name and the
     * {@link Executable} as the test to run.
     * @return  a stream of nodes running the tests.
     */
    default Stream<DynamicNode> testContainer(String methodName, 
            Function<S, Stream<Map.Entry<String, Executable>>> testerStream){
        return testContainer(argumentsSupplier(), methodName, testerStream);
    }
    /**
     * Forges a {@link DynamicTest} to run the input test for each element 
     * of a {@link Stream} of arguments.
     * @param stream        of arguments, the tests will be run on each 
     * element.
     * @param methodName    to set as the test name.
     * @param tester        to run as the test.
     * @return  a stream of nodes running the tests.
     */
    default Stream<DynamicTest> test(Stream<S> stream, String methodName, Consumer<S> tester){
        return stream.map(args
                -> dynamicTest(testName(methodName, args), () -> tester.accept(args)));
    }
    /**
     * Forges a {@link Stream} of {@link DynamicNode} that runs in independent
     * {@link DynamicTest} instances each {@link Executable} returned by the 
     * input {@link Function} on each element of the input {@link Stream}.
     * @param stream        of arguments, the tests will be run on each 
     * element.
     * @param methodName    to set as the test container's name.
     * @param testerStream  to generate the {@link Stream} of test using for 
     * each element the {@link String} as a suffix in the test name and the
     * {@link Executable} as the test to run.
     * @return  a stream of nodes running the tests.
     */
    default Stream<DynamicNode> testContainer(Stream<S> stream, String methodName, 
            Function<S, Stream<Map.Entry<String, Executable>>> testerStream){
        return stream.map(args
                -> {
                    String message = testName(methodName, args);
                    return dynamicContainer(message, 
                            testerStream.apply(args).map(entry 
                                    -> dynamicTest(message + entry.getKey(), entry.getValue())));
                });
    }
}

HungarianSolverTest.java

package AssignmentProblem;

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Stream;
import org.junit.jupiter.api.Assertions;
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import org.junit.jupiter.api.DynamicTest;
import org.junit.jupiter.api.TestFactory;
import test.tools.TestArguments;
import test.tools.TestFrameWork;

public class HungarianSolverTest implements TestFrameWork<HungarianSolver, HungarianArgument> {

    @TestFactory
    public Stream<DynamicTest> testInitialiseValidInput() {
        //Check that initialise does not crash on valid input.
        //Correctness of the result is checked in tests linked to the methods getting the results.
        return test("initialise (valid input)", v -> v.convert());
    }
    
    @TestFactory
    public Stream<DynamicTest> testInitialiseInvalidInput(){
        Stream<HungarianArgument> cases = Stream.of(
                new HungarianArgument(null, null, null, null, "null cost matrix"),
                new HungarianArgument(new int[0][0], null, null, null, "size 0 cost matrix"),
                new HungarianArgument(new int[][]{{0}, {0,1}, {0,1,2},{0,1},{0}}, null, null, null, "non-rectangular cost matrix"));
        return test(cases, 
                "initialise (invalid input)", 
                v -> Assertions.assertThrows(IllegalArgumentException.class, 
                        () -> v.convert()));
    }

    @TestFactory
    public Stream<DynamicTest> testGetRowAssignments() {
        return test("getRowAssignments", v -> assertArrayEquals(v.expectedRowAssignment, v.convert().getRowAssignments()));
    }

    @TestFactory
    public Stream<DynamicTest> testGetColumnAssignemnts() {
        return test("getColumnAssignments", v -> assertArrayEquals(v.expectedColAssignment, v.convert().getColumnAssignemnts()));
    }

    @TestFactory
    public Stream<DynamicTest> testGetAssignments() {
        Comparator<int[]> comparator = (first, second) ->
            Integer.compare(first[0], second[0]) == 0 ? Integer.compare(first[1], second[1]) : Integer.compare(first[0], second[0]);
        return test("getAssignments", v-> {
            /*
            There is no contract on the ordering of the result values.
            */
            int[][] assignments = v.convert().getAssignments();
            Arrays.sort(assignments, comparator);
            Arrays.sort(v.expectedMatrixResult, comparator);
            assertArrayEquals(v.expectedMatrixResult, assignments);
        });
    }

    @TestFactory
    public Stream<DynamicTest> testReduceInitialMatrix() {
        Stream<HungarianArgument> cases = Stream.of(
                new HungarianArgument(new int[][]{{25, 40, 35}, {40, 60, 35}, {20, 40, 25}}, 
                        new int[][]{{0, 0, 10}, {5, 10, 0}, {0, 5, 5}}, 
                        null, null, "square 3*3 matrix"),
                new HungarianArgument(new int[][]{{150, 400, 450},{200, 600, 350}, {200, 400, 250}},
                        new int[][]{{0, 50, 250}, {0, 200, 100}, {0, 0, 0}},
                        null, null, "second square 3*3 matrix"),
                new HungarianArgument(new int[][]{{70, 40, 20, 55},{65, 60, 45, 90},{30, 45, 50, 75},{25,0,55,40}},
                        new int[][]{{50, 20, 0, 0},{20, 15, 0, 10},{0, 15, 20, 10},{25, 0, 55, 5}},
                        null, null, "square 4*4 with initial zeroes matrix"),
                new HungarianArgument(new int[][]{{1,2,25,13},{5,7,25,15},{10,13,16,13},{17,21,11,18},{15,15,15,14}},
                        new int[][]{{0,2,9,16,13},{0,3,11,19,12},{14,12,5,0,3},{0,0,0,5,0}}, 
                        null, null, "5*4 matrix without initial zeroes")
        );
        return test(cases, 
                "reduceInitialMatrix", 
                v -> {
                    HungarianSolver solver = v.convertWithConstructor();
                    solver.reduceInitialMatrix();
                    assertArrayEquals(v.expectedMatrixResult, solver.getState());
                });
    }

    @Override
    public Stream<HungarianArgument> argumentsSupplier() {
        int worstCaseSize = 200;
        int[][] worstCaseMatrix = new int[worstCaseSize][worstCaseSize];
        for (int i = 0; i < worstCaseMatrix.length; i++) {
            for (int j = 0; j < worstCaseMatrix[i].length; j++){
                worstCaseMatrix[i][j] = (i+1)*(j+1);
            }
        }
        int[] worstCaseLinearExpectation = new int[worstCaseSize];
        Arrays.setAll(worstCaseLinearExpectation, i -> worstCaseSize-i-1);
        int[][] worstCaseExpectedAssignments = new int[worstCaseSize][2];
        for (int i = 0; i < worstCaseSize; i++){
            worstCaseExpectedAssignments[i][0] = i;
            worstCaseExpectedAssignments[i][1] = worstCaseSize-i-1;
        }
        return Stream.of(new HungarianArgument(new int[][]{{2500, 4000, 3500}, {4000, 6000, 3500}, {2000, 4000, 2500}},
                new int[][]{{0,1},{1,2},{2,0}}, new int[]{1,2,0}, new int[]{2,0,1}, "simple 3*3 matrix"),
                new HungarianArgument(new int[][]{{2000,6000,3500},{1500, 4000, 4500},{2000,4000,2500}},
                new int[][]{{0,0},{1,1},{2,2}}, new int[]{0,1,2}, new int[]{0,1,2}, "mildly complex 3*3 matrix"),
                new HungarianArgument(new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12}},
                new int[][]{{0,0},{1,1},{2,2}}, new int[]{0,1,2}, new int[]{0,1,2,-1}, "complex 4*3 matrix with equality case"),
                new HungarianArgument(new int[][]{{1,2,25,13},{5,7,25,15},{10,13,16,13},{17,21,11,18},{15,15,15,14}},
                new int[][]{{0,1},{1,0},{2,3},{3,2}}, new int[]{1,0,3,2,-1}, new int[]{1,0,3,2}, "first complex 5*4 matrix without equality case"),
                new HungarianArgument(new int[][]{{1,2,25,13},{5,7,25,15},{10,13,16,14},{17,21,11,18},{15,15,15,13}},
                new int[][]{{0,1},{1,0},{2,3},{3,2}}, new int[]{1,0,3,2,-1}, new int[]{1,0,3,2}, "second complex 5*4 matrix without equality case"),
                new HungarianArgument(worstCaseMatrix, worstCaseExpectedAssignments,
                worstCaseLinearExpectation, worstCaseLinearExpectation, "worst case " + worstCaseSize + "*" + worstCaseSize + " matrix")
        );
    }
    
}

class HungarianArgument implements TestArguments<HungarianSolver>{
    final int[][] costMatrix;
    final int[][] expectedMatrixResult;
    final int[] expectedRowAssignment;
    final int[] expectedColAssignment;
    private final String name;
    HungarianArgument(int[][] costMatrix, int[][] expectedMatrixResult, 
            int[] expectedRowAssignment, int[] expectedColAssignment,
            String name){
        this.costMatrix = costMatrix;
        this.expectedMatrixResult = expectedMatrixResult;
        this.expectedRowAssignment = expectedRowAssignment;
        this.expectedColAssignment = expectedColAssignment;
        this.name = name;
    }
    @Override
    public HungarianSolver convert() {
        return HungarianSolver.initialise(costMatrix);
    }
    public HungarianSolver convertWithConstructor(){
        return new HungarianSolver(costMatrix);
    }
    
    @Override
    public String toString(){
        return this.name;
    }
}

Answer 1

Your nose is correct. What you smell is the effect of voids that mutate the state of the class, so you need to expose the internals.

First step would be to split initialization into a factory.

public class HungarianSolverFactory
{
    public static HungarianSolver hungarianSolverSolve(int[][] costMatrix)
    {
        HungarianSolver result = hungarianSolver(costMatrix);
        result.reduceInitialMatrix();
        result.solveReducedMatrix();

        return result;
    }

    public static HungarianSolver hungarianSolver(int[][] costMatrix)
    {
        int[][] costMatrixFinal;
        int nRows;
        int nCols;
        boolean transposed;

        HungarianSolver.checkMatrixValidity(costMatrix);
        if (costMatrix.length > costMatrix[0].length)
        {
            //flip matrix to have more columns than rows
            transposed = true;
            nRows = costMatrix[0].length;
            nCols = costMatrix.length;
            costMatrixFinal = new int[nRows][nCols];
            for (int i = 0; i < nRows; i++)
            {
                for (int j = 0; j < nCols; j++)
                {
                    costMatrixFinal[i][j] = costMatrix[j][i];
                }
            }
        }
        else
        {
            costMatrixFinal = costMatrix;
            nRows = costMatrix.length;
            nCols = costMatrix[0].length;
            transposed = false;
        }

        int[][] assignments = init2DIntArray(nRows, 2, -1);
        int[] rowAssignments = initIntArray(transposed ? nCols : nRows, -1);
        int[] colAssignments = initIntArray(transposed ? nRows : nCols, -1);
        boolean[] coveredRows = new boolean[nRows];
        boolean[] coveredCols = new boolean[nCols];
        int[] starredRows = initIntArray(nRows, -1);
        int[] starredCols = initIntArray(nCols, -1);
        int[] primedRows = initIntArray(nRows, -1);
        int[] primedCols = initIntArray(nCols, -1);

        return new HungarianSolver(costMatrixFinal, assignments, rowAssignments,
                colAssignments, nRows, nCols, coveredRows, coveredCols, starredRows,
                starredCols, primedRows, primedCols, transposed
        );
    }

    private static int[] initIntArray(
            int length,
            int value
    )
    {
        int[] arr = new int[length];
        Arrays.fill(arr, value);
        return arr;
    }

    private static int[][] init2DIntArray(
            int height,
            int width,
            int value
    )
    {
        int[][] arr = new int[height][width];
        for (int[] arr1D : arr)
        {
            Arrays.fill(arr1D, value);
        }

        return arr;
    }
}

The state of the solver is also huge. I would split the algorithm into three parts: HungarianAssignmentOptimizer, HungarianSolver, HungarianMatrixReducer.

I will show what optimizer would look like approximately. For the other two just reuse what you have and make sure you return things out of methods.

class HungarianAssignmentOptimizer
{
    private HungarianSolver hungarianSolver;
    private HungarianMatrixReducer hungarianMatrixReducer;

    public HungarianAssignmentOptimiser(
            HungarianSolver hungarianSolver,
            HungarianMatrixReducer hungarianMatrixReducer
    )
    {
        this.hungarianSolver = hungarianSolver;
        this.hungarianMatrixReducer = hungarianMatrixReducer;
    }

// you return assignments
    public int[][] solve(int[][] costMatrix) {
        int[][] reducedCostMatrix = this.hungarianMatrixReducer.reduce(costMatrix);
        return this.hungarianSolver.solveReducedMatrix(reducedCostMatrix);
    }
}

You can then easily test each part of the algorithm without it feeling weird being public (since it doesn't mutate the state of the object).

If you feel like you would need more parameters about the matrix, you can create a new class which would hold them (role of java 16 record).

class CostMatrix {
    public final int[][] costMatrix;
    public final int nRows;
    public final int nCols;
    public final boolean transposed;

    public CostMatrix(
            int[][] costMatrix,
            int nRows,
            int nCols,
            boolean transposed
    )
    {
        this.costMatrix = costMatrix;
        this.nRows = nRows;
        this.nCols = nCols;
        this.transposed = transposed;
    }
}

And then:

...

    public int[][] solve(CostMatrix costMatrix) {
        CostMatrix reducedCostMatrix = this.hungarianMatrixReducer.reduce(costMatrix);
        return this.hungarianSolver.solveReducedMatrix(reducedCostMatrix);
    }

Answer 2

This looks very nice, with well named variables and a thought out design, good class and method names. The code is probably only readable if you study the algorithm, but that's OK.

I'll make some remarks though, starting with HungarianSolver. I might need to post another answer to review the rest, 'cause there is a lot of code to handle.

The formatting is nice, but it might do with some additional white space between various lines and e.g. return new int[]{i,j};.

HungarianSolver

Generic remarks

First of all, this class should probably be made final. It is extremely unlikely that the algorithm itself will be altered, so having it made extendable makes little sense, especially since all the fields are private - and thus inaccessible for classes that extend this class - anyway. You would normally only use public and private or default / package only and private in this case, I suppose. Currently it is very much a hodge-podge of access modifiers, without any clear intent (except for everything marked private).

Second, the class seems to be both HungarianSolver and HungarianSolverResult in one. That can be a (somewhat questionable) design decision, but in that case I would recommend documenting it in the JavaDoc of the class.

Generally, we prefer private final over final private, it's not the recommended order.

The value -1 is used so much that it could do with a constant declaration to indicate what it means.

Code specific remarks

Remarks below the code fragments.

 * Implementation of the HungarianAlgorithm.

Even better if you can link to the algorithm; I don't know why HungarianAlgorithm is one word here.

 * ... The proper way to get
 * the solution of the assignment problem with a {@link HungarianSolver} is
 * to call {@link #initialise(int[][])} rather than directly the constructor.

So mark it private...

 * @param costMatrix

Undocumented parameter.

checkMatrixValidity(costMatrix);

You could make the costMatrix a separate class, so that you don't need to check the matrix in the constructor, and document the right way of constructing the instance in the class documentation instead. Note that it might be more logical to call it from the initialise call.

This method should probably be public, I don't see why the getters are public while you cannot inititialise the instance at the same level.

protected static HungarianSolver initialise(int[][] costMatrix) {

This one is now missing the documentation, and it is the preferred way of using the function.

return this.rowAssignments;

A minor remark is that you sometimes use this, and sometimes you don't.

A more grievous error is that it exposes the arrays used within the instance. Even if you'd have good reasons for that, you should at the very least document that - or return a deep copy of the array.

public int[] getColumnAssignemnts() {

This method is missing a JavaDoc comment, maybe it did something wrong, as it has also been misspelled :)

if (costMatrix[i][j] < min) {
    min = costMatrix[i][j];
    if (min == 1){
        break;
    }
}
if (min == 1){
    break;
}

That first if is spurious, the same check at the end will perform the same break; it is in the same scope of the for loop after all.

TestArguments

Not sure if this class is necessary.

This class should be named TestArgumentGenerator or something similar, in itself it is not plural.

 * @return

Undocumented return

 * Initialises an object to use in a test.

No, that would pre-suppose that the object exists. It generates a test instance of type T, you say so right in the class description.

HungarianSolverTest

Suddenly there is a loss of whitespace. If you think that it is not worth typing it, then try an formatter, readily available in e.g. Eclipse and probably all other significant IDEs.

I'm not sure why the constructor itself is not public, the rest seems to be public after all.