Detecting cycles in an adjacency matrix

Question

Let A be the adjacency matrix for the graph G = (V,E). A(i,j) = 1 if the nodes i and j are connected with an edge, A(i,j) = 0 otherwise.

My objective is the one of understanding whether G is acyclic or not. A cycle is defined in the following way:

• i and j are connected: A(i,j) = 1
• j and k are connected: A(j,k) = 1
• k and i are connected: A(k,i) = 1

I have implemented a solution which navigates the matrix as follows:

• Start from an edge (i,j)
• Select the set O of edges which are outgoing from j, i.e., all the 1s in the j-th row of A
• Navigate O in a DFS fashion
• If one of the paths generated from this navigation leads to the node i, then a cycle is detected

Obviously this solution is very slow, since I have to evaluate all the paths in the matrix. If A is very big, the required overhead is very huge. I was wondering whether there is a way of navigating the adjacency matrix so as to find cycles without using an expensive algorithm such as DFS.

I would like to implement my solution in MATLAB.

Thanks in advance,

Eleanore.

Answer 1

Based on the observation of Danil, you need to compute A^n, a slightly more efficient way of doing so is

n = size(A,1);
An = A; 
for ii = 2:n
     An = An * A; % do not re-compute A^n from skratch
     if trace(An) ~= 0
        fprintf(1, 'got cycles\n');
     end
end

Answer 2

If digraph G is represented by its Adjacency matrix M then M'=(I - M ) will be singular if there is a cycle in it. I : identity matrix of same order of M

Answer 3

If A is the adjacency matrix of the directed or undirected graph G, then the matrix A^n (i.e., the matrix product of n copies of A) has following property: the entry in row i and column j gives the number of (directed or undirected) walks of length n from vertex i to vertex j.

E.g. if for some integer n matrix A^n contain at least one non-zero diagonal entry, than graph has cycle of size n.

Most easy way check for non-zero diagonal elements of matrix is calculate matrix trace(A) = sum(diag(A)) (in our case elements of matrix power will be always non-negative).

Matlab solution can be following:

for n=2:size(A,1)
   if trace(A^n) ~= 0
      fprintf('Graph contain cycle of size %d', n)
      break;
   end
end

Answer 4

That is the problem I also found. The explanation, I thought, is the following:
when we talk about cycle, implicitly we mean directed cycles. The adjacency matrix that you have has a different meaning when you consider the directed graph; it is indeed a directed cycle of length 2. So, the solution of $A^n$ is actually for directed graphs. For undirected graphs, I guess a fix would be to just consider the upper triangular version of the matrix (the rest filled with zero) and repeat the procedure. Let me know if this is the right answer.

Answer 5

Some more thoughts on the matrix approach... The example cited is the adjacency matrix for a disconnected graph (nodes 1&2 are connected, and nodes 3&4 are connected, but neither pair is connected to the other pair). When you calculate A^2, the answer (as stated) is the identity matrix. However, since Trace(A^2) = 4, this indicates that there are 2 loops each of length 2 (which is correct). Calculating A^3 is not permitted until these loops are properly identified and removed from the matrix. This is an involved procedure requiring several steps and is detailed nicely by R.L. Norman, "A Matrix Method for Location of Cycles of a Directed Graph," AIChE J, 11-3 (1965) pp. 450-452. Please note: it is unclear from the author whether this approach is guaranteed to find ALL cycles, UNIQUE cycles, and/or ELEMENTARY cycles. My experience suggests that it definitely does not identify ONLY unique cycles.

Answer 6

I came across this question when answering this math.stackexchange question. For future readers, I feel like I need to point out (as others have already) that Danil Asotsky's answer is incorrect, and provide an alternative approach. The theorem Danil is referring to is that the (i,j) entry of A^k counts the number of walks of length k from i to j in G. The key thing here is that a walk is allowed to repeat vertices. So even if a diagonal entries of A^k is positive, each walk the entry is counting may contain repeated vertices, and so wouldn't count as a cycle.

Counterexample: A path of length 4 would contain a 4-cycle according to Danil's answer (not to mention that the answer would imply P=NP because it would solve the Hamilton cycle problem).

Anyways, here is another approach. A graph is acyclic if and only if it is a forest, i.e., it has c components and exactly n-c edges, where n is the number of vertices. Fortunately, there is a way to calculate the number of components using the Laplacian matrix L, which is obtained by replacing the (i,i) entry of -A with the sum of entries in row i of A (i.e., the degree of vertex labeled i). Then it is known that the number of components of G is n-rank(L) (i.e., the multiplicity of 0 as an eigenvalue of L).

So G has a cycle if and only if the number of edges is at least n-(n-rank(L))+1. On the other hand, by the handshaking lemma, the number of edges is exactly half of trace(L). So:

G is acyclic if and only if 0.5*trace(L)=rank(L). Equivalently, G has a cycle if and only if 0.5*trace(L) >= rank(L)+1.