Package edu.princeton.cs.algs4

Class AssignmentProblem

Object

edu.princeton.cs.algs4.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 2⁵².

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

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor	Description
AssignmentProblem(double[][] weight)	Determines an optimal solution to the assignment problem.

Method Summary

Modifier and Type	Method	Description
double	dualCol(int j)	Returns the dual optimal value for the specified column.
double	dualRow(int i)	Returns the dual optimal value for the specified row.
static void	main(String[] args)	Unit tests the AssignmentProblem data type.
int	sol(int i)	Returns the column associated with the specified row in the optimal solution.
double	weight()	Returns the total weight of the optimal solution

Methods inherited from class java.lang.Object

clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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