1 PROCEDURE (G: reduced graph, W:positive integer)
2 Let R(v) be a set of v
3 Let i be integer
4 Let U be an empty set
5 Let i be integer and set i = 0
6 Let Li be layer i
7
8 //Step 1: assign integer labels to vertices.
9 CALL LabelVertices with G RETURN a set of labelled vertices U
10
11 //Step 2: Assign labelled vertices into layers.
12 //starts from bottom and head to the top
13 //assign all sinks to layer(s)
14 FOR each u in U
15 IF u is a sink
16 Add u to set Li
17 Remove u from U
18 //if the layer i is full
19 //assign vertices to the next layer
20 IF Size(Li) >= W
21 Increment i by 1
22 ENDIF
23 ENDIF
24 END LOOP
25
26 WHILE U not empty
27 //Find a set R of vertices that are not assigned
28 //to a layer yet
29 Call findUnassignedLayeredVertices with G, U return R
30 Sort set R based on the vertex labels
31 IF R is empty THEN
32 Increment i by 1 // next layer
33 ELSE
34 FOR each v in R
35 Add v to Li
36 IF Size(Li) THEN
37 Increment i by 1
38 ENDIF
39 END LOOP
40 ENDIF
41 ENDWHILE
42 END PROCEDURE