What would be a good algorithm for a circular reference check in this case?

Question

Given you have the following class (bad C#, but you get the drift):

public abstract class AmICircular
{
  // assume Children is never null
  private List<AmICircular> Children {get;set;}

  // assume target is never null
  public void Add(AmICircular target)
  {
    target.PerformCircularReferenceCheck(this);
    Children.Add(target);
  }

  // throws when a circular reference is detected
  protected abstract void PerformCircularReferenceCheck(AmICircular target);
}

How would you implement PerformCircularReferenceCheck? And, no, this isn't homework.

The naive implementation, imo, would be to do a reference check on this and all children, then call PerformCircularReferenceCheck on target, passing this. But I'm wondering if there are better, proven effective, ways to do this, such as adding a method to collapse the entire Children tree of references for this and target and then examine the results (less pressure on the stack?), or perhaps avoid the check entirely by using a different (maybe self-checking!) collection other than List<T>?

How would you do this?

edit: As stefan pointed out, it is only necessary to determine if this is reachable by the target

Answer 1

The iterative solution is to define a set R (reachable) and CR (children of Reachable).

You start of with R = {this} and RC = {this.children}.

In each step, you check if CR contains this (or target, depending on your exact goal). If not, you add CR to R and set CR to the children of CR, and remove the elements of R from CR.

If CR becomes empty, R is the complete set of elements reachable from this.

Answer 2

In the case where you never add self-referencing (to be defined later) objects, your data structure describes a directed acyclic graph (http://en.wikipedia.org/wiki/Directed_acyclic_graph), where each instance of the of the IAmCircular class describes a node with a set of direct successor nodes = Children.

Assuming the precondition that up to this moment, no cycle was created, the function you want, PerformCircularReferenceCheck, needs only to check if "this" is reachable from "target". If it is, it should return an exception.

Complexity theory wise, this problem is ST-connectivity (http://en.wikipedia.org/wiki/St-connectivity) and is complete for the class NL (http://en.wikipedia.org/wiki/NL_(complexity)), even when you restrict the input to acyclic graphs (which is your case).

In particular, Savitch's theorem (http://en.wikipedia.org/wiki/Savitch%27s_theorem) gives a constructive way to create a O(log^2 n) space algorithm (running in time O(n^2)) for it, where n is the number of nodes.

Also, being NL-complete, it is unlikely that there exists an algorithm which runs in space O(log n) (i.e. use only a constant number of pointers to nodes), since that would imply the unlikely NL = L. EDIT: in particular, small variations of the hare and turtle algo suggested by someone would not work (because they would use too little space).

I would recommend implementing the trivial O(n) time, O(n) space algorithm, which generates for "target" its set of successors (recursively) and verifying if "this" appears in this set.

Be careful, the explicit construction of the set is important. Otherwise, if you just recursively verify if "this" is reachable by any successor of "target", you risk to run in exponential time.

I recommended the O(n) time/O(n) space algorithm because it is asymptotically the best you can do time-wise, and you are already using O(n) space for your data structure.