Class KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation.MatchExtender

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private boolean[] colsVisited  
      private boolean[] rowsVisited  
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private MatchExtender​(boolean[] rowsVisited, boolean[] colsVisited)  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean extend​(int initialCol)
      Performs DFS to seek after matching-augmenting path starting at the initial-vertex
      private boolean extendMatchingEL​(int pathTailCol)
      DFS helper #1 (applicable for ODD-LENGTH paths ONLY)
      private boolean extendMatchingOL​(int pathTailRow, int pathTailCol)
      DFS helper #1 (applicable for ODD-LENGTH paths ONLY)
      • Methods inherited from class java.lang.Object

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

      • rowsVisited

        private final boolean[] rowsVisited
      • colsVisited

        private final boolean[] colsVisited
    • Constructor Detail

      • MatchExtender

        private MatchExtender​(boolean[] rowsVisited,
                              boolean[] colsVisited)
    • Method Detail

      • extend

        public boolean extend​(int initialCol)
        Performs DFS to seek after matching-augmenting path starting at the initial-vertex
        Parameters:
        initialCol - column # of initial-vertex
        Returns:
        true when some augmenting-path found, false otherwise
      • extendMatchingOL

        private boolean extendMatchingOL​(int pathTailRow,
                                         int pathTailCol)
        DFS helper #1 (applicable for ODD-LENGTH paths ONLY)
        Parameters:
        pathTailRow - row # of tail of the matching-augmenting path
        pathTailCol - column # of tail of the matching-augmenting path
        Returns:
        true if matching-augmenting path found, false otherwise
      • extendMatchingEL

        private boolean extendMatchingEL​(int pathTailCol)
        DFS helper #1 (applicable for ODD-LENGTH paths ONLY)
        Parameters:
        pathTailCol - column # of tail of the matching-augmenting path
        Returns:
        true if matching-augmenting path found, false otherwise