de.unihalle.informatik.MiToBo.math.optimization
Class MatchingBipartite_HungarianAlgorithm

java.lang.Object
  extended by de.unihalle.informatik.Alida.operator.ALDOperator
      extended by de.unihalle.informatik.MiToBo.core.operator.MTBOperator
          extended by de.unihalle.informatik.MiToBo.math.optimization.MatchingBipartite
              extended by de.unihalle.informatik.MiToBo.math.optimization.MatchingBipartite_HungarianAlgorithm
All Implemented Interfaces:
de.unihalle.informatik.Alida.datatypes.ALDConfigurationValidator

public class MatchingBipartite_HungarianAlgorithm
extends MatchingBipartite

Bipartite matching with Hungarian algorithm.

This implementation is done according to: Grosche, Ziegler, Ziegler and Zeidler, Teubner-Taschenbuch der Mathematik, Teil II, pp. 219 ff 7th edition, B.G. Teubner Verlagsgesellschaft Leipzig, 1995 It assumes a squared score matrix and tries to find the matching that optimizes the score. The scores should all be positive and per default the algorithm minimizes the overall score. Anyway, the operator can be configured so as to interprete the scores inversely, i.e. searching for the matching that maximizes the sum of scores.

Note, that this implementation is not well-suited for large matrices. The implementation is greedy, so do not expect too much in case of a large number of elements to be matched...

Author:
moeller

Nested Class Summary
static class MatchingBipartite_HungarianAlgorithm.ScoreInterpretation
          Matrix scores interpretation.
 
Nested classes/interfaces inherited from class de.unihalle.informatik.Alida.operator.ALDOperator
de.unihalle.informatik.Alida.operator.ALDOperator.HidingMode
 
Field Summary
protected  byte[][] chainMarkers
          Helper matrix for exchange chain extraction: 0 = unselected, 1 = selected.
protected  boolean[] colMarkers
          Array containing column marks.
protected  byte[][] elementMarkers
          Matrix for elements markers: 0 = no mark, 1 = starred, 2 = primed
protected  boolean junitTest
          Internal flag for interrupting recursive calls in unit testing.
protected  MatchingBipartite_HungarianAlgorithm.ScoreInterpretation matrixScore
          Score interpretation.
protected  int matrixSize
          Number of rows and columns, respectively.
protected  boolean[] rowMarkers
          Array containing row marks.
protected  double stageThreeMin
          Helper to make matrix minimum in stage three externally accessible.
protected  double[][] workingMatrix
          Local copy of matrix modified during calculations.
 
Fields inherited from class de.unihalle.informatik.MiToBo.math.optimization.MatchingBipartite
resultMatrix, scoreMatrix
 
Fields inherited from class de.unihalle.informatik.Alida.operator.ALDOperator
completeDAG, name, portHashAccess, verbose, versionProvider
 
Constructor Summary
protected MatchingBipartite_HungarianAlgorithm()
          Default constructor.
  MatchingBipartite_HungarianAlgorithm(double[][] smatrix, MatchingBipartite_HungarianAlgorithm.ScoreInterpretation o)
          Default constructor with parameters.
 
Method Summary
protected  void calcMatching_mainTest()
          Checks whether a valid solution has been found.
protected  void calcMatching_stageOne()
          Implements stage one: searching for new candidate matches.
protected  void calcMatching_stageThree()
          Implements stage three: decrease scores to generate new zero entries.
protected  void calcMatching_stageTwo(int r, int c)
          Implements stage two: extracting exchange chain.
protected  void calcMatching()
          Function calculating actual matching, to be implemented by subclasses.
protected  void init()
          Initializes the operator, i.e. allocates memory.
protected  void prepareMatching()
          Preprocess the matrix.
 void validateCustom()
           
 
Methods inherited from class de.unihalle.informatik.MiToBo.math.optimization.MatchingBipartite
getMatching, operate
 
Methods inherited from class de.unihalle.informatik.MiToBo.core.operator.MTBOperator
readResolve
 
Methods inherited from class de.unihalle.informatik.Alida.operator.ALDOperator
deserializeFromXmlFile, fieldContained, getALDPortHashAccessKey, getConstructionMode, getInInoutNames, getInInoutNames, getInNames, getInOutNames, getMissingRequiredInputs, getName, getNumParameters, getOutInoutNames, getOutNames, getParameter, getParameterDescriptor, getParameterNames, getSupplementalNames, getVerbose, getVersion, isConfigured, parametersToXmlObject, print, print, print, printInterface, printInterface, readHistory, reinitializeParameterDescriptors, runOp, runOp, runOp, serializeToXmlFile, setConstructionMode, setName, setParameter, setParametersFromXml, setParametersFromXml, setVerbose, toStringVerbose, unconfiguredItems, validate, validateGeneric, writeHistory, writeHistory, writeHistory, writeParametersToXml
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

chainMarkers

protected byte[][] chainMarkers
Helper matrix for exchange chain extraction: 0 = unselected, 1 = selected.


colMarkers

protected boolean[] colMarkers
Array containing column marks.


elementMarkers

protected byte[][] elementMarkers
Matrix for elements markers: 0 = no mark, 1 = starred, 2 = primed


junitTest

protected boolean junitTest
Internal flag for interrupting recursive calls in unit testing.


matrixScore

@Parameter(label="scoreInterpretation",
           required=true,
           type=INPUT,
           description="How to interpret the scores.")
protected MatchingBipartite_HungarianAlgorithm.ScoreInterpretation matrixScore
Score interpretation.


matrixSize

protected int matrixSize
Number of rows and columns, respectively.


rowMarkers

protected boolean[] rowMarkers
Array containing row marks.


stageThreeMin

protected double stageThreeMin
Helper to make matrix minimum in stage three externally accessible.


workingMatrix

protected double[][] workingMatrix
Local copy of matrix modified during calculations.

Constructor Detail

MatchingBipartite_HungarianAlgorithm

protected MatchingBipartite_HungarianAlgorithm()
                                        throws de.unihalle.informatik.Alida.exceptions.ALDOperatorException
Default constructor.

Throws:
de.unihalle.informatik.Alida.exceptions.ALDOperatorException

MatchingBipartite_HungarianAlgorithm

public MatchingBipartite_HungarianAlgorithm(double[][] smatrix,
                                            MatchingBipartite_HungarianAlgorithm.ScoreInterpretation o)
                                     throws de.unihalle.informatik.Alida.exceptions.ALDOperatorException
Default constructor with parameters.

The rows of the matrix should refer to one set of elements, and the cols to the second one. Matrix elements then give the matching scores for all pairs of possible matchings. Note that for this technique the score matrix needs to be square, otherwise an exception is thrown. Also it is assumed that all scores are larger than or equal to zero.

Parameters:
smatrix - Square matrix with pairwise scores.
Throws:
de.unihalle.informatik.Alida.exceptions.ALDOperatorException
Method Detail

calcMatching_mainTest

protected void calcMatching_mainTest()
Checks whether a valid solution has been found.


calcMatching_stageOne

protected void calcMatching_stageOne()
Implements stage one: searching for new candidate matches.


calcMatching_stageThree

protected void calcMatching_stageThree()
Implements stage three: decrease scores to generate new zero entries.


calcMatching_stageTwo

protected void calcMatching_stageTwo(int r,
                                     int c)
Implements stage two: extracting exchange chain.


calcMatching

protected void calcMatching()
Description copied from class: MatchingBipartite
Function calculating actual matching, to be implemented by subclasses.

Specified by:
calcMatching in class MatchingBipartite

init

protected void init()
Initializes the operator, i.e. allocates memory.


prepareMatching

protected void prepareMatching()
Preprocess the matrix.

The method first inverts all entries if large scores are better. Subsequently zeros are starred in the matrix, preferably so that each row and each column contains exactly one star. If this is possible a solution has already been found.


validateCustom

public void validateCustom()
                    throws de.unihalle.informatik.Alida.exceptions.ALDOperatorException
Overrides:
validateCustom in class de.unihalle.informatik.Alida.operator.ALDOperator
Throws:
de.unihalle.informatik.Alida.exceptions.ALDOperatorException