MATLAB function graphallshortestpaths not returning symmetric matrix

Question

I am using the MATLAB function graphallshortestpaths to compute shortest paths between vertices of an undirected network. The undirected network is given as a weighted edge list file, which you can find here.

This is the MATLAB code that I use to compute the shortest paths:

A=load('genome_edge_list');

%Extract the edges
E=[A(:,1);A(:,2)]; 

%Extract the vertices
V=unique(E); 

%N is the number of vertices
N=length(V); 

%Take the inverse of the weights
A(:,3)=1./A(:,3);

%Create a sparse weighted adjacency matrix
B=sparse(A(:,1),A(:,2),A(:,3),N,N);

%Make B symmetric
B=sparse(full(B)+full(B)');

%Compute shortest paths
D=graphallshortestpaths(B,'directed',false);

Now, the matrix D that MATLAB gives as output is not symmetric. However, since the input to graphallshortestpaths is a symmetric matrix in sparse format, the output ought to be a symmetric matrix. So what am I doing wrong?

The only related question that I could find on mathworks is this question, however in that question the OP clearly is not giving a symmetric matrix as input, which explains why the matrix returned by MATLAB is not symmetric.

EDIT:

To see how far off D and D' are, I computed the following:

E=D';
C=D==E;
find(C==0)

this returns the following linear indices:

but the values of D and E at those indices are the same, e.g. D(33133)= 0.1024=E(33133). Now, if I take the difference of the two matrices, then I find that the difference at those indices is -1.0000e-05. It therefore seems to be a rounding error, as @beaker points out. However, as I write in my comment below, I don't understand how this can occur, as graphsallshortestpaths computes the distance between node i and j only once, so the values of D(i,j) and D(i,j) should be the result of the same computation.

How far are the values off by? The only thing I can think of is floating point precision. Also, I think the third line should be V=unique(E); since H is undefined, but I can't see how that could cause the problem even if H was already defined elsewhere. — beaker
@beaker thanks, that was a typo. I checked how far the values are off with C=D==D.' and find(C==0) gives me a list of six indices for which D and D.' should be different. However, the values for those indices are the same, so I am baffled as to why issymmetric(D) returns 0. — n.o.
@beaker, I checked again by computing the difference of the two matrices, and at those six indices they have a difference of -1.0000e-05. So this seems to be a rounding problem. However, I can't see where it occurs, as the distance between node i and node j should be computed only once by graphsallshortestpaths, so the value at D(j,i) should be the same as the value at D(i,j). — n.o.

titus.andronicus titus.andronicus · Accepted Answer · 2017-05-02T06:56:49

Couple or remarks:

As @beaker mentioned in the comment, it could well be a numerical issue. I would be particularly weary of the line where you take the inverse and do A(:,3)=1./A(:,3);. Try to output some debug values and see if this inverse does what you intended.
On the line where you make B symmetric: are you sure you want to do full(b)' and not full(b).'? The first one takes the hermitian, the second the transpose!
Also on the same line where you make B symmetric: perhaps you are missing a 0.5 factor in there? So instead of B=sparse(full(B)+full(B)'); something like B=sparse((full(B)+full(B).').*0.5); (see this answer).

I also think you unintentionally wrote H instead of E on the second line, right?

MATLAB function graphallshortestpaths not returning symmetric matrix

1 Answers