Name given to an

algorithm for

extending a

partial order relation to a

total order.

The input is a set of ordered pairs `i -> j`, meaning "*i* must come before *j*". The output is a permutation of 1, ..., *n* such that *i* is located before *j* whenever `i -> j`. Of course, for some inputs (those that specify a loop) this is not possible; the algorithm reports this error condition.

Here's the algorithm:

- Compute and store the
*in degree* `d[j]` for each *j* (this is the number of *i*'s for which `i -> j`).
- Initialise a collection (typically a queue or a stack, doesn't matter which)
*C* to {*j* : `d[j] == 0`}.
- While
*C* is not empty:
- Remove some element
*i* from *C*.
- Output
*i*.
- For each
*j* such that `i -> j`, decrement `d[d]`; if this zeros it, add *j* to *C*.

- If we output
*n* values in the previous step, the sort succeeded; otherwise it failed, and a loop exists in the input.

Properly implemented, the algorithm runs in

time complexity O(

*n*^{2}) on a

RAM machine. This is quite easy in practice! Just store a linked list of

*j*'s for which

`i -> j` for each

*i*; use this step to calculate

`d[]`, too. The rest is

an easy exercise for the reader...