Will a source-removal sort always return a maximal cycle?
- by Jason Baker
I wrote a source-removal algorithm to sort some dependencies between tables in our database, and it turns out we have a cycle. For simplicity, let's say we have tables A, B, C, and D. The edges are like this:
(A, B)
(B, A)
(B, C)
(C, D)
(D, A)
As you can see, there are two cycles here. One is between A and B and another is between all four of them. Will this type of sort always choke on the largest cycle? Or is that not necessarily the case?
