As already noted, the implementation of the output ranking and the bag are coupled because they share storage. As a result they are not independent. This means that a change in the choice of implementation for one will affect the other. In general, such a situation is to be avoided?/FONT>and, as pointed out earlier, could have been avoided. Certainly the small saving in time and storage did not warrant the added complexity.
There are, however, some important storage considerations that were alluded to earlier. Topsort will run out of storage before it runs out of time, since storage requirements grow as n2. The bulk of the storage needed is taken by the lists array. Suppose a maximum size, based on the available storage of the computer system, is declared for the lists array. Say its length is 50,000. Assuming each of its records takes two entries, this provides enough storage to guarantee the solution of any problem with no more than 25,000 successors (m ?/FONT> 25,000). It makes no difference how the successors are distributed among the objects; only the total number is relevant.
Suppose, instead, that the decision had been to represent each collection of successors by dedicating an array to the collection. Since the programmer does not know in advance how the successors will be distributed, each of the required n arrays should have the same length. Lists are no longer necessary, since the successors can be placed sequentially in the proper array. Of course, a variable will be needed to keep track of the last successor in each array. An additional array may be used for these pointers. If n is to be no greater than (say) 500, then each of the arrays containing the successors can be declared of length 50,000/500, or 100. The upshot is that the solution may now be guaranteed for a different class of problems. These problems must have n ?/FONT> 500, and each object may have no more than 100 successors. Even though the total number of successors may now be 50,000 (twice as many as before), their distribution is critical. When storage is at a premium, such considerations are important.
Had dynamic memory been used instead of the lists array for storage of the successor records, the program would contain no explicit storage limitation (other than the declarations for the length of count, succ, and rank). Still, the maximum dynamic memory size would have imposed a limit on the value of m for which the program would execute.