MATLAB Central Newsreader - bug with graphallshortestpaths?

bug with graphallshortestpaths?

Petros — Thu, 19 Feb 2009 09:58:01 -0500

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

Re: bug with graphallshortestpaths?

Lucio Andrade-Cetto — Thu, 19 Feb 2009 14:30:20 -0500

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

Re: bug with graphallshortestpaths?

Petros — Thu, 19 Feb 2009 16:39:01 -0500

> 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

Re: bug with graphallshortestpaths?

Lucio Andrade-Cetto — Thu, 19 Feb 2009 16:51:02 -0500

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

Re: bug with graphallshortestpaths?

Lucio Andrade-Cetto — Fri, 20 Feb 2009 19:14:01 -0500

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