Package org.apache.hadoop.hbase.util
Class MunkresAssignment
java.lang.Object
org.apache.hadoop.hbase.util.MunkresAssignment
Computes the optimal (minimal cost) assignment of jobs to workers (or other analogous) concepts
given a cost matrix of each pair of job and worker, using the algorithm by James Munkres in
"Algorithms for the Assignment and Transportation Problems", with additional optimizations as
described by Jin Kue Wong in "A New Implementation of an Algorithm for the Optimal Assignment
Problem: An Improved Version of Munkres' Algorithm". The algorithm runs in O(n^3) time and need
O(n^2) auxiliary space where n is the number of jobs or workers, whichever is greater.
-
Field Summary
Modifier and TypeFieldDescriptionprivate int[]
private float[]
private final int
private boolean[]
private float[][]
private float[]
private int[]
private byte[][]
private static final byte
private static final byte
private float[]
private final int
private boolean[]
private static final byte
private final boolean
-
Constructor Summary
ConstructorDescriptionMunkresAssignment
(float[][] costMatrix) Construct a new problem instance with the specified cost matrix. -
Method Summary
Modifier and TypeMethodDescriptionFind a zero cost assignment which is not covered.private void
Corresponds to the "preliminaries" step of the original algorithm.primeInRow
(int r) Find a primed zero in the specified row.int[]
solve()
Get the optimal assignments.starInCol
(int c) Find a starred zero in the specified column.starInRow
(int r) Find a starred zero in a specified row.private boolean
stepOne()
Corresponds to step 1 of the original algorithm.private void
Corresponds to step 3 of the original algorithm.private void
stepTwo()
Corresponds to step 2 of the original algorithm.private boolean
Test whether the algorithm is done, i.e.private void
updateMin
(int row, int col) A specified row has become covered, and a specified column has become uncovered.
-
Field Details
-
NONE
- See Also:
-
STAR
- See Also:
-
PRIME
- See Also:
-
transposed
-
rows
-
cols
-
cost
-
mask
-
rowsCovered
-
colsCovered
-
path
-
assignments
-
leastInRow
-
leastInRowIndex
-
rowAdjust
-
colAdjust
-
-
Constructor Details
-
MunkresAssignment
Construct a new problem instance with the specified cost matrix. The cost matrix must be rectangular, though not necessarily square. If one dimension is greater than the other, some elements in the greater dimension will not be assigned. The input cost matrix will not be modified.
-
-
Method Details
-
solve
Get the optimal assignments. The returned array will have the same number of elements as the number of elements as the number of rows in the input cost matrix. Each element will indicate which column should be assigned to that row or -1 if no column should be assigned, i.e. if result[i] = j then row i should be assigned to column j. Subsequent invocations of this method will simply return the same object without additional computation.- Returns:
- an array with the optimal assignments
-
preliminaries
Corresponds to the "preliminaries" step of the original algorithm. Guarantees that the matrix is an equivalent non-negative matrix with at least one zero in each row. -
testIsDone
Test whether the algorithm is done, i.e. we have the optimal assignment. This occurs when there is exactly one starred zero in each row.- Returns:
- true if the algorithm is done
-
stepOne
Corresponds to step 1 of the original algorithm.- Returns:
- false if all zeroes are covered
-
stepTwo
Corresponds to step 2 of the original algorithm. -
stepThree
Corresponds to step 3 of the original algorithm. -
findUncoveredZero
Find a zero cost assignment which is not covered. If there are no zero cost assignments which are uncovered, then null will be returned.- Returns:
- pair of row and column indices of an uncovered zero or null
-
updateMin
A specified row has become covered, and a specified column has become uncovered. The least value per row may need to be updated.- Parameters:
row
- the index of the row which was just coveredcol
- the index of the column which was just uncovered
-
starInRow
Find a starred zero in a specified row. If there are no starred zeroes in the specified row, then null will be returned.- Parameters:
r
- the index of the row to be searched- Returns:
- pair of row and column indices of starred zero or null
-
starInCol
Find a starred zero in the specified column. If there are no starred zeroes in the specified row, then null will be returned.- Parameters:
c
- the index of the column to be searched- Returns:
- pair of row and column indices of starred zero or null
-
primeInRow
Find a primed zero in the specified row. If there are no primed zeroes in the specified row, then null will be returned.- Parameters:
r
- the index of the row to be searched- Returns:
- pair of row and column indices of primed zero or null
-