[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [igraph] Bug in igraph_get_shortest_paths_dijkstra for small edge weight

**From**: |
Reed, Martin J |

**Subject**: |
[igraph] Bug in igraph_get_shortest_paths_dijkstra for small edge weights |

**Date**: |
Mon, 6 Aug 2012 23:43:54 +0000 |

Hi,
I have found a bug in igraph_get_shortest_paths_dijkstra() from
structural_properties.c (and thus also the other Dijkstra implementations in
the same file). The bug is only serious for small values in the weights vector.
The problem is caused by using zero to signify infinity and thus using 1.0 to
actually signify zero. In part of the implementation there are lines like:
VECTOR(dists)[tto] = altdist+1.0;
(and other points where 1.0 is added or taken away).
If the distances are small (very small compared to 1.0) this causes significant
error. In my case I was porting a Max flow algorithm I had previously written
using the Boost graph library that starts with VERY small edge weights so that
altdist + 1.0 == 1.0
due to numerical precision limits.
The affect of this in my case was either a continual loop later in the
igraph_get_shortest_paths_dijkstra() or in the same function, a crash with
"EXC_BAD_ACCESS, Could not access memory".
I would like to propose a solution that I would like others to test, see my
diff (against most recent nightly build). Essentially I have fixed -1 as
infinity and left the "dists" vector elements at zero to mean zero (as Dijkstra
intended!). I do not see any problem with this (but then many did not see the
problem with the current implementation!) so careful inspection appreciated.
I have not filed a bug report on launchpad yet as I would like comment on this
list before I do. Maybe this is a feature not a bug ;-) If people agree I will
apply the change to other places in structural_properties.c and post a full
diff to launchpad with the bug report.
Diff is below.
Martin Reed, University of Essex, UK

**
**`igraph-mod.diff`

*Description:* igraph-mod.diff

**[igraph] Bug in igraph_get_shortest_paths_dijkstra for small edge weights**,
*Reed, Martin J* **<=**