On Tue, Apr 29, 2014 at 4:36 PM, Ju-Sung Lee <[email protected]> wrote:
> 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 1e-8. > Is this a question? I guess you also want a fabs() here, or rather altdist < curdist - epsilon. Anyway, I think there is an argument for the epsilon comparison, and also one for the current behavior. Because the errors can accumulate (e.g. when you sum up edge weights along the paths), it is sometimes hard to work out what exactly epsilon should be. We would need to work it out for every algorithm. In the shortest paths case it is not that hard, actually. Maybe just using sqrt(epsilon), where epsilon is the machine eps, would work in practice and would be definitely a big step forward. > (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? > Yes, plenty. Gabor > > Jay > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help > >
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
