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.
February 25, 2007 at 11:35 pm
dats fine…but how can we remove the loop from the link list(in some efficient manner..)
February 26, 2007 at 10:57 am
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.
February 26, 2007 at 1:13 pm
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.
February 26, 2007 at 1:20 pm
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.
March 22, 2007 at 1:23 pm
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
March 22, 2007 at 10:59 pm
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.
November 3, 2007 at 7:29 am
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.
November 3, 2007 at 11:26 pm
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!
August 3, 2010 at 9:12 am
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.
January 30, 2009 at 3:57 pm
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.
August 7, 2010 at 3:27 am
No, it can’t because you just checked rabbit.next in the previous else clause.
September 16, 2011 at 2:11 pm
ah, right, didn’t see that.
September 10, 2009 at 9:51 pm
Hi! I was surfing and found your blog post… nice! I love your blog. :) Cheers! Sandra. R.
June 3, 2010 at 9:24 am
Tree must be acyclic, else it is a graph.
:)
June 3, 2010 at 12:07 pm
good point, thanks
October 13, 2010 at 7:51 pm
The logic is very simple,clear and easy to implement and maintain.
Thanks
Sudarshan
September 16, 2011 at 8:41 am
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…….
December 3, 2011 at 1:20 am
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?
February 20, 2013 at 11:28 am
[…] Floyd’s Cycle Detection or the tortoise and the hare or the rabbit and the turtle. […]
January 18, 2015 at 2:54 pm
Hello webmaster do you need unlimited articles for your website ?
What if you could copy content from other blogs, make
it unique and publish on your website – i know the right
tool for you, just search in google:
kisamtai’s article tool
September 17, 2015 at 9:41 am
[…] or “the turtle and the rabbit algorithm”. I found some examples in languages such as Java and Python but nothing using PHP, then I did it by my own based on what I saw. The result code is […]
April 5, 2018 at 3:14 pm
[…] Safe Steroids Store Safe Steroids Store Safe Steroids Store Safe Steroids Store Safe Steroids Store Safe Steroids Store Safe Steroids Store Safe Steroids Store Safe Steroids Store Safe Steroids Store Safe Steroids Store […]
January 2, 2019 at 7:41 pm
If you like to earn, each and every time you play subsequently frequent participation is essential.
June 7, 2019 at 5:21 am
Jouw tanden bleken? Dat doe je gewoon thuis, met onze veilige en vertrouwde producten.