Class KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation.MatchExtender

java.lang.Object
org.jgrapht.alg.matching.KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation.MatchExtender
Enclosing class:
KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E>
protected class KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation.MatchExtender extends Object
Aggregates utilities to extend matching

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final boolean[]
    colsVisited
     
    private final boolean[]
    rowsVisited
     

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    private
    MatchExtender(boolean[] rowsVisited, boolean[] colsVisited)
     

  • Method Summary

    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 Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • rowsVisited

      private final boolean[] rowsVisited

    • colsVisited

      private final boolean[] colsVisited

  • Constructor Details

    • MatchExtender

      private MatchExtender(boolean[] rowsVisited, boolean[] colsVisited)

  • Method Details

    • 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