# Cycle Detection in a Directed Acyclic Graph

Given a directed graph represented by the matrix:

$$g = \begin{matrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{matrix}$$

With vertices of:

$$\{0 , 1\}, \{1 , 2\}, \{2 , 3\}, \{3, 1\}$$

I have followed the logic from this article and found that the graph is cyclic based off of the cube of the original matrix having non zero entries along the diagonal:

$$g^2 = \begin{matrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}$$

$$g^3 = \begin{matrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}$$

It is obvious to me that the cycle is created with the edges: $$\ \{1 , 2\}, \{2 , 3\}, \{3, 1\}$$

Which form the cycle $$\{1 ,2 ,3 ,1\}$$

I am trying to figure out if there is an algorithmic way of determining which vertices caused the cycle.

For a little context:

I am working on an application that will use a directed acyclic graph to coordinate a series of processing algorithms on a set of data where the ordering of the processing must be acyclic, and can be modified during the course of the programs execution.

Because of the fact that the vertices will be changed dynamically I need the ability to ensure that the graph is acyclic before it is processed and if a cycle is introduced somehow the ability to determine the cycle so that it can be corrected.

My mathematical skills are not very strong so I am not sure where to start trying to solve this.

• I edited the example, I should hopefully have correct matrix math now – Alex Zywicki Oct 26 '16 at 14:49

Let me expand a little bit on the "powers of the adjacency matrix" method. Let $A^k_{i,j}$ be the $i,j$ entry of the $k$th power of the adjacency matrix $A$. Then $A^k_{i,j}$ is the number of walks from $i$ to $j$ - this can be easily shown using induction on $k$. In fact, this holds for both directed and undirected graphs. You're right that there is no way to recover the vertices in the cycle. As Alex mentioned, this method takes a long time because matrix multiplication takes about $O(n^3)$ time and so checking for $k$ length cycles would take $O(kn^3)$. So while the results about walks using powers of the adjacency matrix is interesting, I don't know of many practical algorithms that use this fact. I think this result is mainly used in spectral graph theory, where you can relate the number of closed walks in an undirected graph to its eigenvalues.