get_all_shortest_paths crashes python

[JT Bates]

I'm using python-igraph and the interpreter crashes when I call get_all_shortest_paths and the paths have more than one edge:

$ graph.get_all_shortest_paths(2,415,'weight')
Assertion failed: (parent_path_idx >= 0), function igraph_get_all_shortest_paths_dijkstra, file ../../../src/structural_properties.c, line 5756.
Abort trap: 6

Calling shortest_paths or get_shortest_paths does not raise an error. I'm using Mac OS 10.7 and I installed python-igraph from the binary pkg.

[Tamás Nepusz (ntamas)]

Does it happen for every such graph? I cannot reproduce it on my machine yet:

In [1]: g=Graph.GRG(100, 0.2)
In [2]: g.get_all_shortest_paths(2, 98)
Out[2]:
[[2, 11, 12, 29, 43, 68, 86, 98],
 [2, 10, 28, 45, 51, 68, 86, 98],
 [2, 11, 28, 45, 51, 68, 86, 98],
 [2, 19, 28, 45, 51, 68, 86, 98],
 [2, 11, 12, 31, 51, 68, 86, 98],
 [2, 11, 12, 29, 43, 68, 85, 98],
 [2, 10, 28, 45, 51, 68, 85, 98],
 [2, 11, 28, 45, 51, 68, 85, 98],
 [2, 19, 28, 45, 51, 68, 85, 98],
 [2, 11, 12, 31, 51, 68, 85, 98],
 [2, 11, 12, 29, 43, 68, 80, 98],
 [2, 10, 28, 45, 51, 68, 80, 98],
 [2, 11, 28, 45, 51, 68, 80, 98],
 [2, 19, 28, 45, 51, 68, 80, 98],
 [2, 11, 12, 31, 51, 68, 80, 98]]

Can you attach an example graph to this bug report on which I could reproduce the problem?

[JT Bates (jtbates)]

No, not for every graph. This is the smallest example I could produce, the graph is attached.

In [3]: igl = igraph.load('graph.picklez')

In [4]: igl.get_all_shortest_paths(714,1200)
Out[4]: [[714, 191, 415, 1200]]

In [5]: igl.get_all_shortest_paths(714,1200,'weight')
Assertion failed: (parent_path_idx >= 0), function igraph_get_all_shortest_paths_dijkstra, file ../../../src/structural_properties.c, line 5756.
Abort trap: 6

[JT Bates (jtbates)]

I also noticed this error:

In [19]: grg=igraph.Graph.GRG(200,.2)

In [21]: grg.get_shortest_paths(0,0)
Out[21]: [[0]]

In [22]: grg.get_all_shortest_paths(0,0)
---------------------------------------------------------------------------
InternalError Traceback (most recent call last)
/Users/jtbates/kaggle/facebook2/<ipython-input-22-9acb10a42f35> in <module>()
----> 1 grg.get_all_shortest_paths(0,0)

InternalError: Error at ../../../src/structural_properties.c:1006: possible bug in igraph_get_all_shortest_paths, maxdist is negative, Invalid value

Should I open a separate bug report?

[Tamás Nepusz (ntamas)]

Thanks for the graph; there is no need to file a separate bug report, I will take care of both of these soon.

[Tamás Nepusz (ntamas)]

Seems like the bug is triggered by zero-weight edges in your graph, so you can do this as a quick workaround:

g.es.select(weight=0)["weight"] = 1e-15

Chances are that I will commit a fixed version into the trunk today so you can get the latest nightly from about 6am tomorrow (GMT) and compile that.

[Tamás Nepusz (ntamas)]

Fixed in #3066 of trunk and #3015 of 0.6-main.

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/125