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 
    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-mask
    private double[][]
    costMatrix
    Cost matrix
    private double[][]
    excessMatrix
    Excess matrix
    private 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(Graph<V,E> g, List<? extends V> s, List<? extends V> t)
    Construct new instance

  • Method Summary

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