8.5 DETECTING CYCLES IN THE ALGORITHM

This section explains how cycles could be detected in the algorithm using the adjacency matrix A. Let us assume we modify the cycle-free algorithm in Fig. 8.1 to have an algorithm with a cycle in it like the one shown in Fig. 8.3. The dashed arrows indicate the extra links we added. Inspecting the figure indicates we have a cycle, 3 → 7 → 5 → 8 → 3.

Figure 8.3 Modifying the algorithm of Fig. 8.1 to contain a cycle as indicated by the dashed arrows.

The corresponding adjacency matrix is given by

(8.8)

An inspection of the matrix would not reveal the presence of any cycle. In fact, nothing too interesting happens for powers of B² and B³. However, for B⁴, the matrix takes on a very interesting form:

(8.9)

We note that there are four nonzero diagonal elements: b₄ (3, 3), b₄ (5, 5), b₄ (7, 7), and b₄ (8, 8). This indicates that there is a four-hop loop between nodes 3, 5, 7, and 8. The order of the loop can be determined by examining the rows associated with these nodes. Starting with node 3, we see that it depends on node 8. So, the path of the loop is 8 → 3. Now we look at row 8 and see that it depends on node 5. So, the path of the loop is 5 → 8 → 3. Continuing in this fashion, we see that our loop is 3 → 7 → 5 → 8 → 3, which we have found by inspection of the graph. The advantage of this technique is that it is applicable to any number of nodes and can be automated.

Another interesting property of cyclic algorithms and cyclic graphs is that higher powers of the adjacency matrix will not produce a zero matrix. In fact, the adjacency matrix will show cyclic or periodic behavior:

(8.10)