Topological sorting requires ranking a set of objects subject to constraints on the resultant topology?/FONT>that is, on the placement of the objects. It occurs in many practical situations. For example, textbooks are often written so that each chapter builds on material covered earlier and cannot be understood without this base of information. Determining the order in which to present topics to ensure that all prerequisite material has been covered reduces to finding a topological sort of the topics. Other examples involving topological sorting are presented later.
The approach to the topological sorting problem presented in this chapter and the characteristics of the final program are intended to serve as prototypes. The problem is substantial and the algorithm developed important, but it is the process by which it is achieved that is most important. Developing an efficient topological sorting program is a complex process and demonstrates the general problem solving methodology used in this text. It requires the application of structured programming concepts, during which the selection of data structures plays a significant role.
The resultant topological sorting program is a model solution, representing nearly the best programmers can hope to achieve. Few solutions to problems have all its characteristics. It is concise and clear; correctness is easy to determine; and the storage and execution time requirements can be analyzed. Invalid input data are not difficult to deal with. What more can we ask?
The following are some examples of problems whose solutions require topological sorting.
Example 11.1
A large skyscraper is to be constructed. Imagine that you must write a program to prescribe the order in which all the tasks are to be performed. The tasks include T3?/FONT>install windows; T50?/FONT>install floors; T8?/FONT>install window sashes; T1000?/FONT>clear the ground; T7?/FONT>build the foundation; T9?/FONT>install doors. For any two tasks, it is possible to specify whether one should be done before the other. Clearly, T8 must be done before T3, and T1000 must be done before T7, while it makes no difference whether or not T3 is done before T9. The constraint that Ti be done before Tj is represented as the pair (i, j). n
Example 11.2
Imagine that you want to write a book on data structures. All technical words used must be defined. First write down all the relevant words. If word wj uses wi in its definition, represent this constraint by the pair (i, j). n
Example 11.3
As a student you must take a number of courses to graduate. Represent the fact that course cj has course ci as a prerequisite by the pair (i, j). n
Example 11.4
A number of books must be read for a course you are taking. Represent the fact that you prefer to read book i before book j by the pair (i, j). n
Suppose that an order is given in which the construction tasks of Example 11.1 are to be carried out. If you proceed to carry out the tasks, you may not be able to do the next task, since tasks that must precede it have not yet been finished. The same situation can arise in Examples 11.2, 11.3, and 11.4, when an order is specified in which words are to be defined, courses to be taken, and books to be read, respectively. This is because words used in the next word's definition have not yet been defined, all prerequisites for the next course may not have been taken, or you will not read the next available book because you want to honor your preferences. A topological sort gives an order in which to proceed so that such difficulties will never be encountered.
11.1.1 Binary Relations and Partial Orders
11.1.2 Graphic Representation of Partial Orders
11.1.3 Topological Sorts: Consistent Rankings