search

luukvdmeer / sfnetworks

Tidy Geospatial Networks in R
https://luukvdmeer.github.io/sfnetworks/
Other
352 stars 20 forks source link

Test fails with the development version of igraph #232

Closed krlmlr closed 1 year ago

krlmlr commented 1 year ago

Describe the bug

One of the tests, https://github.com/luukvdmeer/sfnetworks/blob/main/tests/testthat/test_paths.R#L237-L243, now fails with the development version of igraph. The call distances(mode = "in", algorithm = "johnson") now raises an error.

Distances should be the same, irrespective of the algorithm used by igraph. What's the purpose of this test, can this be achieved in another way (e.g., by mocking)?

Reproducible example

N/A

Expected behavior

Tests pass with the development version of igraph.

R Session Info

Install the latest version of igraph via devtools::install_github("igraph/rigraph@master") .

CC @ntamas @szhorvat.

szhorvat commented 1 year ago

For context on this, please see https://github.com/igraph/rigraph/issues/571. It's not quite settled yet how this will be dealt with in igraph. The original fix restricts the Johnson method to using only mode='out' on directed graphs. The failure here was caused by using mode='in'.

All this said, the test used in sfnetwork does not achieve anything, and I recommend removing or changing it. Johnson's algorithm is intended specifically for directed graphs with some negative edge weights. When there are no negative weights, igraph will just use Dijsktra's algorithm, even if you specified Johnson. Thus the test, in its current form, compares Dijsktra against Dijkstra and can never fail.

Why does igraph just use Dijkstra when there are no negative weights? This makes perfect sense if we look at how Johnson's algorithm works: it simply transforms edge weights to ensure that they are all non-negative, allowing the use of Dijkstra's method instead of the Bellman-Ford algorithm, which has worse asymptotic complexity.

To sum up, I recommend removing the test that @krlmlr referenced, irrespective of how this will be dealt with in igraph 1.3.6. Comparing results between Johnson and Dijkstra makes no sense as the former is only used with negative edge weights, while the latter is only used with non-negative ones.

loreabad6 commented 1 year ago

Hi @krlmlr and @szhorvat, thank you for pointing us to this failing test. The aim of the test is jsut to check that parameters are passed correctly onto igraph::distances(), and during creating this test we probably overlooked the conceptual theory of the algorithms. To keep the test alive, I switched the algorithm to unweighted, which should definitely result in different distances.