Class AssignmentProblem


  • public class AssignmentProblem
    extends Object
    The AssignmentProblem class represents a data type for computing an optimal solution to an n-by-n assignment problem. The assignment problem is to find a minimum weight matching in an edge-weighted complete bipartite graph.

    The data type supplies methods for determining the optimal solution and the corresponding dual solution.

    This implementation uses the successive shortest paths algorithm. The order of growth of the running time in the worst case is O(n^3 log n) to solve an n-by-n instance.

    This computes correct results if all arithmetic performed is without floating-point rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 252.

    For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne
    • Constructor Detail

      • AssignmentProblem

        public AssignmentProblem​(double[][] weight)
        Determines an optimal solution to the assignment problem.
        Parameters:
        weight - the n-by-n matrix of weights
        Throws:
        IllegalArgumentException - unless all weights are nonnegative
        IllegalArgumentException - if weight is null
    • Method Detail

      • dualRow

        public double dualRow​(int i)
        Returns the dual optimal value for the specified row.
        Parameters:
        i - the row index
        Returns:
        the dual optimal value for row i
        Throws:
        IllegalArgumentException - unless 0 <= i < n
      • dualCol

        public double dualCol​(int j)
        Returns the dual optimal value for the specified column.
        Parameters:
        j - the column index
        Returns:
        the dual optimal value for column j
        Throws:
        IllegalArgumentException - unless 0 <= j < n
      • sol

        public int sol​(int i)
        Returns the column associated with the specified row in the optimal solution.
        Parameters:
        i - the row index
        Returns:
        the column matched to row i in the optimal solution
        Throws:
        IllegalArgumentException - unless 0 <= i < n
      • weight

        public double weight()
        Returns the total weight of the optimal solution
        Returns:
        the total weight of the optimal solution
      • main

        public static void main​(String[] args)
        Unit tests the AssignmentProblem data type. Takes a command-line argument n; creates a random n-by-n matrix; solves the n-by-n assignment problem; and prints the optimal solution.
        Parameters:
        args - the command-line arguments