Detecting Infinite Loop

Just yesterday I have come across a problem at work. The problem is the possible occurrence of infinite loop inside a tree structure. To solve it, I need to come up with an algorithm to detect infinite loop occurrence. This little puzzle brings back the memory of a similar and simpler puzzle my high school computer science instructor asked the class.

The problem was: Given an uni-directional linked list, detect infinite loop without using any extra data structure.

The linked list data structure is really simple:
Node.java

class Node {
  Node next;
}

My solution to the problem was something like:
Function isInInfiniteLoop

boolean isInInfiniteLoop(Node node) {
  if (node == null) {
    return false;
  }
  Node turtle = node; // slower moving node
  Node rabbit = node.next; // faster moving node
  while (rabbit != null) {
    if (rabbit.equals(turtle)) {
      // the faster moving node has caught up with the slower moving node
      return true;
    } else if (rabbit.next == null) {
      // reached the end of list
      return false;
    } else {
      turtle = turtle.next;
      rabbit = rabbit.next.next;
    }
  }
  // rabbit reached the end
  return false;
}

Simple, isn’t it! At the first glance, almost everyone wondered if this short piece of code is really up to the task. The logic behind it is analogous to having two runners, one (rabbit) running faster than the other (turtle) and, if the course is circular, the faster runner eventually overlapping the slower runner.

Note that it is important for the slower runner to keep moving instead of remaining at the same node because we don’t know where the course will merge into circle. If the merge point is further down the course, the non-moving runner will never enter the loop which the faster runner is lapping.

This algorithm is not only simplistic, it is also efficient. It is just a O(N) or linear function.

Now, getting back to my work related problem, the data structure I am facing is a tree instead of a sequential linked list. The structure is something like:
TreeNode.java

class TreeNode {
  TreeNode parent;
  List children;
}

I have had a hard time figuring out how to apply my little rabbit and turtle algorithm into this context. When it comes to tree structure, I always think recursion. However, I cannot imagine transforming my algorithm into a recursive algorithm. It just appears overwhelming.

Then, it suddenly hits me, since TreeNode can traverse to its parent, luckily, I could do it backwards. The traversal from child to parent is just another sequential linked list.

It simply feels awesome to see that this little algorithm I thought of years ago is still useful today.

About these ads

19 Responses to “Detecting Infinite Loop”

  1. Anurag Garg Says:

    dats fine…but how can we remove the loop from the link list(in some efficient manner..)

  2. An alternative way is to use treat the tree like a directed graph [D = (N,A); N= nodes, A = arcs] and then apply a Topological Ordering to the nodes. This algorithm has an O(|N|) runtime.

    Let D’ be a new graph with D’ = (N’, A) where N’ initially contains all nodes.

    i := 1
    while there exists a Node v with no parents,
    label the node as i
    i++
    delete v from N’ and all the outgoing arcs in D’
    end while

    If after |N| iterations, N’ is not empty, then you know you have a directed cycle.

  3. To Anurag Garg:
    To break the infinite loop, we need to find the link that causes it. The causing link should be the first link that points to an already traversed node. My algorithm however does not pinpoint the causing link.

    I’m afraid I can’t yet come up with an easy and efficient algorithm to do that. I know a more complex algorithm that can pinpoint the causing link but require an O(N^2) operation. I’m not sure if that’s efficient enough for you.

  4. To Rod:
    The problem only gives us the starting node. That means we wouldn’t have N’ (where it contains all nodes). Your solution also suggests using an extra data structure D’ for record keeping, which the problem says not to use.

  5. What you’ve discovered is called Floyd’s cycle-finding algorithm and is used in Pollard Rho factorization because the self loops make a Rho looking shape

    http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm

    http://en.wikipedia.org/wiki/Pollard's_rho_algorithm

  6. To Jack:
    Thanks a lot for the info!
    –It is sometimes called the “tortoise and the hare”-algorithm.–
    WOW! even the metaphor is the same.
    It’s nice to know there is a official name and proven algorithm for this.

  7. Hi Eddie,
    As far as my understanding of your algorithm goes, this can effectively detect loops of size 1. For eg. lets say the 10th node points to the 11th node which points back to the former and creates an infinite loop.

    I have a problem wherein I do not know the size of the loop ( may involve 2 nodes, 10 nodes or 20 nodes or whatever) and I
    do not know the starting node that causes the infinite loop.
    Can your algorithm be extended to resolve my problem? Please explain. Thanks.

  8. To Maddy:
    Actually this algorithm can detect loops of any number of nodes, not necessarily just size of 1.
    You can try drawing linked lists having loops composed by different number of nodes (2, 10, or 20) and tracing the steps manually.
    I think it’s more visible and easier to understand the algorithm this way.
    Please give it a try and if you have any question, let me know!

    • The easiest way to understand the algorithm is to use two key insights:
      1) if a cycle exists, the faster runner/hare/rabbit is (kind of) behind the turtle when the turtle crosses the cycle’s endpoint.
      2) the turtle advances one step and the rabbit two, so the rabbit gets one step closer to the turtle every iteration.

      Clearly, the size of loop is insignificant. As the rabbit only closes in by one step every iteration, it can’t jump over the turtle at any point.
      Remark that this understanding doesn’t help you think about the efficiency of the algorithm, only about its correctness.

  9. Hi, there is a small bug in your code. When it is not cyclic, rabbit.next.next can give you a nullpointer exception if the length is odd.

  10. Hi! I was surfing and found your blog post… nice! I love your blog. :) Cheers! Sandra. R.

  11. tszming Says:

    Tree must be acyclic, else it is a graph.

    :)

  12. Sudarshan Says:

    The logic is very simple,clear and easy to implement and maintain.

    Thanks
    Sudarshan

  13. This explanation is too good. This was the question I was asked today in my interview and I couldn’t answer :(
    Wish I had read your blog earlier…….

  14. Hi, I know this has been written long time ago, but I don’t get clearly how the algorithm works on the tree by going backwards.

    The node in which the loop goes ( the one that has two parents or pointed by two other nodes) would have refreshed his parent reference?

    Or am I getting things wrong?

  15. [...] Floyd’s Cycle Detection or the¬†tortoise¬†and the hare or the rabbit and the turtle. [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: