|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectde.unihalle.informatik.Alida.operator.ALDOperator
de.unihalle.informatik.MiToBo.core.operator.MTBOperator
de.unihalle.informatik.MiToBo.math.optimization.MatchingBipartite
de.unihalle.informatik.MiToBo.math.optimization.MatchingBipartite_HungarianAlgorithm
public class MatchingBipartite_HungarianAlgorithm
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...
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 |
---|
protected byte[][] chainMarkers
protected boolean[] colMarkers
protected byte[][] elementMarkers
protected boolean junitTest
@Parameter(label="scoreInterpretation", required=true, type=INPUT, description="How to interpret the scores.") protected MatchingBipartite_HungarianAlgorithm.ScoreInterpretation matrixScore
protected int matrixSize
protected boolean[] rowMarkers
protected double stageThreeMin
protected double[][] workingMatrix
Constructor Detail |
---|
protected MatchingBipartite_HungarianAlgorithm() throws de.unihalle.informatik.Alida.exceptions.ALDOperatorException
de.unihalle.informatik.Alida.exceptions.ALDOperatorException
public MatchingBipartite_HungarianAlgorithm(double[][] smatrix, MatchingBipartite_HungarianAlgorithm.ScoreInterpretation o) throws de.unihalle.informatik.Alida.exceptions.ALDOperatorException
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.
smatrix
- Square matrix with pairwise scores.
de.unihalle.informatik.Alida.exceptions.ALDOperatorException
Method Detail |
---|
protected void calcMatching_mainTest()
protected void calcMatching_stageOne()
protected void calcMatching_stageThree()
protected void calcMatching_stageTwo(int r, int c)
protected void calcMatching()
MatchingBipartite
calcMatching
in class MatchingBipartite
protected void init()
protected void prepareMatching()
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.
public void validateCustom() throws de.unihalle.informatik.Alida.exceptions.ALDOperatorException
validateCustom
in class de.unihalle.informatik.Alida.operator.ALDOperator
de.unihalle.informatik.Alida.exceptions.ALDOperatorException
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |