A fact from Cycle detection appeared on Wikipedia's
Main Page in the
Did you know column on 26 October 2007. The text of the entry was as follows:
|
This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
Sorry about the mistake in the image - lambda should be 2 (the number of elements not involved in the cycle). I uploaded (and re-uploaded) a fixed image, but it doesn't seem to have taken effect. I tried emptying my cache, but the old, incorrect image is still there. Also, the new image has labels on the elements. I'll give it a few hours, and if it still hasn't worked I'm re-uploading again. -- Decrypt3 18:38, May 21, 2004 (UTC)
Fixed it by re-uploading under a different name. Any sysops who see this should delete CycleFinding.Dec3.png. -- Decrypt3 12:29, May 22, 2004 (UTC)
The article states that the worst-case performance of the algorithm is λ + μ/2 comparisons. This statement cannot be correct, since in the example where λ=2 and μ=6, λ + μ/2 = 5, but the description of a running of the algorithm states that it finishes in 6 iterations.
The article also states that the slow sequence cannot get more than halfway around the loop without meeting the fast sequence, but in the given example the sequences meet at the second half of the loop.
The article in JACM cited:
does in fact contain a cycle-finding algorithm, but it's a backtracking algorithm for finding all cycles in a graph of a bounded size (essentially depth-first search). It's not the tortoise-and-hare algorithm. I'm intrigued that a little Googling for citations finds only references to the same JACM paper. Is there a published source of the original algorithm, or are we all relying on folk-knowledge that this was first published by Floyd? —Preceding unsigned comment added by 163.1.125.59 ( talk) 10:56, 16 October 2007 (UTC)
Don Knuth's Art of Computer Programming, Vol 2 (Seminumerical Algorithms) attributes the idea to Bob Floyd, and has the algorithm in the exercises. That dates it to about 1968, but does not give a published reference. 163.1.125.59 13:38, 16 October 2007 (UTC)
Floyd's is not the only algorithm for solving the problem of detecting cycles in a sequence or functional graph. There is also an algorithm of Brent: maintain a single pointer into the sequence, and compare it to the sequence value at the last position that was a power of two. An algorithm of Nivasch DOI:10.1016/j.ipl.2004.01.016 that uses more space but fewer function evaluations, and many other people's algorithms described briefly in Nivasch's paper. I don't think we need separate Wikipedia articles for all of these different techniques, but I think it would be appropriate to have an article that covers the subject more generally, describing both the different techniques and several applications of this problem (loop detection in logic programming, Pollard's rho factorization, cycle detection for pseudorandom number generators, etc). So I suggest we move this article to Loop detection or Cycle detection or Cycle-finding algorithms or something more generically named like that and add descriptions of the other techniques. Any thoughts on this plan? — David Eppstein 21:39, 17 October 2007 (UTC)
While I am at this (not for long), I'd like to say that the description of the algorithm has two major flaws IMO. First, the algorithm must be described in terlm of the most basic model, i.e., in terms of a graph. Second, I fail to uderstand why a
pseudo-random function is used in description. I don't even want to lookm into "
pseudo-random function" article: the phrase "Clearly such a sequence must cycle after at most n iterations of the pseudo-random function, because there are only n possible values for an element." implies that the value of f(i) is deterministic regardless the call of the function. And the whole discussion is in fact valid for any funcions whose
range belongs to its
domain. Or am I missinig something here? `'
Míkka
23:37, 17 October 2007 (UTC)
I've 2 questions ? Can we use floyds cycle finding algorithm sequence of values which repeats itself but contains duplicate values .
Fib mod m can have values like 0,1,1,2,3... now hare and tortoise are equal at 1,1 or some other elements. Shouldn't they be unique ? I think we need to find the periodicity using KMP or something alike. Please suggest.
How is such algorithm called — early loop detection in OpenRC? I think it should be added to the article. — Xaionaro ( talk) 11:20, 24 January 2014 (UTC)
The hare - tortoise image is cute, but I think it's too much 'heavy'. A more stylized and lighter image may be better. —Preceding unsigned comment added by 79.42.205.63 ( talk • contribs)
I like it.-- CzarKirk ( talk) 03:30, 16 January 2009 (UTC)
Currently both the floyd and brent code examples of the algorithm leaves out a critical component, making it nearly useless as is. both algorithms have an undefined function f(someNode) which is explained to simply return the node next to someNode. However in most graphs there isnt a single node adjacent to another, there are several. since f() isnt actually defined it doesnt tell you which of the neighbor nodes should be selected, and clearly just picking any at all wont work (or else the entire graph doesnt get traversed). This should be fixed, or perhaps someone could explain this to me and i can fix it? - Debeo Morium: to be morally bound ( Talk | Contribs) 04:55, 21 April 2010 (UTC)
In computer science, cycle detection is the problem of detecting whether a Graph has any paths that begin and end in the same vertex. I think there should be a subsection about this, or a link to another page that talks about this problem. -- Erel Segal ( talk) 10:09, 3 January 2011 (UTC)
I agree with Erel Segal. I think this article, "cycle detection", should define cycle detection as the more general detection of cycles in a directed graph. The special case dealt with here (functional case, where a given node/value has a single successor) deserves special attention, but as a special case, not as the full "cycle detection" problem.
I was searching for incremental algorithms for the graph theoretic cycle detection -- i.e., where you've identified all cycles in a huge network, then one link is changed and you need to adjust the cycle identification. Is it possible to do this more efficiently than a full reprocessing of the full network? I don't know the answer (yet), but it would have been nice for me if the article might have addressed this. — Preceding unsigned comment added by Ldc ( talk • contribs) 22:29, 10 August 2011 (UTC)
Does it have to be 1x and 2x or any numbers will do? Should the numbers not be co-prime? What about 2x and 8x or 21x and 55x? 117.198.122.24 ( talk) 07:38, 26 October 2012 (UTC)
I can't seem to understand why the T and H should meet at the node, k nodes before entry point, whenever the length of the list excluding (before) the loop is k? Does this only work when the speeds are x and 2x or all the time? 117.198.124.222 ( talk) 06:39, 28 October 2012 (UTC)
x_i = x_i + kλ cannot be true unless kλ=0. I assume it's supposed to be x_(i+1) = x_i + kλ — Preceding unsigned comment added by 208.54.80.171 ( talk) 23:31, 9 December 2012 (UTC)
It seems like the second loop might never end. Both Tortoise and Hare advance at the same speed. What's going on there? — Preceding unsigned comment added by 31.154.17.58 ( talk) 14:28, 8 May 2016 (UTC)
LCG of TI calculators is ok, because they have more than 32 bits of precision, Brent hit integer overflow in his own program rather than mistake in LCG — Preceding unsigned comment added by 94.244.46.42 ( talk) 12:16, 14 February 2021 (UTC)
I tried to run an example ([1]) with the following directed graph: 0 → 1 → 2 → 3 → 1. Here: λ = 3 and μ = 1.
Exiting the first while loop, I have parameters power=2, lam=1. This means that after the for loop with range(lam), the distance between hare and tortoise is 2, and not λ = 3.
I cannot find the mistake in my execution. Are you sure the algorithm is correct?
Resources:
[1] Link to an image of the execution I wrote using my iPad: https://www.dropbox.com/s/gv28mk695pjig8b/execution-python-code-brent-algorithm-section-1.png?dl=0
M12ats 87 ( talk) 21:45, 10 August 2022 (UTC)
In code we can see
Because the # distance between them is constant at 2ν, a multiple of λ, # they will agree as soon as the tortoise reaches index μ.
What is 2ν? Is it node "ν", where there two in-edge, or something else? Tookser ( talk) 10:50, 24 March 2024 (UTC)
A fact from Cycle detection appeared on Wikipedia's
Main Page in the
Did you know column on 26 October 2007. The text of the entry was as follows:
|
This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
Sorry about the mistake in the image - lambda should be 2 (the number of elements not involved in the cycle). I uploaded (and re-uploaded) a fixed image, but it doesn't seem to have taken effect. I tried emptying my cache, but the old, incorrect image is still there. Also, the new image has labels on the elements. I'll give it a few hours, and if it still hasn't worked I'm re-uploading again. -- Decrypt3 18:38, May 21, 2004 (UTC)
Fixed it by re-uploading under a different name. Any sysops who see this should delete CycleFinding.Dec3.png. -- Decrypt3 12:29, May 22, 2004 (UTC)
The article states that the worst-case performance of the algorithm is λ + μ/2 comparisons. This statement cannot be correct, since in the example where λ=2 and μ=6, λ + μ/2 = 5, but the description of a running of the algorithm states that it finishes in 6 iterations.
The article also states that the slow sequence cannot get more than halfway around the loop without meeting the fast sequence, but in the given example the sequences meet at the second half of the loop.
The article in JACM cited:
does in fact contain a cycle-finding algorithm, but it's a backtracking algorithm for finding all cycles in a graph of a bounded size (essentially depth-first search). It's not the tortoise-and-hare algorithm. I'm intrigued that a little Googling for citations finds only references to the same JACM paper. Is there a published source of the original algorithm, or are we all relying on folk-knowledge that this was first published by Floyd? —Preceding unsigned comment added by 163.1.125.59 ( talk) 10:56, 16 October 2007 (UTC)
Don Knuth's Art of Computer Programming, Vol 2 (Seminumerical Algorithms) attributes the idea to Bob Floyd, and has the algorithm in the exercises. That dates it to about 1968, but does not give a published reference. 163.1.125.59 13:38, 16 October 2007 (UTC)
Floyd's is not the only algorithm for solving the problem of detecting cycles in a sequence or functional graph. There is also an algorithm of Brent: maintain a single pointer into the sequence, and compare it to the sequence value at the last position that was a power of two. An algorithm of Nivasch DOI:10.1016/j.ipl.2004.01.016 that uses more space but fewer function evaluations, and many other people's algorithms described briefly in Nivasch's paper. I don't think we need separate Wikipedia articles for all of these different techniques, but I think it would be appropriate to have an article that covers the subject more generally, describing both the different techniques and several applications of this problem (loop detection in logic programming, Pollard's rho factorization, cycle detection for pseudorandom number generators, etc). So I suggest we move this article to Loop detection or Cycle detection or Cycle-finding algorithms or something more generically named like that and add descriptions of the other techniques. Any thoughts on this plan? — David Eppstein 21:39, 17 October 2007 (UTC)
While I am at this (not for long), I'd like to say that the description of the algorithm has two major flaws IMO. First, the algorithm must be described in terlm of the most basic model, i.e., in terms of a graph. Second, I fail to uderstand why a
pseudo-random function is used in description. I don't even want to lookm into "
pseudo-random function" article: the phrase "Clearly such a sequence must cycle after at most n iterations of the pseudo-random function, because there are only n possible values for an element." implies that the value of f(i) is deterministic regardless the call of the function. And the whole discussion is in fact valid for any funcions whose
range belongs to its
domain. Or am I missinig something here? `'
Míkka
23:37, 17 October 2007 (UTC)
I've 2 questions ? Can we use floyds cycle finding algorithm sequence of values which repeats itself but contains duplicate values .
Fib mod m can have values like 0,1,1,2,3... now hare and tortoise are equal at 1,1 or some other elements. Shouldn't they be unique ? I think we need to find the periodicity using KMP or something alike. Please suggest.
How is such algorithm called — early loop detection in OpenRC? I think it should be added to the article. — Xaionaro ( talk) 11:20, 24 January 2014 (UTC)
The hare - tortoise image is cute, but I think it's too much 'heavy'. A more stylized and lighter image may be better. —Preceding unsigned comment added by 79.42.205.63 ( talk • contribs)
I like it.-- CzarKirk ( talk) 03:30, 16 January 2009 (UTC)
Currently both the floyd and brent code examples of the algorithm leaves out a critical component, making it nearly useless as is. both algorithms have an undefined function f(someNode) which is explained to simply return the node next to someNode. However in most graphs there isnt a single node adjacent to another, there are several. since f() isnt actually defined it doesnt tell you which of the neighbor nodes should be selected, and clearly just picking any at all wont work (or else the entire graph doesnt get traversed). This should be fixed, or perhaps someone could explain this to me and i can fix it? - Debeo Morium: to be morally bound ( Talk | Contribs) 04:55, 21 April 2010 (UTC)
In computer science, cycle detection is the problem of detecting whether a Graph has any paths that begin and end in the same vertex. I think there should be a subsection about this, or a link to another page that talks about this problem. -- Erel Segal ( talk) 10:09, 3 January 2011 (UTC)
I agree with Erel Segal. I think this article, "cycle detection", should define cycle detection as the more general detection of cycles in a directed graph. The special case dealt with here (functional case, where a given node/value has a single successor) deserves special attention, but as a special case, not as the full "cycle detection" problem.
I was searching for incremental algorithms for the graph theoretic cycle detection -- i.e., where you've identified all cycles in a huge network, then one link is changed and you need to adjust the cycle identification. Is it possible to do this more efficiently than a full reprocessing of the full network? I don't know the answer (yet), but it would have been nice for me if the article might have addressed this. — Preceding unsigned comment added by Ldc ( talk • contribs) 22:29, 10 August 2011 (UTC)
Does it have to be 1x and 2x or any numbers will do? Should the numbers not be co-prime? What about 2x and 8x or 21x and 55x? 117.198.122.24 ( talk) 07:38, 26 October 2012 (UTC)
I can't seem to understand why the T and H should meet at the node, k nodes before entry point, whenever the length of the list excluding (before) the loop is k? Does this only work when the speeds are x and 2x or all the time? 117.198.124.222 ( talk) 06:39, 28 October 2012 (UTC)
x_i = x_i + kλ cannot be true unless kλ=0. I assume it's supposed to be x_(i+1) = x_i + kλ — Preceding unsigned comment added by 208.54.80.171 ( talk) 23:31, 9 December 2012 (UTC)
It seems like the second loop might never end. Both Tortoise and Hare advance at the same speed. What's going on there? — Preceding unsigned comment added by 31.154.17.58 ( talk) 14:28, 8 May 2016 (UTC)
LCG of TI calculators is ok, because they have more than 32 bits of precision, Brent hit integer overflow in his own program rather than mistake in LCG — Preceding unsigned comment added by 94.244.46.42 ( talk) 12:16, 14 February 2021 (UTC)
I tried to run an example ([1]) with the following directed graph: 0 → 1 → 2 → 3 → 1. Here: λ = 3 and μ = 1.
Exiting the first while loop, I have parameters power=2, lam=1. This means that after the for loop with range(lam), the distance between hare and tortoise is 2, and not λ = 3.
I cannot find the mistake in my execution. Are you sure the algorithm is correct?
Resources:
[1] Link to an image of the execution I wrote using my iPad: https://www.dropbox.com/s/gv28mk695pjig8b/execution-python-code-brent-algorithm-section-1.png?dl=0
M12ats 87 ( talk) 21:45, 10 August 2022 (UTC)
In code we can see
Because the # distance between them is constant at 2ν, a multiple of λ, # they will agree as soon as the tortoise reaches index μ.
What is 2ν? Is it node "ν", where there two in-edge, or something else? Tookser ( talk) 10:50, 24 March 2024 (UTC)