Floyd’s Algorithm – Tortoise and Hare

Methodology

In a recent post we talked about finding a cycle in a graph using a breadth first search (BFS) and modified topological sort approach. Here we’ll look at another method, Floyd’s cycle finding algorithm, nicknamed The Tortoise and the Hare, which detects a cycle differently from our previous method. In the prevous post the idea is to eliminate all vertices and edges that are not part of cycles so that what’s left is a cycle or cycles. Floyd’s algorithm finds cycles directly – it recognizes that it’s traversing a cycle. This has the advantage of allowing us to get the cycle length. Previously we could have easily totaled the vertices remaining in the cycles but since we never traversed the cycles we didn’t know how many cycles there were or their lengths.

Another characteristic of Floyd’s algorithm is that it is well suited for space complexity since it stores only two pointers that move through the graph. One pointer, the hare, moves twice as fast as the other, the tortoise, and if the two meet we know they’re in a cycle. To simplify the example we’ll start with a functional graph. In a functional graph the vertices can have no more than one outbound edge. So each vertex can be thought of as having a function (edge) that returns the next vertex, or null if there’s no outbound edge.

 Fig.1 A functional graph containing a cycle

In the code, instead of a Vertex.outEdges() method as before, we have outEdge() which returns a single Edge containing the destination Vertex. Here’s a Java implementation that begins at a passed-in start Vertex and makes the tortoise and hare race through the graph.

Floyd’s Algorithm

public static void findCycleInfo(Set vertices, Vertex startVertex){

   Vertex tortoise = startVertex;   //vertex zero

   Vertex hare = startVertex;       //vertex zero

   while (true){

      if (hare.outEdge() == null){

         System.out.println(“No cycle”);

         break;

      }else hare = hare.outEdge().dest();   //Advance hare a step

      if (hare.outEdge() == null){

         System.out.println(“No cycle”);

         break;

      }else hare = hare.outEdge().dest();   //Advance hare another step

      tortoise = tortoise.outEdge().dest(); //Advance tortoise one step

      if (tortoise == hare){                //Compare identity

         System.out.println(“Cycle found”);

         break;

      }

   }

}

Note that to further simplify things we have considered searching only one branch of the graph. In the previous post we handled multiple incoming edges by having our iteration loop exist inside of an enclosing loop that made sure we tried all branches. Here we’re seeing only the inner loop that begins at the given start vertex and traverses until it hits a dead-end or a cycle. The hare takes 2 steps for each single tortoise step so they will land together on the same vertex only if they’re in a cycle. Using the example in Figure 1, and looking at the index numbers of the vertices, the steps progress like this:

	Tortoise		0		Hare		0		Starting line
	Tortoise		1		Hare		2
	Tortoise		2		Hare		4
	Tortoise		3		Hare		6
	Tortoise		4		Hare		8
	Tortoise		5		Hare		10
	Tortoise		6		Hare		12		6 and 12 are the same vertex – “G”

The tortoise has moved ahead 6 vertices and the hare has moved 12 and they met on the “G” vertex so we know there’s a cycle. Now we may want to get some other values too like the length of the sequence before the cycle (the tail length), and the length of the cycle itself.

Tail Length

We can get the tail length by starting one pointer at the beginning and starting the tortoise where we left it and having each advance one step at a time until they meet. They will always meet at the vertex where the tail ends and the cycle begins.

	Tail Pointer		0		Tortoise		6		Starting line
	Tail Pointer		1		Tortoise		7
	Tail Pointer		2		Tortoise		8
	Tail Pointer		3		Tortoise		9
	Tail Pointer		4		Tortoise		10		Same vertex – “E”

Now we know “E” is the start of the cycle and if we’ve kept count we know that the tail is 4 edges long.

Cycle Length

To calculate the cycle length we can get the total graph length from vertex zero, around the cycle once and then subtract the tail length. When we ran the “tail length” step above, the tortoise ended up at the cycle start vertex but its index doesn’t give us the correct total graph length because it may have been around the loop more than once. So first start the tortoise back where it met the hare at vertex “G” (index 6) and advance until we reach the cycle start while noting the count. The tortoise begins on index 6, moves ahead one to “E” for a total graph length of 7 steps. Then we just subtract the tail length of 4 which gives us the cycle length, 3.

Complete Implementation

/** Use Floyd’s algorithm, “tortoise and hare”, to find a cycle.

* Searches for a cycle in a single branch of a functional graph

* beginning at a given vertex. Outputs if cycle found, tail

* length, cycle start vertex, cycle length

*/

public static void findCycleInfo(Set vertices, Vertex startVertex){

   boolean cycleFound = false;

   int meetIndex = 0;

   Vertex meetVertex = null;

   int tailLength = 0;

   Vertex cycleStartVertex = null;

   int cycleLength = 0;

   /*

   *Determine if a cycle exists. Start at given Vertex

   */

   Vertex tortoise = startVertex;   //vertex “0”

   Vertex hare = startVertex;       //vertex “0”

   while (true){

      if (hare.outEdge() == null){

         System.out.println(“No cycle”);

         break;

      }else hare = hare.outEdge().dest();   //Advance hare a step

      if (hare.outEdge() == null){

         System.out.println(“No cycle”);

         break;

      }else hare = hare.outEdge().dest();   //Advance hare a second step

      tortoise = tortoise.outEdge().dest(); //Advance tortoise one step

      meetIndex += 1;

      if (tortoise == hare){                //Compare identity

         cycleFound = true;

         System.out.println(“Cycle found”);

         meetVertex = hare;

         break;

      }

   }

   /*

   *Find the tail length

   */

   if (cycleFound){

      Vertex tailPointer = startVertex;

      while (true){

         if (tailPointer == tortoise){      //Compare identity

            cycleStartVertex = tortoise;

            System.out.println(“Tail length is: ” + tailLength);

            System.out.println(“Cycle start Vertex is: ” + cycleStartVertex.name());

            break;

         }

         tailPointer = tailPointer.outEdge().dest(); //Advance tailCounter one step

         tortoise = tortoise.outEdge().dest();       //Advance tortoise one step

         tailLength += 1;

      }

   }

   /*

   *Find the cycle length

   */

   if (cycleFound){

      tortoise = meetVertex;

      int indx = meetIndex;

      while (true){

         if (tortoise == cycleStartVertex){ //Compare identity

            cycleLength = indx – tailLength;

            System.out.println(“Cycle length is: ” + cycleLength);

            break;

         }

         tortoise = tortoise.outEdge().dest();       //Advance tortoise one step

         indx += 1;

      }

   }

}

Test

A test that passes in the Vertices from Figure 1, and Vertex “A” as the starting point will print the following results:

Cycle found
Tail length is: 4
Cycle start Vertex is: E
Cycle length is: 3