de.unihalle.informatik.MiToBo.math.optimization

Class MatchingBipartite_HungarianAlgorithm

java.lang.Object

de.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

All Implemented Interfaces:

de.unihalle.informatik.Alida.datatypes.ALDConfigurationValidator, de.unihalle.informatik.Alida.operator.events.ALDOperatorExecutionProgressEventListener, EventListener

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

Nested Classes

Modifier and Type	Class and Description
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, de.unihalle.informatik.Alida.operator.ALDOperator.HistoryConstructionMode

Field Summary

Fields

Modifier and Type	Field and Description
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, operatorExecutionEventlistenerList, portHashAccess, verbose, versionProvider

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	MatchingBipartite_HungarianAlgorithm() Default constructor.
	MatchingBipartite_HungarianAlgorithm(double[][] smatrix, MatchingBipartite_HungarianAlgorithm.ScoreInterpretation o) Default constructor with parameters.

Method Summary

Modifier and Type	Method and Description
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

addOperatorExecutionProgressEventListener, addParameter, addParameter, addParameterUnconditioned, fieldContained, fireOperatorExecutionProgressEvent, getALDPortHashAccessKey, getConstructionMode, getDocumentation, getHidingMode, getInactiveParameterNames, getInInoutNames, getInInoutNames, getInNames, getInOutNames, getMissingRequiredInputs, getName, getNumParameters, getOutInoutNames, getOutNames, getParameter, getParameterDescriptor, getParameterDescriptorUnconditioned, getParameterNames, getParameterUnconditioned, getSupplementalNames, getVerbose, getVersion, handleOperatorExecutionProgressEvent, hasInOutParameters, hasParameter, isAnnotatedParameter, isConfigured, print, print, print, printInterface, printInterface, readHistory, reinitializeParameterDescriptors, removeOperatorExecutionProgressEventListener, removeParameter, runOp, runOp, runOp, setConstructionMode, setConstructionMode, setConstructionMode, setHidingMode, setName, setParameter, setParameterUnconditioned, setVerbose, toStringVerbose, unconfiguredItems, validate, validateGeneric, writeHistory, writeHistory, writeHistory

Methods inherited from class java.lang.Object

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

Field Detail

rowMarkers

protected boolean[] rowMarkers

Array containing row marks.

colMarkers

protected boolean[] colMarkers

Array containing column marks.

elementMarkers

protected byte[][] elementMarkers

Matrix for elements markers: 0 = no mark, 1 = starred, 2 = primed

workingMatrix

protected double[][] workingMatrix

Local copy of matrix modified during calculations.

matrixSize

protected int matrixSize

Number of rows and columns, respectively.

chainMarkers

protected byte[][] chainMarkers

Helper matrix for exchange chain extraction: 0 = unselected, 1 = selected.

junitTest

protected boolean junitTest

Internal flag for interrupting recursive calls in unit testing.

stageThreeMin

protected double stageThreeMin

Helper to make matrix minimum in stage three externally accessible.

matrixScore

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

Score interpretation.

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

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

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.

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_stageTwo

protected void calcMatching_stageTwo(int r,
                                     int c)

Implements stage two: extracting exchange chain.

calcMatching_stageThree

protected void calcMatching_stageThree()

Implements stage three: decrease scores to generate new zero entries.