[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[igraph] problem with shortest paths with weights

From: Ju-Sung Lee
Subject: [igraph] problem with shortest paths with weights
Date: Tue, 29 Apr 2014 13:36:43 -0700 (PDT)

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.  (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?


reply via email to

[Prev in Thread] Current Thread [Next in Thread]