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?
By running a cli command npx madge --circular --extensions ts ./ we can quickly get a list of circular dependencies of all . ts files in current directory and its subdirectories. That's it! Now you see where you have circular dependencies and can go and fix it.
A circular dependency occurs when two classes depend on each other. For example, class A needs class B, and class B also needs class A. Circular dependencies can arise in Nest between modules and between providers. While circular dependencies should be avoided where possible, you can't always do so.
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.
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)
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With