Talk:Cycle detection

Other

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)

Contradictions in the article

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.

Fixed. BradAustin2 21:55, 11 March 2007 (UTC)

Reference for the algorithm

The article in JACM cited:

{cite journal|last=Floyd|first=R.W.|authorlink=Robert W. Floyd|title=Non-deterministic Algorithms|journal=J. ACM|pages=pp. 636-644|month=October|year=1967|url=http://doi.acm.org/10.1145/321420.321422}

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)

Apologies for quick revert. You gave no explanations and the reference is indeed present in many sources.

Did you see the 1967 paper yourself? If yes, did you read it carefully? May be it is among the passing remarks or trivially follows from some of the remarks, because the idea itself is quite simple to describe. I remember solving it myself at a student olympiad. And indeed, this reference is given in some books in, e.g., cryptography.

If you are right, then I would recommend to do the following, it this order (for various reasons, related with works of wikipedia).

1. Write an article about Floyd's algorithm of finding cycles in a directed graph (one of examples in the mentioned 1967 paper)
2. In the current article, mention that a number of sources refer to the 1967 paper. Point out that in fact the paper covears a different kind of cycle finding algorithm, referring to the wikipedia article
3. Mention the Knuth's "unreferenced reference".

When I will be in a university library, I will verify the 1967 article myslef. And of course, keep looking for independent confirmation. `'Míkka 15:56, 17 October 2007 (UTC)

The 1967 article is available as a pdf at the ULR given above, and contains a description of an application of the algorithm already described in Depth-first search to cycle-finding, although the article is about a way of presenting such an algorithm as a nondeterministic algorithm rather than about dfs.

You didn't read my question carefully. I don't doubt it contains what you say. My question was whether it contains anything else: an idea, a hint, a footnote. For a mathematician I'd expect you be more carful with details. What is more, the article is not "available as a pdf". It is "available if you have a subscription or pay for it" Anyway, I did read the article myself after all and hereby confirm that no, I didn't see any even remote hints about the "turtle and hare" trick nor even about detection of a cycle. `'Míkka 22:23, 17 October 2007 (UTC)

Sorry! I did read the question: what I did was to omit the word only from my answer. And I was unaware that the pdf wasn't free because an institutional subscription entirely hides the page calling for payment.89.243.59.31 05:59, 18 October 2007 (UTC)

I suspect that the Art of Computer Programming is the ultimate source for the presentation in Floyd's cycle-finding algorithm, because it uses the symbols λ and μ for the parameters, although confusingly Knuth uses λ where the article uses μ, and μ where the article has λ.

I'll ask Don Knuth whether he knows of an earlier published version of tortoise-and-hare when I see him next.89.243.59.31 20:01, 17 October 2007 (UTC)

In the meantime I described the situation in a footnote in the article. Constructive criticism welcome, as always. —David Eppstein 21:14, 17 October 2007 (UTC)

Other algorithms

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)

I agree that it would be a good idea to make an article about the problem, rather than about one particular solution. `'Míkka 22:02, 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 think the point of the pseudo-random function part is not that it be pseudo-random, but that it be a function. You can't use this algorithm for a sequence that is truly random (because it won't cycle), and using it for sequences that depend on more than just the previous term (such as e.g. Fibonacci modulo p) requires some modification. —David Eppstein 23:46, 17 October 2007 (UTC)

The pseudo-random is probably another artefact of the original source for the article being Art of Computer Programming, where the algorithm appears in the context of testing the cycle length of Pseudorandom number generators. (The same is true of Richard Brent's article.) The link redirecting to pseudorandom function family is clearly misleading.89.243.59.31 05:59, 18 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.

There's no unambiguous way of determining a cycle in an infinite sequence that may have repetitions: any time you think you have a repetition, it could change to a longer one. For instance, your sequence could begin

0,1,1,2,3,0,1,1,2,3,0,1,1,2,3,4,0,1,1,2,3,0,1,1,2,3,0,1,1,2,3,4,0,1,1,2,3,0,1,1,2,3,0,1,1,2,3,4,5,...

KMP would work to find repetitions in finite strings where the whole sequence is known (or to find the repetitions up to a given point in an infinite sequence), as you suggest, but would use far greater amounts of memory than the algorithms described here. —David Eppstein (talk) 15:37, 27 February 2009 (UTC)

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)

Too much graphical-heavy image

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)

Example code needs fixing

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)

You seem to have mistaken this for an article about finding cycles in arbitrary graphs. For that, you probably want depth first search or something like that. This is about finding cycles in sequences defined by repeatedly calling a function. f is an input to the algorithm, and (together with the initial value) defines the sequence in which a cycle is to be found. —David Eppstein (talk) 05:06, 21 April 2010 (UTC)

Cycle detection in computer science

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 think the "in mathematics" of our existing lede is inaccurate: the subject of the current article is computer science, just as the different subject you discuss is. If you think cycle detection in graphs is notable enough for its own article, you're welcome to write cycle detection (graph theory) and we can add a hatnote linking to it from this one. —David Eppstein (talk) 17:36, 3 January 2011 (UTC)

I’m thinking of starting a section under something like Cycle (graph theory)#Cycle detection. Vadmium (talk) 10:45, 13 September 2011 (UTC).

Please see WP:NOTDICT. If it's not about the same problem, it should not be in the same article. —David Eppstein (talk) 15:39, 13 September 2011 (UTC)

Can you elaborate? Are you saying that #Cycle detection in computer science and #Cycle detection in directed graphs are not closely enough related to the topic of Cycle (graph theory) to be mentioned in that article? My main problem was that there is bugger-all information relating cycles in directed graphs to things like topological sorting, strongly connected components, back edges. See also Talk:Cycle (graph theory)#Algorithms for cycle detection in graph theory. Vadmium (talk) 02:00, 14 September 2011 (UTC).

Yes. I believe that the problem of finding cycles in a function or sequence (what this article is about) is very different from the problem of finding cycles in a digraph (what you seem to be talking about). They are different problems with different types of inputs, different types of outputs, different styles of analysis, and different algorithms used to solve them. I believe that it would be more confusing than helpful to conflate them. With a function or sequence input over a finite domain, one knows that cycles are always going to exist, there is a unique cycle that can be reached from any starting value, and the goal is to find that cycle using time and space much smaller than the domain of the function. The input is not a graph; it is a single starting value together with a black box for generating the value of a function. Instead, for finding cycles in digraphs, one does not generally know whether or not cycles exist, the whole digraph is given as input so there's no point in spending less than linear time, there are multiple different outgoing edges from each vertex, there can in generally be exponentially cycles, and there's no clear definition of "the cycle" that you want to find. I think you would be much better off discussing the cycle finding problem for digraphs in connection with either topological sorting or strongly connected components — a digraph either has a topological sort or a cycle, so finding a cycle when topological sorting fails can be a useful sanity check, and the strongly connected components are exactly the sets of vertices that are part of a (not necessarily simple) cycle. —David Eppstein (talk) 04:09, 14 September 2011 (UTC)

Okay, thanks for explaining. I think I misunderstood and perhaps my original comment wasn’t clear. I meant to suggest that another existing article, Cycle (graph theory), should be the place for this graph theory problem. The reason it’s all over this talk page of the iterated functions article is probably because the title Cycle detection is ambiguous without further explanation, and some graph theory pages link to it.

 Anyway, I’ve created my section (in a different article) and added a hatnote for it. Vadmium (talk) 06:06, 14 September 2011 (UTC).

Oh, ok. Sorry for misunderstanding your intentions. Yes, the graph theoretic cycle article seems like a good place to at least mention this topic. —David Eppstein (talk) 06:10, 14 September 2011 (UTC)

Cycle detection in directed graphs

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)

Any speeds of Hare and Tortoise?

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)

They need to be coprime, and the larger they are the more steps you might have to take until finding the loop. So 1 and 2 are the best choice. —David Eppstein (talk) 15:14, 26 October 2012 (UTC)

Why co-prime? What difference does it make? 117.198.124.222 (talk) 06:38, 28 October 2012 (UTC)

I'd like to note, for any future reader of this discussion, that the respective speeds of tortoise and hare don't need to be coprime; they only need to be non-zero and distinct. Let $s_{T},s_{H}\in \mathbb {N} ,\mathrm {s.t.} \ s_{T}\leq s_{H},$ denote the speeds of the tortoise and hare respectively; let $\Delta =s_{H}-s_{T}$. To find a solution for any $\mu \geq 0$ and $\lambda >0$, the necessary condition imposed on $s_{T}$ and $s_{H}$ is that there exist $k,l\in \mathbb {N^{+}}$, such that (a) $k\cdot \Delta =l\cdot \lambda$, and (b) $k\cdot s_{T}\geq \mu$.

The reasoning is this:

1. In each step, the mutual distance of tortoise and hare increases by the difference of their speeds $\Delta$, so after $k$ steps, their distance is $k\cdot \Delta$. We want this distance to be a positive multiple of $\lambda$: if their distance is a positive multiple of $\lambda$ and they both have the same value, we've found the cycle. It's necessary to note that the multiple must be positive and not zero, because if it's zero, they are at the same position in the sequence and thus always have the same value. In such case, we obviously cannot find a cycle. This is why we must require that both $k$ and $\Delta$ are non-zero; the latter implying that $s_{T}$ and $s_{H}$ are distinct. From here on, assume $\Delta \neq 0$.
2. We must assure that after the $k^{\mathrm {th} }$ step, both tortoise and hare are inside the cycle. Hence the requirement $k\cdot s_{T}\geq \mu$, which ensures that after the $k^{\mathrm {th} }$ step, the tortoise (and thus the hare as well) has entered the cycle. Note that $k$ can be any positive natural number, and therefore any positive multiple of $\lambda$; let $k_{\lambda }$ denote any such positive multiple of $\lambda$. For each $k_{\lambda }$, $k_{\lambda }\cdot \Delta$ is also a positive multiple of $\lambda$, viz. $\exists l\in \mathbb {N^{+}} :k_{\lambda }\cdot \Delta =l\cdot \lambda$. In other words, any $k_{\lambda }$ can satisfy equation (a). Now let's assume $s_{T}=0$; then the equation (b) $k_{\lambda }\cdot s_{T}\geq \mu$ implies $\mu =0$. But since we want to allow any $\mu \geq 0$, we must require $s_{T}\neq 0$ and thus, since $s_{T}$ cannot be negative, $s_{T}>0$. There are infinitely many $k_{\lambda }$, and assuming $s_{T}>0$, there are also infinitely many those $k_{\lambda }$, for which $k_{\lambda }\cdot s_{T}\geq \mu$. In other words, if the tortoise is moving at a non-zero speed, it would eventually enter the cycle and synchronize with the hare, no matter how large $\mu$ or $\lambda$ or $s_{H}$ is.

We can pick any $s_{T}$ and $s_{H}$, as long as they fulfill the above conditions, namely $s_{T}\neq s_{H}$ and $s_{T}>0$, or simply $0<s_{T}<s_{H}$. Whether they are coprime or not does not matter. --84.245.121.75 (talk) 09:17, 3 August 2020 (UTC)

Where do the Hare and Tortoise meet?

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)

At each step the hare gets one position farther ahead of the tortoise, because it is faster by one unit. So after k steps (when the tortoise enters the loop) the hare is k positions ahead, or equivalently L-k steps positions behind, where L is the length of the loop. And after L-k more steps, the hare has caught up to the tortoise again. At this time the tortoise will have moved L-k units past where it entered the loop; that is, k nodes before the entry point.—David Eppstein (talk) 07:19, 28 October 2012 (UTC)

What if the speed of the tortoise and hare are x and y respectively? and the nodes before the loop is k and nodes in the loop is L?117.198.136.11 (talk) 06:30, 30 October 2012 (UTC)

Wrong equation

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)

Yes, that is the wrong equation. It is so wrong that it is not even in the article. Instead, what we have is x_i = x_{i+kλ}, which is not so difficult to satisfy. —David Eppstein (talk) 23:37, 9 December 2012 (UTC)

Mistake in Python floyd code

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)

Try working through a few examples. —David Eppstein (talk) 17:57, 8 May 2016 (UTC)

I tried to run an example with the following directed graph: 0 -> 1 -> 2 -> 3 -> 1. Here: λ = 3 and μ = 1.

Existing 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.

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

I cannot find the mistake in my execution. Are you sure the algorithm is correct? M12ats 87 (talk) 13:04, 20 July 2022 (UTC)

Mistake in Brent's article

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)

Mistake in Python floyd code 2

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)

I found my mistake:

In an iteration where lam (which stands for lambda, i.e., λ) is zeroed, we still do lam += 1 at the end of the iteration. Thus, we never have lam = 0 at the end of an iteration.

With that in mind, illustration 2 in my execution image shows the states of variables after the first iteration, and I have lam = 0. This is wrong. After fixing this, the execution is okay, and we get the correct parameters.

Two more points:

1. The headline for my question is incorrect: My illustration represents an execution of Brent's algorithm, not Floyd's, because only Brent's algorithm has a variable named power.

2. The illustration I used is confusing. Using a table where each row represents variable state after an iteration and columns represent variable states is more comfortable. For positions of pointers, I flat the linked list and also put it in a column. Example: https://www.dropbox.com/s/ni5s3j9keuleqai/execution-python-code-brent-algorithm_version2_trimmed.png?dl=0 M12ats 87 (talk) 13:58, 21 October 2022 (UTC)

Possible typo in code comment

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)