Package org.jgrapht.alg
Class KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E>
- java.lang.Object
-
- org.jgrapht.alg.KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E>
-
- Enclosing class:
- KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>
protected static class KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E> extends java.lang.Object
The actual implementation.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation.MatchExtender
Aggregates utilities to extend matching
-
Field Summary
Fields Modifier and Type Field Description private int[]
columnMatched
``columnMatched[i]'' is the column # of the ZERO matched at the i-th row(package private) boolean[]
columnsCovered
Columns coverage bit-maskprivate double[][]
costMatrix
Cost matrixprivate double[][]
excessMatrix
Excess matrixprivate int[]
rowMatched
``rowMatched[j]'' is the row # of the ZERO matched at the j-th column(package private) boolean[]
rowsCovered
Rows coverage bit-mask
-
Constructor Summary
Constructors Constructor Description KuhnMunkresMatrixImplementation(WeightedGraph<V,E> G, java.util.List<? extends V> S, java.util.List<? extends V> T)
Construct new instance
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description 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(package private) int
buildMaximalMatching()
Builds maximal matching corresponding to the given excess-matrix(package private) void
buildVertexCoverage()
Builds vertex-cover given built up matching(package private) void
extendEqualityGraph()
Extends equality-graph subtracting minimal excess from all the COLUMNS UNCOVERED and adding it to the all ROWS COVERED(package private) double[][]
makeExcessMatrix()
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 Detail
-
costMatrix
private double[][] costMatrix
Cost matrix
-
excessMatrix
private double[][] excessMatrix
Excess matrix
-
rowsCovered
boolean[] rowsCovered
Rows coverage bit-mask
-
columnsCovered
boolean[] columnsCovered
Columns 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 Detail
-
KuhnMunkresMatrixImplementation
public KuhnMunkresMatrixImplementation(WeightedGraph<V,E> G, java.util.List<? extends V> S, java.util.List<? extends V> T)
Construct new instance- Parameters:
G
- the input graphS
- first partition of the vertex setT
- second partition of the vertex set
-
-
Method Detail
-
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
-
-