Package org.apache.hadoop.hbase.util

Class MunkresAssignment

java.lang.Object
org.apache.hadoop.hbase.util.MunkresAssignment
@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 Details

  • Constructor Details

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

  • Method Details

    • 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