Topological sorting

PROBLEM
We will assume that the objects to be sorted are numbered from 1 to N in any order. The input to a topological sorting algorithm is a directed graph with no cycles - i.e. the sequence of pairs numbers, where the pair J K means object J precedes object K. Then J is K's predecessor and K is J's successor. As an example of the input, we might have the pairs, for N=9)

 9 2  3 7  7 5  5 8  8 6 4 6  1 3  7 4  9 5  2 8

The algorithm must order the nodes such that all predecessors appear before their successors. For example

1 9 3 2 7 5 4 8 6

ALGORITHM
We start by taking an object which is not preceded by any other object in the ordering. This object may be placed first in the output. Now we remove this object from the input set of objects, the resulting array is again partially ordered, and the process can be repeated until the whole set has been sorted. For each node the algorithm stores the number of predecessors the node has and the set of its successors. For instance our nine-node graph is represented as a following table

Representation of the graph
Object Predecessor Count Successors
1 0 3
2 1 8
3 1 7
4 1 6
5 2 8
6 2
7 1 5    4
8 2 6
9 0 2    5

The algorithm chooses a node whose predecessor count is zero, writes on the output, and decrements the predecessor count of all its successors. To remember the order in which the counts went to zero it uses a queue of nodes for that task.

IMPLEMENTATION
Unit: program

Input: the number N and the sequence of pairs: predecessor successor

Result: Program writes on the screen a linear sequence of the objects such that all predecessors appear before their successors.

 /* 9 2 3 7 7 5 5 8 8 6 4 6 1 3 7 4 9 5 2 8 */ Count. = 0; N = 9; S. = "" do I = 2 while SOURCELINE(I) <> "*/"   Record = SOURCELINE(I)   do while Record <> ""     parse var Record J K Record     Count.K = Count.K + 1; S.J = S.J K   end end do I = 1 to N; if Count.I = 0 then queue I; end do while QUEUED() <> 0   pull K; say K; N = N - 1   Successors = S.K   do while Successors <> ""     parse var Successors X Successors     Count.X = Count.X - 1     if Count.X = 0 then queue X   end end if N <> 0 then   say "TOPOLOGICAL_SORT: Error",     "- a cycle in the input graph"

Literature
Bentley J. More Programming Pearls - Confession of a Coder