A topological sort produces a ranking of objects that satisfies constraints on their allowable positions within the ranking. The obvious algorithm for finding a topological sort, searching through all rankings until one satisfying the constraints is found, is not feasible. A feasible algorithm was developed by constructing a ranking that satisfied the constraints. The initial implementation merely produced an image of the input data in memory. It was improved significantly by using an array to contain predecessor counts, creating lists of successors, and introducing a bag to hold objects whose predecessor counts became zero. This solution was achieved by a process of stepwise refinement, stressing data abstraction, encapsulation, modularity, and the proper choice of data structures. The functional modularity of the final solution allowed immediate application of a routine developed earlier?/FONT>the list traversal routine. Again, because of functional modularity, it was not difficult to determine where and how to build in appropriate checks of the input data.
More generally, the analysis of the storage and time requirements of a fairly complex program was demonstrated. Even though this cannot always be accomplished, or may be difficult for complex programs, it serves as an example of what we hope to be able to do.