Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
bug with graphallshortestpaths?

Subject: bug with graphallshortestpaths?

From: Petros

Date: 19 Feb, 2009 09:58:01

Message: 1 of 5

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

Subject: bug with graphallshortestpaths?

From: Lucio Andrade-Cetto

Date: 19 Feb, 2009 14:30:20

Message: 2 of 5

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

Subject: bug with graphallshortestpaths?

From: Petros

Date: 19 Feb, 2009 16:39:01

Message: 3 of 5


> 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

Subject: bug with graphallshortestpaths?

From: Lucio Andrade-Cetto

Date: 19 Feb, 2009 16:51:02

Message: 4 of 5

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

Subject: bug with graphallshortestpaths?

From: Lucio Andrade-Cetto

Date: 20 Feb, 2009 19:14:01

Message: 5 of 5

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

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us