[Toybox] tsort regrets

[Ray Gardner]

On 11/3/23 12:36:30, Rob Landley wrote:
...
> > One other thing: In an earlier post to the list, I pondered that I'd
> > need to do something about duplicate input pairs to tsort. Knuth's
> > approach doesn't need to be concerned about that, the duplicates sorta
> > come out in the wash.
>
>   // Slight mod: if self-reference relation, do not record it.
>   // (If it's self-reference, the symbol is already in the table now.)
>   // Note that this links the most recent into the head of the successor
>   // list, reversing their order in the input. If the symbols table kept a
>   // tail pointer, they could be kept in the list in original order.
>   if (strcmp(pred, succ)) {
>
> That would be "the wash". :)

Actually that "slight mod" is to deal with where the tsort spec says
"Pairs of identical items indicate presence, but not ordering." So a pair
"foo foo" gets "foo" into the output, in no specific place because (unless
foo is used elsewhere) foo has no predecessors or successors. Knuth's algo
would consider "foo foo" to be a loop.

The "come out in the wash" is because a dup, e.g. "foo bar", "foo bar"
causes bar to be listed twice in the linked list from foo, and this puts
the predecessor count for bar at 2. When foo is written out, the algo
finds both "bar" entries in the linked list and decrements "bar"s
predecessor count twice, so the duplicate is a wash.