11.5: Behavior for Replicated Pairs or Loops

In the solution to the topological sorting problem, it is assumed that each distinct input pair appears only once and also that the input contains no loops. Either assumption might be violated. Of course, more obvious errors could occur. For example, n or one of the input pair members could be negative or out of range. It is not difficult to add a validation routine to check for these kinds of input errors. Subtler errors, such as replication of pairs or the occurrence of loops, are not as obviously remedied.

What does happen if pairs are replicated or loops occur in the input ? How would you recognize loops? Replication of an input pair i, j causes the count of j to be 1 larger than it should be. It also causes the successor j to appear on the list of successors of i one more time. When object i is eventually removed, its list of successors is traversed. This results in the count of j being reduced one additional time, so that the extra increase due to the i, j replication is cancelled. The implementation will thus work correctly as long as there is room for the extra successor records to appear in lists. If there is no room to accommodate these extra records, it is not possible to predict what will occur when the implementation is executed.

Loops, on the other hand, result in some objects never being output. Objects that are involved in a loop, or that are the successors of an object in a loop, will never have their counts go to zero, and will never appear in the bag of objects. In fact, had the test for completion been "S not empty" or "n objects output," loops in the input would cause an infinite loop in the program. It should now be clear that next-1, when the loop in phase II is exited, will be the actual number of objects that were output by the loop. If this is less than n, then loops occurred in the input. This can provide a simple test for loops.