Step 3 Define θ$_{2}$ : V ( D$_{3}$ ) → V ( D$_{2}$ ) by θ$_{2}$ ( t$_{2}$ ) = 4 and θ$_{2}$ ( u ) = u for all u ∈ V ( D$_{2}$ ) . 

Step 4 ( X$_{3}$,ρ$_{3}$ ) is preordered so the algorithm stops. The compression map is θ$_{1}$ ◦ θ$_{2}$ . 

## 4 Proof of Theorem 3.2 

If D is the compression of a preordered directed graph then every clasp in D is unlocked by part 3 of Lemma 3.6. We assume D is stable and every clasp in D is unlocked and prove D is the compression of a preorder. We set D$_{1}$ = D , and describe an algorithm to construct stable directed graphs D$_{1}$,...,D$_{m}$ such that D$_{i}$ is a compression of D$_{i}$$_{+1}$ for each i < m . In the last iteration D$_{m}$ is preordered and the desired compression map is obtained by composition. 

Assume D$_{1}$ is not preordered and fix a clasp x$_{1}$ ∈ V ( D$_{1}$ ). In the first iteration of our algorithm we have i = 1. 

## Step 1 

The sets Y$_{i}$ and A$_{i}$ are defined below. 

• Y$_{i}$ = { y ∈ V ( D$_{i}$ ) \ { x$_{i}$ } : wx$_{i}$ , x$_{i}$y ∈ A ( D ) and wy / ∈ A ( D$_{i}$ ) for some w ∈ V ( D$_{i}$ ) } 

• A$_{i}$ = { a ∈ V ( D$_{i}$ ) \ { x$_{i}$ } : ( a,x$_{i}$,y ) ∈ Trans ( D$_{i}$ ) for some y ∈ Y$_{i}$ } . 

Note that Y$_{i}$ is nonempty since x$_{i}$ is a clasp. 

