CODEWITHSUNDEEP
circular-dependencycircular-reference
LuigleDR
LuigleDR

Reputation: 339

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

I have a graph of multi-level dependecies like this, and I need to detect any circular reference in this graph.

A = B

B = C

C = [D, B]

D = [C, A]

Somebody have a problem like this?

Any solution???

Thanks and sorry by english.

========= updated ==========

I had another situation.

1

2 = 1

3 = 2

4 = [2, 3]

5 = 4

In this case, my recursive code iterate two times in "4" reference, but this references don't generate a infinite loop. My problem is to know when function iterate more than one time a reference and is not infinite loop and when is a infinite loop, to inform user.

1 = 4

2 = 1

3 = 2

4 = [2, 3]

5 = 4

This case is a bit diferent from 2th example. This generate a infinite loop. how can I know when cases generate a infinite loop or not?

Upvotes: 15

Views: 17060

Answers (3)

michiel perdeck
michiel perdeck

Reputation: 21

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

Upvotes: 2

RossFabricant
RossFabricant

Reputation: 12492

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

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

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

Upvotes: 18

KJ Saxena
KJ Saxena

Reputation: 21848

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

Upvotes: 5

Related Questions