Will a source-removal sort always return a maximal cycle?
Posted
by Jason Baker
on Stack Overflow
See other posts from Stack Overflow
or by Jason Baker
Published on 2010-04-02T17:58:05Z
Indexed on
2010/04/02
18:03 UTC
Read the original article
Hit count: 169
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?
© Stack Overflow or respective owner