Thread Subject: bug with graphallshortestpaths?

I think there is a bug with graphallshortestpaths function. Here is an example with the problem.
clear
load A.mat
% A.mat incudes only one sparce double 357x357 matrix called "A"


[DIST1] = graphallshortestpaths(A,'directed',false);
% DIST1 includes unreached points (indicated with "Inf" )
%this is the wrong behavior


A2=A./1000;
% I produce A2 with lower weith values.

[DIST2] = graphallshortestpaths(A2,'directed',false);
% DIST2 does not include unreached points (indicated with "Inf"), just
%because the A matrix has lower weight values
%this is the normal behavior


Any help is welcome

below I post a link someone can download the example above as good as the A.mat in order to try it.

http://users.auth.gr/~painter/bug/bug_example.zip




MATLAB/PLATFORM INFO
Release: R2008b
Product: Bioinformatics Toolbox
Product Version: 3.2
Operating System: Windows Vista

Petros:

This looks like a genuine bug, it can easily be reproducible with:
graphashortestpath(sparse([1 2 2 3 4],[2 3 4 5 5],[100 97.362401 97.362400 100 100],5,5),1)

Apparantly when the Jonhson's alg accumulates more than 197.3624 is marks the path as unreacheable.

A possible workaround is either scale the weigth of the edges as you did it or use a loop with graphshortestpath.

Lucio

> Apparantly when the Jonhson's alg accumulates more than 197.3624 is marks the path as unreacheable.
>
> A possible workaround is either scale the weigth of the edges as you did it or use a loop with graphshortestpath.
>
> Lucio


Yeap, that's it Lucio, thank you for the immediate response! I hope Mathworks to fix the problem with an update of graphallshortestpaths function. I am afraid that scaling the weights is going to effect the accuracy. The loop option is not applicable for computation efficency reasons... : - S

We do have a fix now, I will post it later today in our customer support site.
Lucio

"Petros" <painter@geo.auth.gr> wrote in message <gnk1v5$5s7$1@fred.mathworks.com>...
>
> > Apparantly when the Jonhson's alg accumulates more than 197.3624 is marks the path as unreacheable.
> >
> > A possible workaround is either scale the weigth of the edges as you did it or use a loop with graphshortestpath.
> >
> > Lucio
>
>
> Yeap, that's it Lucio, thank you for the immediate response! I hope Mathworks to fix the problem with an update of graphallshortestpaths function. I am afraid that scaling the weights is going to effect the accuracy. The loop option is not applicable for computation efficency reasons... : - S

There is a fix now available at:
http://www.mathworks.com/support/bugreports/details.html?rp=525696

Lucio

"Lucio Andrade-Cetto" <lcetto@nospam.mathworks.com> wrote in message <gnk2lm$ml7$1@fred.mathworks.com>...
> We do have a fix now, I will post it later today in our customer support site.
> Lucio
>
> "Petros" <painter@geo.auth.gr> wrote in message <gnk1v5$5s7$1@fred.mathworks.com>...
> >
> > > Apparantly when the Jonhson's alg accumulates more than 197.3624 is marks the path as unreacheable.
> > >
> > > A possible workaround is either scale the weigth of the edges as you did it or use a loop with graphshortestpath.
> > >
> > > Lucio
> >
> >
> > Yeap, that's it Lucio, thank you for the immediate response! I hope Mathworks to fix the problem with an update of graphallshortestpaths function. I am afraid that scaling the weights is going to effect the accuracy. The loop option is not applicable for computation efficency reasons... : - S