Is this picture concerning Cycle Detection wrong?

[liars_paradox]

For the following picture:

 

 

 

 

The description for the picture said:

The figure shows a function ƒ that maps the set S = {0,1,2,3,4,5,6,7,8} to itself. If one starts from x₀ = 2 and repeatedly applies ƒ, one sees the sequence of values2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ...

source: Cycle Detection (2011). Wikipedia.org

 

 

Shouldn't the table read more like "2,0,6,3,1" under f(x)?

[imatfaal]

No. In simple terms the table shows you where you go next - if you are on 8 you goto 0, if you are on 7 goto 4, 4 stays on 4. Just looking at the table alone (or even more so instruction sets) it is sometimes tough to appreciate that loops / cycles will appear. The directed graph [with only one arrow LEAVING each node and the arrows corresponding to the table x and f(x) ] makes it obvious that loops will occur - ie the triangle formed by 1, 6, 3. Any number other than 4 or 7 will put you onto that triangular pathway. The compsci behind cycle detection is beyond me - but the wikipage you quote looks like as good a start as any.

[khaled]

If you want to implement a cycle detection, you need a graph search, using a Queue with a good

heuristic, and a marking list,

 

If you look up Wikipedia, you can find a complex but good algorithms, especially ones that run in Polynomial time

and in open graphs (graph with infinite number of vertices) .. since cycle detection is a Decision Problem,

Edited January 27, 2011 by khaled