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[4,2]{{1,2}, {1,4}, {2,3}, {3,1}}; Console.WriteLine(IsCircular(ids)); Console.ReadLine(); } static bool IsCircular(int[,] ids) { for (int i = 0; i { if (ids[i,0] == ids[i,1]) return true; } bool[] used = new bool[ids.GetLength(0)]; // all elements false for (int i = 0; i { int idFirst = ids[i,0]; int idNext = ids[i,1]; 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[j,0] == 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[4,2]{{1,2}, {1,4}, {2,3}, {3,1}}; Console.WriteLine(IsCircular(ids)); Console.ReadLine(); } static bool IsCircular(int[,] ids) { for (int i = 0; i { if (ids[i,0] == ids[i,1]) return true; } for (int i = 0; i { int idFirst = ids[i,0]; int idNext = ids[i,1]; for (int j = i + 1; j { if (ids[j,0] == idNext && ids[j,1] == idFirst) return true; } } for (int i = 0; i { int idFirst = ids[i,0]; int idNext = ids[i,1]; for (int j = 0; j { if (ids[j,0] == idNext) { idNext = ids[j, 1]; if (idFirst == idNext) return true; j = (j > 0) ? 0 : 1; } } } return false; } }

Recursion and Circular References

Answers (4)