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.
Best Answer
Alex has given many links that mention either the use of Depth First Search or Tarjan's algorithm. Since you mentioned that you are working on your algorithmic and mathematical skills, I suggest you look into Depth First Search (DFS) as a way of detecting cycles in directed (or undirected) graphs. Not only will the algorithm detect a cycle, but it will also return all the vertices in the cycle. Note that DFS will be able to detect a cycle but DFS alone won't tell you the best way to "re-route" your graph to make it acyclic. I suppose this depends more on your application. However, there is a large literature on job scheduling so you might be able to find an answer to your problem there.
A lot of common problems can be solved using DFS so it's a good to have in your algorithmic toolbox. Once you understand how it works, you'll be able to solve many more problems. In general, DFS may not be the fastest solution, but it's a very good start.
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.