11.3.2 An Initial Implementation

A straightforward representation of the partial order would be to keep an image in memory of all input arrows. We might use two arrays, first and second, for this purpose. First would contain the first integer, and second would contain the second integer of an input pair. The "record the information" task would then involve putting i and j into the next available locations of first and second, respectively. For Example 11.6, after phase I was executed, the result would be the arrays shown in Figure 11.4.

Suppose the while loop of phase II is being executed, and task 5a is to be carried out. An object with no predecessors must be selected. How is such an object found? Any object that has no predecessors will not appear in the second array. Somehow the second array must be searched to select an object with no predecessors. This can be accomplished by using an array S, traversing second, and marking location i of S when object i appears in second. Any location in S left unmarked corresponds to an object with no predecessors.

Suppose this is done, and object 5 is selected. Object 5 can then be output to the next place in the ranking. To accomplish task 5b, the "updating of the records," then requires that the array first be traversed. As it is traversed, each time a 5 is encountered, the program must mark the location of first in which it appears, and the corresponding location of second. The mark signifies that the corresponding arrow emanating from 5 has been removed from the representation.

Figure 11.4 Result of Phase I of the First Refinement

This completes one execution of the loop. This same processing must be repeated for each repetition of that loop. The loop will be repeated n times, once for each of the n objects. The first and second arrays must be traversed each time. This will take time proportional to their length, which, in general, will be m. Hence this implementation of the algorithm will take time proportional to n ?/FONT> m. The storage required is roughly 2m locations for first and second, and n locations for S.