[ACCEPTED]-How do I detect circular logic or recursion in a multi-levels references and dependencies-circular-reference

Accepted answer
Score: 16

Topological sorting. The description on Wikipedia is clear 11 and works for all your examples.

Basically 10 you start with a node that has no dependencies, put 9 it in a list of sorted nodes, and then remove 8 that dependency from every node. For you 7 second example that means you start with 6 1. Once you remove all dependencies on 1 5 you're left with 2. You end up sorting them 4 1,2,3,4,5 and seeing that there's no cycle.

For 3 your third example, every node has a dependency, so 2 there's nowhere to start. Such a graph must 1 contain at least one cycle.

Score: 5

Keep a list of uniquely identified nodes. Try to loop 6 through the entire tree but keep checking 5 nodes in the list till you get a node being 4 referred as a child which is already there 3 in the unique list - take it from there 2 (handle the loop or simply ignore it depending 1 on your requirement)

Score: 2

One way to detect circular dependency is 7 to keep a record of the length of the dependency 6 chains that your ordering algorithm detects. If 5 a chain becomes longer than the total number 4 of nodes (due to repetition over a loop) then 3 there is a circular dependency. This should 2 work both for an iterative and for a recursive 1 algorithm.

More Related questions