# MATLAB finding graph

• Dec 4th 2009, 06:51 AM
htata123
MATLAB finding graph
im writing a code to find the length of the shortest cycle in a graph. We need to use an n*n adjacency matrix for this and we evaluate A^k and the value for k at which the diagonal of A^k has at least one non-zero entry is the length of the shortest graph. I have a code for this but at this point, it spits out all values and not the smallest value of k only, my code;

Quote:

Code:
function sma(A)
[n,n] = size(A);
for k = 1:n;
P = A^k;
for k = 1:n;
if diag(A^k) == diag(zeros(n));
disp('no cycles for this graph exist');
else disp(min(k));
end
end
end
thanks for any help
• Dec 4th 2009, 09:58 AM
CaptainBlack
Quote:

Originally Posted by htata123
hi,

im writing a code to find the length of the shortest cycle in a graph. We need to use an n*n adjacency matrix for this and we evaluate A^k and the value for k at which the diagonal of A^k has at least one non-zero entry is the length of the shortest graph. I have a code for this but at this point, it spits out all values and not the smallest value of k only; my code;
Code:

```function sma(A) [n,n] = size(A); for k = 1:n;     P = A^k;     for k = 1:n;      if diag(A^k) == diag(zeros(n));           disp('no cycles for this graph exist');       else disp(min(k));       end     end end```
thanks for any help

Start by writing a description (in pseudo-code if you know what that is) of the algorithm you intend to implement.

Also have you run the code you posted? Were there any error messages?

CB
• Dec 4th 2009, 10:39 AM
htata123
I ran the code and it seems to display all values of K, not the minimum. So the algorithm I'm trying to implement is like this;

for all values of k from 1 to n (size of square matrix),

compute A^k.

Now in the new set of matrices A^k, I need to find the smallest k such that A^k does not have a zero diagonal. So what I did for that was I compared the diagonal for each A^k with the diagonal of the zero matrix. If that was equal then that value of k is not valid. The code does that. The output when I ran the code is like 1, 2, 3, 4, 5 which is fine, but I only need it to display 1. If there are no such values of K, i.e. all powers of A^k have zero diagonals then it should display no graphs exist.
• Dec 5th 2009, 12:22 AM
CaptainBlack
Quote:

Originally Posted by htata123
I ran the code and it seems to display all values of K, not the minimum. So the algorithm I'm trying to implement is like this;

for all values of k from 1 to n (size of square matrix),

compute A^k.

Now in the new set of matrices A^k, I need to find the smallest k such that A^k does not have a zero diagonal. So what I did for that was I compared the diagonal for each A^k with the diagonal of the zero matrix. If that was equal then that value of k is not valid. The code does that. The output when I ran the code is like 1, 2, 3, 4, 5 which is fine, but I only need it to display 1. If there are no such values of K, i.e. all powers of A^k have zero diagonals then it should display no graphs exist.

Try this:

Code:

```function sma(A)   [n,n] = size(A);   for k = 1:n;       P = A^k;       for k = 1:n;        if diag(A^k) == diag(zeros(n));         disp('no cycles for this graph exist');       else         k         break       end   end end```
CB
• Dec 5th 2009, 07:40 AM
htata123
the code you gave me definitely gives me the minimum value but it also gives me an output like this;

K =

0 1 1 1
1 0 1 1
1 0 0 1
0 0 1 0

>> proj6(K)
the minimum cycle length of this graph is;
cycles for this graph do not exist

k =

2

the minimum cycle length of this graph is;
cycles for this graph do not exist

k =

2

the minimum cycle length of this graph is;
cycles for this graph do not exist

k =

2

the minimum cycle length of this graph is;
cycles for this graph do not exist

k =

2

i know the cycle doesn't exist for k=1, but it exists for k=2, so it should not be providing the output above. It also repeats itself four times
• Dec 5th 2009, 08:42 AM
htata123
hey i just figured the code out. it works well thanks for your help