TAOCP 2.2.3 Exercise 21

Algorithm `T` in Section 2.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.3: Linked Allocation

Exercise 21. [21] Would Algorithm T still perform a valid topological sort if one of the relations "$j \prec k$" were repeated several times in the input? What if the input contained a relation of the form "$j \prec j$"?

Verified: yes
Solve time: 45s

Solution

Algorithm T in Section 2.2.3 performs a topological sort by maintaining a queue of nodes whose COUNT field is zero and then repeatedly removing a node from the front of the queue, outputting it, and decrementing the COUNT of its successors. The correctness of Algorithm T relies on two invariants: each node is output exactly once, and a node is output only after all its predecessors have been output.

Suppose that the input contains a repeated relation $j \prec k$. Each time the algorithm encounters a relation, it decrements COUNT(k) by one in step T6. If $j \prec k$ appears $m$ times, then COUNT(k) is incremented initially by $m$ (from step T1 or T2) and then decremented $m$ times as $j$ is output. The net effect is identical to the case in which $j \prec k$ occurs only once. Therefore, repeated relations do not change the final values of COUNT nor the order in which nodes become eligible for output. Consequently, Algorithm T still produces a valid topological sort when relations are repeated.

Next, suppose that the input contains a relation of the form $j \prec j$. In step T6, the algorithm would decrement COUNT(j) when node $j$ is output. Initially, COUNT(j) counts the number of distinct predecessors of $j$; a self-relation would increment COUNT(j) by one. When node $j$ is eventually output, step T6 decrements COUNT(j) from $1$ to $0$, but the algorithm does not explicitly prevent a node from appearing in the queue while it is still being processed. However, the self-loop creates a dependency cycle: $j$ must appear after itself. Topological sorting is only defined for acyclic relations; a cycle prevents any valid topological order. Therefore, if a self-relation exists, Algorithm T cannot produce a valid topological sort because the input violates the acyclicity requirement.

In summary, repeated relations $j \prec k$ do not affect the correctness of Algorithm T, since each decrement in COUNT(k) corresponds exactly to the number of incoming arcs. Relations of the form $j \prec j$ introduce a cycle, which violates the fundamental assumption of topological sorting, and Algorithm T will fail to produce a valid sort in this case.

This completes the proof.

∎