Class KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,​E>

    • 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
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      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 java.lang.Object

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

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

      • KuhnMunkresMatrixImplementation

        public KuhnMunkresMatrixImplementation​(Graph<V,​E> g,
                                               java.util.List<? extends V> s,
                                               java.util.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 Detail

      • 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