info.mrupp.isoak1
Class HungarianAlgorithm

java.lang.Object
  extended by info.mrupp.isoak1.HungarianAlgorithm

public class HungarianAlgorithm
extends java.lang.Object

The Hungarian algorithm (Kuhn-Munkres assignment algorithm). Computes an assignment of the rows to the columns of a matrix (or vice versa) with minimum or maximum value. Returns the value of the assignment and optionally the indices of the assignment.

Implementation based on the exposition by Bob Pilgrim.


Nested Class Summary
static class HungarianAlgorithm.OptimizationType
          Optimization type (either minimization or maximization of the assignment value).
 
Constructor Summary
HungarianAlgorithm()
          Initializes the optimizer.
 
Method Summary
 float hungarianAlgorithm(Array2Float matrix, HungarianAlgorithm.OptimizationType type, int[] assignment)
          The Hungarian algorithm.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

HungarianAlgorithm

public HungarianAlgorithm()
Initializes the optimizer. Only minimal memory is reserved. Additional memory will be reserved depending on passed problem instances. Reuse HungarianAlgorithm objects (one per thread).

Method Detail

hungarianAlgorithm

public float hungarianAlgorithm(Array2Float matrix,
                                HungarianAlgorithm.OptimizationType type,
                                int[] assignment)
The Hungarian algorithm. Computes an optimal assignment for a given matrix.

Parameters:
matrix - the matrix for which the assignment is computed.
type - indicates wether a minimum value or maximum value assignment is computed.
assignment - a buffer where the (zero-based) indices of the computed assignment are stored. Can be null if the indices are not needed.
Returns:
the value of the optimal assignment.