Thread Subject:

problem about graphshortestpath()

HI,
I would like to calculate the shortest path of a single origin and destination in a graph.

My code and error inforamtion are below.
I think DG is already a sparse matrix. I do not know why I got an error information "Sparse array should have same number of rows and columns" when I ran the command "[dist,path,pred] = graphshortestpath(DG,1,5)".
Could you please give me some suggestion if anyone have this experience?
Thanks a lot.

//-------------------my code and error information--------------------------------//
DG =

   (1,2) 40.0353
   (2,3) 10.2607
   (1,4) 53.6700
   (2,4) 71.4801
   (2,5) 61.3451
   (3,5) 93.5625

K>> [dist,path,pred] = graphshortestpath(DG,1,5)
??? Error using ==> graphalgs
Sparse array should have same number of rows and columns.

Error in ==> graphshortestpath at 136
        [dist,pred] = graphalgs(algorithmkeys{algorithm},debug_level,directed,G,S);

"dhuan Du" <dupeony@gmail.com> wrote in message <gprnm1$rid$1@fred.mathworks.com>...
> HI,
> I would like to calculate the shortest path of a single origin and destination in a graph.
>
> My code and error inforamtion are below.
> I think DG is already a sparse matrix. I do not know why I got an error information "Sparse array should have same number of rows and columns" when I ran the command "[dist,path,pred] = graphshortestpath(DG,1,5)".
> Could you please give me some suggestion if anyone have this experience?
> Thanks a lot.
>
> //-------------------my code and error information--------------------------------//
> DG =
>
> (1,2) 40.0353
> (2,3) 10.2607
> (1,4) 53.6700
> (2,4) 71.4801
> (2,5) 61.3451
> (3,5) 93.5625
>
> K>> [dist,path,pred] = graphshortestpath(DG,1,5)
> ??? Error using ==> graphalgs
> Sparse array should have same number of rows and columns.
>
> Error in ==> graphshortestpath at 136
> [dist,pred] = graphalgs(algorithmkeys{algorithm},debug_level,directed,G,S);

  The function 'graphshortestpath' expects a square matrix, and you have given it only the upper half, so you will have to fill in or at least extend to a full 5 x 5 matrix before making the call.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gprp12$1ta$1@fred.mathworks.com>...
> The function 'graphshortestpath' expects a square matrix, and you have given it only the upper half, so you will have to fill in or at least extend to a full 5 x 5 matrix before making the call.
>
> Roger Stafford

  To enlarge upon what I said above, when you create a sparse matrix, it is possible to force a square size on it even though the area it is defined in is not square. For example

 A = sparse([1 2 1],[1 2 3],1);

will have size(A) = [2,3], whereas

 B = sparse([1 2 1],[1 2 3],1,3,3);

gives size(B) = [3,3], even though the non-zero portions of A and B are identical.

Roger Stafford

Thanks a lot Roger Stafford. I did not really understand your suggestions. The matrix, DG just gave the all link inforamtion about my graph. How can I change it to a square matrix without change the link connection information of my graph?

Thanks,

Dhuan


"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gprp12$1ta$1@fred.mathworks.com>...
> "dhuan Du" <dupeony@gmail.com> wrote in message <gprnm1$rid$1@fred.mathworks.com>...
> > HI,
> > I would like to calculate the shortest path of a single origin and destination in a graph.
> >
> > My code and error inforamtion are below.
> > I think DG is already a sparse matrix. I do not know why I got an error information "Sparse array should have same number of rows and columns" when I ran the command "[dist,path,pred] = graphshortestpath(DG,1,5)".
> > Could you please give me some suggestion if anyone have this experience?
> > Thanks a lot.
> >
> > //-------------------my code and error information--------------------------------//
> > DG =
> >
> > (1,2) 40.0353
> > (2,3) 10.2607
> > (1,4) 53.6700
> > (2,4) 71.4801
> > (2,5) 61.3451
> > (3,5) 93.5625
> >
> > K>> [dist,path,pred] = graphshortestpath(DG,1,5)
> > ??? Error using ==> graphalgs
> > Sparse array should have same number of rows and columns.
> >
> > Error in ==> graphshortestpath at 136
> > [dist,pred] = graphalgs(algorithmkeys{algorithm},debug_level,directed,G,S);
>
> The function 'graphshortestpath' expects a square matrix, and you have given it only the upper half, so you will have to fill in or at least extend to a full 5 x 5 matrix before making the call.
>
> Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gprqjn$fki$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gprp12$1ta$1@fred.mathworks.com>...
> > The function 'graphshortestpath' expects a square matrix, and you have given it only the upper half, so you will have to fill in or at least extend to a full 5 x 5 matrix before making the call.
> >
> > Roger Stafford
>
> To enlarge upon what I said above, when you create a sparse matrix, it is possible to force a square size on it even though the area it is defined in is not square. For example
>
> A = sparse([1 2 1],[1 2 3],1);
>
> will have size(A) = [2,3], whereas
>
> B = sparse([1 2 1],[1 2 3],1,3,3);
>
> gives size(B) = [3,3], even though the non-zero portions of A and B are identical.
>
> Roger Stafford



Hi. Roger Stafford:

Thanks again for your help. Based on your suggestion, do A and B represent the same graph?

Hi, Roger Stafford:

In A = sparse([1 2 1],[1 2 3],1), what the "1" represents after the two vector?

The similar question, in B = sparse([1 2 1],[1 2 3],1,3,3), what the "1, 3, 3" represents repectivley?

Thanks again!

Dhuan

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gprqjn$fki$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gprp12$1ta$1@fred.mathworks.com>...
> > The function 'graphshortestpath' expects a square matrix, and you have given it only the upper half, so you will have to fill in or at least extend to a full 5 x 5 matrix before making the call.
> >
> > Roger Stafford
>
> To enlarge upon what I said above, when you create a sparse matrix, it is possible to force a square size on it even though the area it is defined in is not square. For example
>
> A = sparse([1 2 1],[1 2 3],1);
>
> will have size(A) = [2,3], whereas
>
> B = sparse([1 2 1],[1 2 3],1,3,3);
>
> gives size(B) = [3,3], even though the non-zero portions of A and B are identical.
>
> Roger Stafford

"dhuan Du" <dupeony@gmail.com> wrote in message <gptme1$cj6$1@fred.mathworks.com>...
> ......
> In A = sparse([1 2 1],[1 2 3],1), what the "1" represents after the two vector?
> The similar question, in B = sparse([1 2 1],[1 2 3],1,3,3), what the "1, 3, 3" represents repectivley?

  Dhuan, you really should become accustomed to reading the documentation or help files for the functions you use. You can't get very far in the use of Matlab without doing this. (Confession: Sometimes I am guilty of the same failing.)

  In the case of the 'sparse' function, its third argument determines what quantities are to be placed in the sparse matrix. It is either a vector the same length as the first two arguments or a scalar which is to be repeated as many times as that length. In the example I gave it is the scalar 1 repeated three times.

  The additional 3,3 at the fourth and fifth arguments force the sparse matrix to have at least a size 3 in each dimension. That is what is needed to produce a square 3 x 3 matrix even if the bottom row is all zeros. Doing this kind of thing is what is necessary to present 'graphshortestpath' with a square matrix in your example even though your bottom two rows would be all zeros.

  Earlier you asked "How can I change it to a square matrix without change the link connection information of my graph?" The best way of course is to make appropriate use of the fourth and fifth arguments when you create the sparse matrix for the first time. However, if you have already created a sparse matrix A and want to enlarge it without making any changes to its non-zero portions, you can always do this:

 (I,J,S] = find(A);
 B = sparse(I,J,S,m,n);

which forces the creation of a copy of A which is at least a size of m x n even though some of its last rows or columns have may have no non-zero elements in them.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gptt1t$nvc$1@fred.mathworks.com>...
> "dhuan Du" <dupeony@gmail.com> wrote in message <gptme1$cj6$1@fred.mathworks.com>...
> > ......
> > In A = sparse([1 2 1],[1 2 3],1), what the "1" represents after the two vector?
> > The similar question, in B = sparse([1 2 1],[1 2 3],1,3,3), what the "1, 3, 3" represents repectivley?
>
> Dhuan, you really should become accustomed to reading the documentation or help files for the functions you use. You can't get very far in the use of Matlab without doing this. (Confession: Sometimes I am guilty of the same failing.)
>
> In the case of the 'sparse' function, its third argument determines what quantities are to be placed in the sparse matrix. It is either a vector the same length as the first two arguments or a scalar which is to be repeated as many times as that length. In the example I gave it is the scalar 1 repeated three times.
>
> The additional 3,3 at the fourth and fifth arguments force the sparse matrix to have at least a size 3 in each dimension. That is what is needed to produce a square 3 x 3 matrix even if the bottom row is all zeros. Doing this kind of thing is what is necessary to present 'graphshortestpath' with a square matrix in your example even though your bottom two rows would be all zeros.
>
> Earlier you asked "How can I change it to a square matrix without change the link connection information of my graph?" The best way of course is to make appropriate use of the fourth and fifth arguments when you create the sparse matrix for the first time. However, if you have already created a sparse matrix A and want to enlarge it without making any changes to its non-zero portions, you can always do this:
>
> (I,J,S] = find(A);
> B = sparse(I,J,S,m,n);
>
> which forces the creation of a copy of A which is at least a size of m x n even though some of its last rows or columns have may have no non-zero elements in them.
>
> Roger Stafford

Dear Mr.Roger
can i have ur private email??because i want to send my programmed..i have a problem in my matlab programme..i dont know how to solve it.. thank you