tsort: incorrect loop detection

[Nekrolm]

Graph

  A B
  B C
  C B
  C D
  D A

So there are two loops:

A -> B -> C -> D -> A

B -> C -> B

dmis@dmis-asus-N7600PC:~/WORKSPACE/coreutils$ tsort loop.txt 
tsort: loop.txt: input contains a loop:
tsort: B
tsort: C
tsort: loop.txt: input contains a loop:
tsort: A
tsort: B
tsort: C
tsort: D
A
B
C
D
dmis@dmis-asus-N7600PC:~/WORKSPACE/coreutils$ target/debug/coreutils tsort loop.txt 
tsort: loop.txt: input contains a loop:
tsort: A
tsort: B
tsort: C
tsort: loop.txt: input contains a loop:
tsort: B
tsort: C
C
B
D
A

[Nekrolm]

Found and fixed this during testing for #8737

tsort: loop.txt: input contains a loop:
tsort: B
tsort: C
C
D
A
B

Breaking edge B - C breaks both loops that's why a bigger one is not printed.

But GNU tsort prints both. Interesting -- how?

[Nekrolm]

I honestly don't think that for unsortable graphs there should be any meaningful final result. And which edge is broken. But any reported loop must be valid

[romanstingler]

Found and fixed this during testing for #8737

tsort: loop.txt: input contains a loop:
tsort: B
tsort: C
C
D
A
B

Breaking edge B - C breaks both loops that's why a bigger one is not printed.

But GNU tsort prints both. Interesting -- how?

I have not looked into the uutils code or your code yet but

Your input has 2 cycles
A -> B, B -> C, C -> B, C -> D, D -> A
Smaller cycle: B -> C -> B
Larger cycle: A -> B -> C -> D -> A

you would have something
Read token pairs and builds a graph using a binary tree for nodes, with predecessor counts (count) and successor lists (top).

After reading: A: count=1, top={B}, B: count=2, top={C}, C: count=1, top={B,D}, D: count=1, top={A}.
Total nodes: 4.

The detect_loop function uses DFS to find a cycle (e.g., B -> C -> B):

Prints the cycle (B, C) to stderr.
Breaks the cycle by removing an edge (e.g., C -> B), updating counts (B->count from 2 to 1).

you would run the detect_loop again because you have no zero yet.
detect_loop finds the second cycle (A -> B -> C -> D -> A), prints it (A, B, C, D), and breaks it (e.g., removes D -> A, setting A->count = 0).

After breaking the second cycle, A has count = 0, so scan_zeros adds A to the head queue.
The main loop outputs A, processes its successors (B->count becomes 0), outputs B, and so on, producing A, B, C, D.

in my opinion your test test_loop_for_iterative_dfs_correctness() https://github.com/uutils/coreutils/pull/8737/files#diff-4edbd35c077fe5f4781a814a077d171592bf2a18562e68bfd1c673d0a0e49a0c should exactly represent the GNU tsort output

tsort: /tmp/loop.txt: input contains a loop:
tsort: B
tsort: C
tsort: /tmp/loop.txt: input contains a loop:
tsort: A
tsort: B
tsort: C
tsort: D
A
B
C
D

[Nekrolm]

Output depends on the choosen edge to break (BC or CB)

I can update the logic to choose the last edge in cycle instead of the first edge. Then output will match

[romanstingler]

yes, the projects goal is to match the GNU coreutils exactly, so that people can expect the same output so that their scripts, tools.. doesn't break.

I would prefer having it the same, even if I can understand your point

[Nekrolm]

Well, it's not possible without checking exact code of GNU coreutils (which is not allowed due to licensing). Sorting unsortable graphs -- 100% implementation defined.

E.g. if I just change the code to take last edge in the loop, output for this test will change and won't match gnu tsort:

// fn test_cycle()
// The graph looks like:  a --> b <==> c --> d
"a b b c c d c b"

a b c d or a c b d