Recursion and Circular References

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 < ids.GetLength(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 < ids.GetLength(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 < ids.GetLength(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;
      }  
}

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.

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 < ids.GetLength(0); i++)
        {
           if (ids[i,0] == ids[i,1]) return true;
        }

        for (int i = 0; i < ids.GetLength(0) - 1; i++)
        {
           int idFirst = ids[i,0];
           int idNext  = ids[i,1];
           for (int j = i + 1; j < ids.GetLength(0); j++)
           {
              if (ids[j,0] == idNext && ids[j,1] == idFirst) return true;
           }
        }

        for (int i = 0; i < ids.GetLength(0); i++)
        {
           int idFirst = ids[i,0];
           int idNext  = ids[i,1];
           for (int j = 0; j < ids.GetLength(0) && j != i; j++)
           {
              if (ids[j,0] == idNext)
              {
                 idNext = ids[j, 1];
                 if (idFirst == idNext) return true;
                 j = (j > 0) ? 0 : 1;                 
              }
           }
          
         }

         return false;
     }            
}