|
|
Our input file consists of words separated by white space (spaces, tabs, newlines). Each word is considered to represent some abstract object; the words are taken in pairs to assert that the first object of each pair is ``less than'' the second. If both words in the pair are the same, that pair just says that the particular word exists without saying anything about its ordering. The problem is to find a single linear ordering that satisfies all the given constraints. This may be impossible because of a loop in the ordering. In that case, the program should say so.
For example, the following input represents some constraints on clothing:
pants belt left_sock left_shoe right_sock right_shoe shirt shirt pants left_shoe pants right_shoe
Here, we say that one article of clothing is ``less than'' another if it must be put on before the other. Thus each sock must be put on before the corresponding shoe, it is difficult to put on pants over shoes, one must put one's pants on before one's belt, and there is a shirt in there somewhere.
One ordering that satisfies all these constraints is:
left_sock pants right_sock shirt belt left_shoe right_shoe
There are others, of course.
Topological sorting is often used to put modules into an appropriate order for load module archives in the UNIX® system; there is therefore a topological sort utility program called tsort available as a standard for comparison.