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
Addison-Wesley, 1990
Knuth D. E. Fundamental Algorithms, vol. 1 of The Art of Computer Programming, second edition
Addison-Wesley, 1973
