Index
Help
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(M,A,B,C) = GallaiEdmondsDecomposition(G)
while
not
(A ==[]
and
B ==[]
and
C ==[]):
for
v
in
A + B:
if
is_supervertex(v)
and
not
is_dualvar(v):
u[v] = 0.0# adds new dual var
eps1,tight_edges1 = mindist(B,B)
eps1 *= 0.5
eps2,tight_edges2 = mindist(B,C)
eps3 = min([u[v]
for
v
in
A
if
is_supervertex(v)] +[Infinity])
i,eps = argmin_min([eps1,eps2,eps3])
for
v
in
A:# ----- deflate A
u[v] -= eps
for
v
in
B:# ----- inflate B
u[v] += eps
for
v
in
A:
if
not
is_supervertex(v):
RemoveIncidentUntightEdges(v,A,B,C)
else
:
RemoveIncidentUntightEdgesFromSupervertex(v,A,B,C)
if
i == 2:# eps == eps3
for
v
in
A:
if
is_supervertex(v)
and
u[v] == 0.0:
Unshrink(v)
tight_edges =[]
if
eps == eps1:
tight_edges += tight_edges1
if
eps == eps2:
tight_edges += tight_edges2
for
v,w
in
tight_edges:
AddTightEdge(v,w)
(M,A,B,C) = GallaiEdmondsDecomposition(G)
CheckSolution(M,u)