Recursion and Circular References

Question

I have an array to store IDs and dependent IDs and want be able to identify if any of the relationships cause a circular reference. Any suggestions on how to do this using c#?

Example,

ID DependsOnID
1 2
1 4
2 3
3 1 (circular reference)

Alan · Answer

Bob Although the code I posted earlier appeared to work (and did work with the example in question) I found when I tested it more thoroughly today that it doesn't always work and sometimes hangs. In fact I doubt whether a non-recursive solution is possible. I've therefore recoded it using recursion and hopefully this will now work properly in all cases: using System; class Program { static void Main() { int[] ids = new int[42]{{12} {14} {23} {31}}; Console.WriteLine(IsCircular(ids)); Console.ReadLine(); } static bool IsCircular(int[] ids) { for (int i = 0; i { if (ids[i0] == ids[i1]) return true; } bool[] used = new bool[ids.GetLength(0)]; // all elements false for (int i = 0; i { int idFirst = ids[i0]; int idNext = ids[i1]; if (i > 0) Array.Clear(used 0 used.Length); used[i] = true; bool circular = IsCircularHelper(ids idFirst idNext used); if (circular) return true; } return false; } static bool IsCircularHelper(int[] ids int idFirst int idNext bool[] used) { for (int j = 0; j { if (used[j]) continue; if (ids[j0] == idNext) { idNext = ids[j 1]; if (idFirst == idNext) return true; used[j] = true; bool circular = IsCircularHelper(ids idFirst idNext used); if (circular) return true; } } return false; } }

Bob R · Answer

it works! thanks

Sunny Chen · Answer

Actually for some object relations in domain business analysis recursion and circular references are the relations that we should handle for example a file system directory might be a sub directory of another but it also might be a parent for other directories. So the object directory here should handle this recursion relationship. You can check http://www.castleproject.org for the object relational framework if you encounter the complex object relation in your business analysis.

Alan · Answer

Try this code which appears to be working correctly: using System; class Program { static void Main() { int[] ids = new int[42]{{12} {14} {23} {31}}; Console.WriteLine(IsCircular(ids)); Console.ReadLine(); } static bool IsCircular(int[] ids) { for (int i = 0; i { if (ids[i0] == ids[i1]) return true; } for (int i = 0; i { int idFirst = ids[i0]; int idNext = ids[i1]; for (int j = i + 1; j { if (ids[j0] == idNext && ids[j1] == idFirst) return true; } } for (int i = 0; i { int idFirst = ids[i0]; int idNext = ids[i1]; for (int j = 0; j { if (ids[j0] == idNext) { idNext = ids[j 1]; if (idFirst == idNext) return true; j = (j > 0) ? 0 : 1; } } } return false; } }