Thread: 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;

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

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

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.

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

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

hey i just figured the code out. it works well thanks for your help