Module org.jgrapht.core
Package org.jgrapht.alg.matching
Class KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E>
java.lang.Object
org.jgrapht.alg.matching.KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E>
- Enclosing class:
KuhnMunkresMinimalWeightBipartitePerfectMatching<V,
E>
static class KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E>
extends Object
The actual implementation.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprotected class
Aggregates utilities to extend matching -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int[]
``columnMatched[i]'' is the column # of the ZERO matched at the $i$-th row(package private) boolean[]
Columns coverage bit-maskprivate double[][]
Cost matrixprivate double[][]
Excess matrixprivate int[]
``rowMatched[j]'' is the row # of the ZERO matched at the $j$-th column(package private) boolean[]
Rows coverage bit-mask -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected int[]
Gets costs-matrix as input and returns assignment of tasks (designated by the columns of cost-matrix) to the workers (designated by the rows of the cost-matrix) so that to MINIMIZE total tasks-tackling costs(package private) int
Builds maximal matching corresponding to the given excess-matrix(package private) void
Builds vertex-cover given built up matching(package private) void
Extends equality-graph subtracting minimal excess from all the COLUMNS UNCOVERED and adding it to the all ROWS COVERED(package private) double[][]
Composes excess-matrix corresponding to the given cost-matrixprivate static boolean
minimal
(int[] match, boolean[] rowsCovered, boolean[] colsCovered) Assures given column-n-rows-coverage/zero-matching to be minimal/maximalprivate static int
uncovered
(double[][] excessMatrix, boolean[] rowsCovered, boolean[] colsCovered) Accounts for zeroes being uncovered
-
Field Details
-
costMatrix
private double[][] costMatrixCost matrix -
excessMatrix
private double[][] excessMatrixExcess matrix -
rowsCovered
boolean[] rowsCoveredRows coverage bit-mask -
columnsCovered
boolean[] columnsCoveredColumns coverage bit-mask -
columnMatched
private int[] columnMatched``columnMatched[i]'' is the column # of the ZERO matched at the $i$-th row -
rowMatched
private int[] rowMatched``rowMatched[j]'' is the row # of the ZERO matched at the $j$-th column
-
-
Constructor Details
-
KuhnMunkresMatrixImplementation
Construct new instance- Parameters:
g
- the input graphs
- first partition of the vertex sett
- second partition of the vertex set
-
-
Method Details
-
buildMatching
protected int[] buildMatching()Gets costs-matrix as input and returns assignment of tasks (designated by the columns of cost-matrix) to the workers (designated by the rows of the cost-matrix) so that to MINIMIZE total tasks-tackling costs- Returns:
- assignment of tasks
-
makeExcessMatrix
double[][] makeExcessMatrix()Composes excess-matrix corresponding to the given cost-matrix -
buildMaximalMatching
int buildMaximalMatching()Builds maximal matching corresponding to the given excess-matrix- Returns:
- size of a maximal matching built
-
buildVertexCoverage
void buildVertexCoverage()Builds vertex-cover given built up matching -
extendEqualityGraph
void extendEqualityGraph()Extends equality-graph subtracting minimal excess from all the COLUMNS UNCOVERED and adding it to the all ROWS COVERED -
minimal
private static boolean minimal(int[] match, boolean[] rowsCovered, boolean[] colsCovered) Assures given column-n-rows-coverage/zero-matching to be minimal/maximal- Parameters:
match
- zero-matching to checkrowsCovered
- rows coverage to checkcolsCovered
- columns coverage to check- Returns:
- true if given matching and coverage are maximal and minimal respectively
-
uncovered
private static int uncovered(double[][] excessMatrix, boolean[] rowsCovered, boolean[] colsCovered) Accounts for zeroes being uncovered- Parameters:
excessMatrix
- target excess-matrixrowsCovered
- rows coverage to checkcolsCovered
- columns coverage to check
-