Re: [igraph] problem with shortest paths with weights

[Gábor Csárdi]

On Tue, Apr 29, 2014 at 4:36 PM, Ju-Sung Lee <address@hidden> 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
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help