
From:  Gábor Csárdi 
Subject:  Re: [igraph] problem with shortest paths with weights 
Date:  Wed, 30 Apr 2014 10:17:55 0400 
The following problem occurs in igraph 0.7.1 for R. I believe there's a problem with shortest paths computations (e.g., get.all.shortest.paths) due to imprecise comparison of double types in the C code (e.g., many instances of "else if (altdist < curdist)" in structural_properties.c). Problems occur if one's graph contains edge weights like 1/3 (or 0.3333...) and if three of those are added, their result is not quite 1.0. Should not the "less than" test be something akin to "if (curdist  altdist > epsilon)" where epsilon is say 1e8.
(BTW, I read that Knuth suggests a variant that is dependent on the magnitude of the one of curdist or altdist values). Are there float/double comparisons in any other places in igraph that might be affected?
Jay
_______________________________________________
igraphhelp mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraphhelp
[Prev in Thread]  Current Thread  [Next in Thread] 