MunkresAssignment (Apache HBase 1.2.12 API)

java.lang.Object
- org.apache.hadoop.hbase.util.MunkresAssignment

```
@InterfaceAudience.Private
public class MunkresAssignment
extends Object
```
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

Fields
Modifier and Type	Field and Description
`private int[]`	`assignments`
`private float[]`	`colAdjust`
`private int`	`cols`
`private boolean[]`	`colsCovered`
`private float[][]`	`cost`
`private float[]`	`leastInRow`
`private int[]`	`leastInRowIndex`
`private byte[][]`	`mask`
`private static byte`	`NONE`
`private Deque<Pair<Integer,Integer>>`	`path`
`private static byte`	`PRIME`
`private float[]`	`rowAdjust`
`private int`	`rows`
`private boolean[]`	`rowsCovered`
`private static byte`	`STAR`
`private boolean`	`transposed`

Constructor Summary

Constructors
Constructor and Description

MunkresAssignment(float[][] costMatrix)
Construct a new problem instance with the specified cost matrix.

Constructors
Constructor and Description
`MunkresAssignment(float[][] costMatrix)` Construct a new problem instance with the specified cost matrix.

Method Summary

Methods
Modifier and Type	Method and Description
`private Pair<Integer,Integer>`	`findUncoveredZero()` Find a zero cost assignment which is not covered.
`private void`	`preliminaries()` Corresponds to the "preliminaries" step of the original algorithm.
`private Pair<Integer,Integer>`	`primeInRow(int r)` Find a primed zero in the specified row.
`int[]`	`solve()` Get the optimal assignments.
`private Pair<Integer,Integer>`	`starInCol(int c)` Find a starred zero in the specified column.
`private Pair<Integer,Integer>`	`starInRow(int r)` Find a starred zero in a specified row.
`private boolean`	`stepOne()` Corresponds to step 1 of the original algorithm.
`private void`	`stepThree()` Corresponds to step 3 of the original algorithm.
`private void`	`stepTwo()` Corresponds to step 2 of the original algorithm.
`private boolean`	`testIsDone()` 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.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - NONE
```
private static final byte NONE
```
    See Also:
    Constant Field Values
  - STAR
```
private static final byte STAR
```
    See Also:
    Constant Field Values
  - PRIME
```
private static final byte PRIME
```
    See Also:
    Constant Field Values
  - transposed
```
private final boolean transposed
```
  - rows
```
private final int rows
```
  - cols
```
private final int cols
```
  - cost
```
private float[][] cost
```
  - mask
```
private byte[][] mask
```
  - rowsCovered
```
private boolean[] rowsCovered
```
  - colsCovered
```
private boolean[] colsCovered
```
  - path
```
private Deque<Pair<Integer,Integer>> path
```
  - assignments
```
private int[] assignments
```
  - leastInRow
```
private float[] leastInRow
```
  - leastInRowIndex
```
private int[] leastInRowIndex
```
  - rowAdjust
```
private float[] rowAdjust
```
  - colAdjust
```
private float[] colAdjust
```
- Constructor Detail
  - MunkresAssignment
```
public MunkresAssignment(float[][] costMatrix)
```
    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.
    
    Parameters:
    costMatrix -
- Method Detail
  - solve
```
public int[] 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
```
private void 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
```
private boolean 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
```
private boolean stepOne()
```
    Corresponds to step 1 of the original algorithm.
    
    Returns:
    false if all zeroes are covered
  - stepTwo
```
private void stepTwo()
```
    Corresponds to step 2 of the original algorithm.
  - stepThree
```
private void stepThree()
```
    Corresponds to step 3 of the original algorithm.
  - findUncoveredZero
```
private Pair<Integer,Integer> 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
```
private void updateMin(int row,
             int col)
```
    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 covered
    col - the index of the column which was just uncovered
  - starInRow
```
private Pair<Integer,Integer> starInRow(int r)
```
    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
```
private Pair<Integer,Integer> starInCol(int c)
```
    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
```
private Pair<Integer,Integer> primeInRow(int r)
```
    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

Class MunkresAssignment

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

NONE

STAR

PRIME

transposed

rows

cols

cost

mask

rowsCovered

colsCovered

path

assignments

leastInRow

leastInRowIndex

rowAdjust

colAdjust

Constructor Detail

MunkresAssignment

Method Detail

solve

preliminaries

testIsDone

stepOne

stepTwo

stepThree

findUncoveredZero

updateMin

starInRow

starInCol

primeInRow