Topological Sort

Fancy name. Makes it sound hard: label nodes with depth and then sort?

• Take a directed acyclic graph (DAG).
• Output a linear order of nodes such that all arrows are pointing to the right.

Essentially a linear schedule so there are no conflicts during dressing. Example.

Claim: A (finite) DAG always has at least one node with no incoming edges and one with no outgoing edges. Proof by contradiction.