IndexHelp
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 (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)