org.openimaj.math.combinatorics.optimisation

## Class HungarianAlgorithm

• java.lang.Object
• org.openimaj.math.combinatorics.optimisation.HungarianAlgorithm

• ```public class HungarianAlgorithm
extends Object```
An implementation of the Hungarian algorithm for solving the assignment problem. An instance of the assignment problem consists of a number of workers along with a number of jobs and a cost matrix which gives the cost of assigning the i'th worker to the j'th job at position (i, j). The goal is to find an assignment of workers to jobs so that no job is assigned more than one worker and so that no worker is assigned to more than one job in such a manner so as to minimize the total cost of completing the jobs.

An assignment for a cost matrix that has more workers than jobs will necessarily include unassigned workers, indicated by an assignment value of -1; in no other circumstance will there be unassigned workers. Similarly, an assignment for a cost matrix that has more jobs than workers will necessarily include unassigned jobs; in no other circumstance will there be unassigned jobs. For completeness, an assignment for a square cost matrix will give exactly one unique worker to each job.

This version of the Hungarian algorithm runs in time O(n^3), where n is the maximum among the number of workers and the number of jobs.

Author:
Kevin L. Stern
• ### Constructor Summary

Constructors
Constructor and Description
`HungarianAlgorithm(double[][] costMatrix)`
Construct an instance of the algorithm.
`HungarianAlgorithm(Jama.Matrix costMatrix)`
Construct an instance of the algorithm.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`protected void` `computeInitialFeasibleSolution()`
Compute an initial feasible solution by assigning zero labels to the workers and by assigning to each job a label equal to the minimum cost among its incident edges.
`int[]` `execute()`
Execute the algorithm.
`protected void` `executePhase()`
Execute a single phase of the algorithm.
`protected int` `fetchUnmatchedWorker()`
`protected void` `greedyMatch()`
Find a valid matching by greedily selecting among zero-cost matchings.
`protected void` `initializePhase(int w)`
Initialize the next phase of the algorithm by clearing the committed workers and jobs sets and by initializing the slack arrays to the values corresponding to the specified root worker.
`protected void` ```match(int w, int j)```
Helper method to record a matching between worker w and job j.
`protected void` `reduce()`
Reduce the cost matrix by subtracting the smallest element of each row from all elements of the row as well as the smallest element of each column from all elements of the column.
`protected void` `updateLabeling(double slack)`
Update labels with the specified slack by adding the slack value for committed workers and by subtracting the slack value for committed jobs.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### HungarianAlgorithm

`public HungarianAlgorithm(Jama.Matrix costMatrix)`
Construct an instance of the algorithm.
Parameters:
`costMatrix` - the cost matrix, where matrix[i][j] holds the cost of assigning worker i to job j, for all i, j. The cost matrix must not be irregular in the sense that all rows must be the same length.
• #### HungarianAlgorithm

`public HungarianAlgorithm(double[][] costMatrix)`
Construct an instance of the algorithm.
Parameters:
`costMatrix` - the cost matrix, where matrix[i][j] holds the cost of assigning worker i to job j, for all i, j. The cost matrix must not be irregular in the sense that all rows must be the same length.
• ### Method Detail

• #### computeInitialFeasibleSolution

`protected void computeInitialFeasibleSolution()`
Compute an initial feasible solution by assigning zero labels to the workers and by assigning to each job a label equal to the minimum cost among its incident edges.
• #### execute

`public int[] execute()`
Execute the algorithm.
Returns:
the minimum cost matching of workers to jobs based upon the provided cost matrix. A matching value of -1 indicates that the corresponding worker is unassigned.
• #### executePhase

`protected void executePhase()`
Execute a single phase of the algorithm. A phase of the Hungarian algorithm consists of building a set of committed workers and a set of committed jobs from a root unmatched worker by following alternating unmatched/matched zero-slack edges. If an unmatched job is encountered, then an augmenting path has been found and the matching is grown. If the connected zero-slack edges have been exhausted, the labels of committed workers are increased by the minimum slack among committed workers and non-committed jobs to create more zero-slack edges (the labels of committed jobs are simultaneously decreased by the same amount in order to maintain a feasible labeling).

The runtime of a single phase of the algorithm is O(n^2), where n is the dimension of the internal square cost matrix, since each edge is visited at most once and since increasing the labeling is accomplished in time O(n) by maintaining the minimum slack values among non-committed jobs. When a phase completes, the matching will have increased in size.

• #### fetchUnmatchedWorker

`protected int fetchUnmatchedWorker()`
Returns:
the first unmatched worker or `dim` if none.
• #### greedyMatch

`protected void greedyMatch()`
Find a valid matching by greedily selecting among zero-cost matchings. This is a heuristic to jump-start the augmentation algorithm.
• #### initializePhase

`protected void initializePhase(int w)`
Initialize the next phase of the algorithm by clearing the committed workers and jobs sets and by initializing the slack arrays to the values corresponding to the specified root worker.
Parameters:
`w` - the worker at which to root the next phase.
• #### match

```protected void match(int w,
int j)```
Helper method to record a matching between worker w and job j.
• #### reduce

`protected void reduce()`
Reduce the cost matrix by subtracting the smallest element of each row from all elements of the row as well as the smallest element of each column from all elements of the column. Note that an optimal assignment for a reduced cost matrix is optimal for the original cost matrix.
• #### updateLabeling

`protected void updateLabeling(double slack)`
Update labels with the specified slack by adding the slack value for committed workers and by subtracting the slack value for committed jobs. In addition, update the minimum slack values appropriately.