Results 1 to 6 of 6

Math Help - MATLAB finding graph

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    29

    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
    Last edited by mr fantastic; December 5th 2009 at 11:47 AM. Reason: Restored deleted question
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by htata123 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    29
    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.
    Last edited by mr fantastic; December 5th 2009 at 11:48 AM. Reason: Restored deleted reply
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by htata123 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2009
    Posts
    29
    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
    Last edited by mr fantastic; December 5th 2009 at 11:51 AM. Reason: Restored deleted reply
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2009
    Posts
    29
    hey i just figured the code out. it works well thanks for your help
    Last edited by mr fantastic; December 5th 2009 at 11:50 AM. Reason: Restored deleted reply
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Smooth graph matlab
    Posted in the Math Software Forum
    Replies: 4
    Last Post: November 15th 2010, 11:05 AM
  2. Matlab making a newtork graph
    Posted in the Math Software Forum
    Replies: 4
    Last Post: November 4th 2010, 03:59 AM
  3. matlab plotting graph need help
    Posted in the Math Software Forum
    Replies: 1
    Last Post: August 6th 2010, 11:27 PM
  4. Plot a semi log graph using matlab
    Posted in the Math Software Forum
    Replies: 1
    Last Post: May 31st 2010, 08:28 PM
  5. plotting a graph in matlab
    Posted in the Math Software Forum
    Replies: 3
    Last Post: March 21st 2009, 02:11 PM

Search Tags


/mathhelpforum @mathhelpforum