Java Program to Implement Floyd Cycle Algorithm

This is a Java Program to Implement Floyd Cycle Algorithm. Cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values. Floyd’s cycle-finding algorithm, also called the “tortoise and the hare” algorithm, is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds.

Here is the source code of the Java Program to Implement Floyd Cycle Algorithm . The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 ** Java Program to Implement Floyd Cycle Algorithm 
 **/
 
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
 
/** Class FloydCycle **/
public class FloydCycle
{
    private List<Integer> func;
    private int lam, mu; 
    /** Constructor **/
    public FloydCycle(List<Integer> list, int x0)
    {
        func = list;
        /** print sequence **/
        printSequence(x0);
        /** find cycle **/
        findCycle(x0);
        /** display results **/
        display();
    }
    /** function to find cycle **/
    private void findCycle(int x0)
    {
        int tortoise = f(x0);    
        int hare = f(f(x0));    
        while (tortoise != hare)
        {
            tortoise = f(tortoise);
            hare = f(f(hare));
        }
        int mu = 0;
        tortoise = x0;
        while (tortoise != hare)
        {
            tortoise = f(tortoise);
            hare = f(hare);
            mu += 1;
        }
        int lam = 1;
        hare = f(tortoise);
        while (tortoise != hare)
        {
            hare = f(hare);
            lam += 1;
        }
        this.lam = lam;
        this.mu = mu;
    }
    /** function to return value of function f(x) **/
    private int f(int p)
    {
        return func.get(p);
    }
    /** function to print first n sequence **/
    public void printSequence(int x0)
    {
        int n = func.size();
        int tempx = x0;
        System.out.print("\nFirst "+ n +" elements in sequence : \n"+ tempx);
        for (int i = 0; i < n; i++)
        {
            tempx = f(tempx);
            System.out.print(" "+ tempx);
        }
        System.out.println();        
    }
    /** function to display results **/
    public void display()
    {
        System.out.println("\nLength of cycle : "+ lam);
        System.out.println("Position : "+ (mu + 1));
    }
    /** Main function **/
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Floyd Cycle Algorithm Test\n");
        System.out.println("Enter size of list");
        int n = scan.nextInt();
        List<Integer> list = new ArrayList<Integer>();
        System.out.println("\nEnter f(x)");
        for (int i = 0; i < n; i++)
            list.add(scan.nextInt());
        System.out.println("\nEnter x0");
        int x0 = scan.nextInt();
        FloydCycle fc = new FloydCycle(list, x0);
    }
}

Floyd Cycle Algorithm Test
 
Enter size of list
9
 
Enter f(x)
6 6 0 1 4 3 3 4 0
 
Enter x0
2
 
First 9 elements in sequence :
2 0 6 3 1 6 3 1 6 3
 
Length of cycle : 3
Position : 3