algorithm.matching
Class HungarianAlgorithm

java.lang.Object
  algorithm.matching.HungarianAlgorithm

All Implemented Interfaces:

MatchingAlgorithm

public class HungarianAlgorithm
extends java.lang.Object
implements MatchingAlgorithm

An implementation of the classic hungarian algorithm for the assignment problem. Copyright 2007 Gary Baker (GPL v3)

Author:

gbaker

Field Summary

private static org.apache.log4j.Logger

logger logger instance

Constructor Summary

HungarianAlgorithm()

Method Summary

private boolean	allAreCovered(int[] coveredCols) Test if all columns are covered.
MatchList	computeAssignments(double[][] input, Config config) Compute the assignments for the given cost matrix.
private void	coverColumnsOfStarredZeroes(int[] starsByCol, int[] coveredCols) just marke the columns covered for any coluimn containing a starred zero
private void	incrementSetOfStarredZeroes(int[] unpairedZeroPrime, int[] starsByRow, int[] starsByCol, int[] primesByRow)
private void	initStars(float[][] costMatrix, int[] starsByRow, int[] starsByCol) init starred zeroes for each column find the first zero if there is no other starred zero in that row then star the zero, cover the column and row and go onto the next column
private void	makeMoreZeroes(float[][] matrix, int[] coveredRows, int[] coveredCols)
private static double[][]	prepareMatrix(double[][] weight_origin, Config config) prepare the stored weight function so that it can be used by hungarian algorithm.
private int[]	primeSomeUncoveredZero(float[][] matrix, int[] primesByRow, int[] coveredRows, int[] coveredCols) finds some uncovered zero and primes it
private void	reduceMatrix(float[][] matrix) the first step of the hungarian algorithm is to find the smallest element in each row and subtract it's values from all elements in that row

Methods inherited from class java.lang.Object

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

Field Detail

logger

private static org.apache.log4j.Logger logger

logger instance

Constructor Detail

HungarianAlgorithm

public HungarianAlgorithm()

Method Detail

computeAssignments

public MatchList computeAssignments(double[][] input,
                                    Config config)
                             throws InvalidWeightFunctionGivenException

Description copied from interface: MatchingAlgorithm

Compute the assignments for the given cost matrix. Returned is a matchlist containing the indices in the cost matrix for the matched elements.

Specified by:

computeAssignments in interface MatchingAlgorithm

Parameters:

input - the cost matrix

config - the configuration parameters for this algorithm

Returns:

matchlist, containing the "cheapaest" matching

Throws:

InvalidWeightFunctionGivenException

prepareMatrix

private static double[][] prepareMatrix(double[][] weight_origin,
                                        Config config)
                                 throws InvalidWeightFunctionGivenException

prepare the stored weight function so that it can be used by hungarian algorithm. these preparations include:

• create a copy of the matrix, as we need the original one later
• if it is not a square matrix, append dummy rows or columns. as a dummy value, we have the maximum entry in the whole matrix.

Returns:

a weight matrix with the alterations described above

Throws:

InvalidWeightFunctionGivenException

allAreCovered

private boolean allAreCovered(int[] coveredCols)

Test if all columns are covered.

Parameters:

coveredCols - the covered columns

Returns:

true if all columns are covered, false if not

reduceMatrix

private void reduceMatrix(float[][] matrix)

the first step of the hungarian algorithm is to find the smallest element in each row and subtract it's values from all elements in that row

initStars

private void initStars(float[][] costMatrix,
                       int[] starsByRow,
                       int[] starsByCol)

init starred zeroes for each column find the first zero if there is no other starred zero in that row then star the zero, cover the column and row and go onto the next column

Parameters:

costMatrix -

starsByRow -

starsByCol -

coverColumnsOfStarredZeroes

private void coverColumnsOfStarredZeroes(int[] starsByCol,
                                         int[] coveredCols)

just marke the columns covered for any coluimn containing a starred zero

Parameters:

starsByCol -

coveredCols -

primeSomeUncoveredZero

private int[] primeSomeUncoveredZero(float[][] matrix,
                                     int[] primesByRow,
                                     int[] coveredRows,
                                     int[] coveredCols)

finds some uncovered zero and primes it

Parameters:

matrix - the cost matrix

primesByRow - the primed rows

coveredRows - the primes columns

coveredCols - all covered columns

Returns:

the indices of the primed zero, null if no zero could be primed

incrementSetOfStarredZeroes

private void incrementSetOfStarredZeroes(int[] unpairedZeroPrime,
                                         int[] starsByRow,
                                         int[] starsByCol,
                                         int[] primesByRow)

Parameters:

unpairedZeroPrime -

starsByRow -

starsByCol -

primesByRow -

makeMoreZeroes

private void makeMoreZeroes(float[][] matrix,
                            int[] coveredRows,
                            int[] coveredCols)