Linked Allocation:
Topological Sort

This assignment will implement the topological sort, Algorithm 2.2.3T of TAoCP. The discussion on pp. 261-266 of TAoCP explains what is meant by a "partial ordering" - one which satisfies the three requirements listed there - but it might be easier to think of a PERT chart application. PERT charts (Project Evaluation Review Technique) are diagrams which show the order in which tasks must be completed, and their relationship to other tasks in a project.

Fig. 6 on p. 262 could then be interpreted as requiring that tasks 1 and 9 be completed prior to any others; or stated differently, that tasks 2 and 5 require that 9 be completed first (9<2 and 9<5), task 3 requires that 1 be completed first (1<3), and so on.

We could write the entire set of relationships as: 9<2, 3<7, 7<5, 5<8, 8<6, 4<6, 1<3, 7<4, 9<5, and 2<8. Other relationships, such as 7<8 are implicit and need not be stated. In fact, if no relationships are provided, the standard linear order is used: 1, 2, 3, ..., 9 in this case.

The problem is to arrange the numbers sequentially as in Fig. 7 on p. 263 so that the stated relationships are satisfied; that is, to embed the partial order in a linear order. The topological sort is the process which does that arranging, by implementing Algorithm T.

1. Your program will consist of one CSect (called TopSort) which implements Algorithm T and performs a topological sort on the numbers 1 through n (where n is determined at execution by the first input record).

2. The input file is a sequence of records, each of which contains a pair of numbers (without parentheses). The first pair is (0,n); the zero can be ignored, and n is the largest number to be included. Every other pair (j,k) describes the order relationship between two numbers: j precedes k. The input file does not end with a (0,0) pair as described in TAoCP, but rather with the usual end-of-file condition.

3. Your program should pre-allocate a table with room for a maximum n=25, plus one more entry (see below). Each table entry will consist of two words, Count and Top. Count will be reused as QLink once Count reaches zero (as described in TAoCP). The following DSect should be used to describe a table entry:

   CntNode  DSect ,             Table entry
   Count    DS    F             Count of predecessors
            Org   Count         Redefine for use when Count is zero
   QLink    DS    F             Link to next element in output queue
   Top      DS    A             Top of successor stack
   

4. The successors to any number will be saved in a linked stack whose Top pointer is in CntNode above. The successor node contains the index of the sucessor value and a link field (called Next) to the next successor. Each successor node should be acquired from a linked Avail stack as needed. (The Avail stack should be pre-allocated as twenty-five 8-byte entries using the first word as the link field. This can be accomplished by using the following code:

   Avail    DC    A(*+4)        Avail pointer (top of avail stack)
            DC    24A(*+8,0)    Two words each, link in first
            DC    A(0,0)        Last node, with null link
   

   The following DSect should be used to describe a sucessor node:

   SucNode  DSect ,             Successor in a relationship
   Suc      DS    F             Index of this successor
   Next     DS    A             Link to next successor in stack
   

5. QLink and Suc will contain the index of a table entry rather than its address, as will the queue front and rear pointers, F and R. (For example, the number 1 will have index 1.) In order to access a table entry, its address must be used. Write macro instruction(s) to do any conversions, BASE to convert an index to an address, and INDEX to convert an address to an index. Each macro would have only one operand, a register. BASE converts the index in the register to an address, and INDEX converts the address in the register to an index. The computation will depend on the address of the table, which should be assumed by the macro (rather than passed as an operand).

6. The "extra" table entry will be the first one, to be used for QLink(0) only. This will also facilitate the writing of BASE and INDEX macros. For example, to convert an index to an address, simply multiply the index by the size of an entry, then add the address of the table. So the table entry for the number 1 can be found at table+8.

7. The output from your sort will occur in step T5 and should appear as one number on each line, double-spaced. Write an appropriate header at the top of the page.

8. There are no "closed loops" in the input file, but step T8 should still check N and write an error message if it is not zero.

1. Use the IBM structured macros for this assignment. Although Algorithm T is not written in a particularly structured way, certain parts of the program, such as steps T2 and T3 combined, are more easily written using the structured macros.

2. Use the PGMDUMP macro at the beginning of execution to limit the size of dumps. (See QDriver from the previous assignment.) Without it, your job may generate up to 60,000 lines if it terminates abnormally. This is unwieldy to read at your computer, and the labs won't print it.

3. This is the first assignment in which Labeled Usings will be necessary to keep the various copies of each data structure organized. Plan to have many labeled Using and Drop statements throughout your program.

4. The logic of Algorithm T has been rewritten for easier implementation, with each step having its own doc box. You may wish to rewrite this for your own preferences, but whatever you use, it will be the design your program should follow. For readability, you might also want to start each step at the top of a new page in your listing.

5. There are no special JCL requirements for this assignment. The data file containing the relationships is

   //GO.XREAD DD DSN=T90MES1.C464.DATA(ASN4DATA),DISP=SHR
   

6. During the testing and debugging of your program, you may want to provide your own set of test data records for transactions. If you want to do this, substitute the following lines in place of the GO.XREAD statement above.

   //GO.XREAD DD *
   .
   .
   . your test set of input records
   .
   .
   /*
   //
   

   In particular, you may wish to test your program using the relationships provided as the example in TAoCP. The output from this test data should be 1 9 3 2 7 4 5 8 6 0 (one number on each double-spaced line).