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 Object
Aggregates utilities to extend matching
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final boolean[]
private final boolean[]
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
MatchExtender
(boolean[] rowsVisited, boolean[] colsVisited) -
Method Summary
Modifier and TypeMethodDescriptionboolean
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)
-
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 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
-