Module org.jgrapht.core
Package org.jgrapht.alg.matching
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 java.lang.Object
Aggregates utilities to extend matching
-
-
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-vertexprivate 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)
-
-
-
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 pathpathTailCol
- 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
-
-