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 Classes
    Modifier and Type
    Class
    Description
    protected class 
    Aggregates utilities to extend matching
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private int[]
    ``columnMatched[i]'' is the column # of the ZERO matched at the $i$-th row
    (package private) boolean[]
    Columns coverage bit-mask
    private double[][]
    Cost matrix
    private double[][]
    Excess matrix
    private 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
    Constructor
    Description
    KuhnMunkresMatrixImplementation(Graph<V,E> g, List<? extends V> s, List<? extends V> t)
    Construct new instance
  • Method Summary

    Modifier and Type
    Method
    Description
    protected 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-matrix
    private static boolean
    minimal(int[] match, boolean[] rowsCovered, boolean[] colsCovered)
    Assures given column-n-rows-coverage/zero-matching to be minimal/maximal
    private static int
    uncovered(double[][] excessMatrix, boolean[] rowsCovered, boolean[] colsCovered)
    Accounts for zeroes being uncovered

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

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

    • KuhnMunkresMatrixImplementation

      public KuhnMunkresMatrixImplementation(Graph<V,E> g, List<? extends V> s, List<? extends V> t)
      Construct new instance
      Parameters:
      g - the input graph
      s - first partition of the vertex set
      t - 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 check
      rowsCovered - rows coverage to check
      colsCovered - 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-matrix
      rowsCovered - rows coverage to check
      colsCovered - columns coverage to check