Def improveLabels(val)
«»» change the labels, and maintain minSlack
«»
for u in S
lu[u] -= va
for v in V
if v in T
lv[v] += va
else
minSlack[v] [0] -= va
def improveMatching(v)
«»» apply the alternating path from v to the root in the tree
«»
u = T[v
if u in Mu
improveMatching (Mu[u]
Mu[u] =
Mv[v] =
def slack (u, v): return lu[u]+lv[v] - w[u] [v
def augment()
«»» augment the matching, possibly improving the lablels on the way
«»
while True
# select edge (u, v) with u in S, v not in T and min slac
((val, u), v) = min([(minSlack[v], v) for v in V if v not in T]
assert u in
if val>0
improveLabels(val
# now we are sure that (u, v) is saturate
assert slack (u, v)==
T[v] = u # add (u, v) to the tre
if v in Mv
u1 = Mv[v] # matched edge
assert not u1 in
S[u1] = True #… add endpoint to tre
for v in V: # maintain minSlac
if not v in T and minSlack[v] [0] > slack (u1, v)
minSlack[v] = [slack (u1, v), u1
else
improveM