1 PROCEDURE (G=(L1, L2, E): two-layered graph, C=( L2xL2: acyclic constraints)
2 Let V be a set of vertices that have constraints;
3 Let V’ be a set of vertices that do not have constraints
4 L(u) <- {}; //Empty list
5 CALL computeBaryCenter with G Return L(u)
6 Add all pair constrained (u, v) to V
7 Add vertices that do not have constraints to V'
9 WHILE (u,v) = find_violate_constraint(V,C) is not empty
10 create new dummy vertex vc
11 deg(vc) = deg(u) + deg(v)
12 b(vc) = (b(u ) * deg(u ) + b(v) * deg(v)) / deg(vc)
13 L(vc) = L(u) × L(v)
14 //Add incident edges of u or v to vc
15 FOR each c in C
16 IF c is incident to u or v
17 make c incident to vc
18 ENDIF
19 END LOOP
20 Remove any self loop from C
21 Remove (u,v) from V.
22 IF vc has incident constraint THEN
23 Add vc into V
24 ELSE
25 Add vc into V’
26 ENDIF
27 Add both set V and V' to V''
28 Sort V’’ by barycentric values
29 Empty the temporary list L
30 //Concatenate and replace dummy vertices by the
31 //original vertices
32 FOR each v in V’’
33 Concatenate vertices into a list L
34 END LOOP
35 ENDWHILE
37 END PROCEDURE