yen_k_shortest_paths with k=2 returns same path twice

vlandau commented 3 years ago

Description of bug When trying to find the two shortest paths from source to target, yen_k_shortest_paths returns the same path twice instead of two different paths that have the same weight.

How to reproduce

using SimpleWeightedGraphs, LightGraphs
g = [0.0      1.0      0.0      1.0      2.82843  0.0      0.0      0.0;
     1.0      0.0      1.0      1.41421  2.0      1.41421  0.0      0.0;
     0.0      1.0      0.0      0.0      2.82843  1.0      0.0      0.0;
     1.0      1.41421  0.0      0.0      2.0      0.0      1.0      1.41421;
     2.82843  2.0      2.82843  2.0      0.0      2.0      2.82843  2.0;
     0.0      1.41421  1.0      0.0      2.0      0.0      0.0      1.41421;
     0.0      0.0      0.0      1.0      2.82843  0.0      0.0      1.0;
     0.0      0.0      0.0      1.41421  2.0      1.41421  1.0      0.0]
g = SimpleWeightedGraph(g)
pathstate = yen_k_shortest_paths(g, 2, 8, weights(g), 2)

Expected behavior I would expect to get back two paths, [2 4 8] and [2 6 8], which both have the same cost distance.

Actual behavior Instead, [2 4 8] is returned twice.

Code demonstrating bug See "how to reproduce" above.

Version information

output from versioninfo()

Julia Version 1.5.3
Commit 788b2c77c1 (2020-11-09 13:37 UTC)
Platform Info:
OS: Linux (x86_64-pc-linux-gnu)
CPU: Intel(R) Xeon(R) E-2176M  CPU @ 2.70GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-9.0.1 (ORCJIT, skylake)
Environment:
JULIA_NUM_THREADS = 11
JULIA_EDITOR = atom  -a

output from ] status LightGraphs [093fc24a] LightGraphs v1.3.0

Additional context I'm using SimpleWeightedGraphs.jl (v1.1.1). Please let me know if I should open this issue in SimpleWeightedGraphs.jl instead.

sbromberger commented 3 years ago

Can reproduce locally.

sbromberger commented 3 years ago

@Thuener - do you have a few cycles to help here?

Thuener commented 3 years ago

I will take a look, give me some days plz.

yucho147 commented 3 years ago

I suffered from the same problem.
This issue seems to be caused by the following bug in SimpleWeightGraph. https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl/issues/66

For example, l.53 in the source code of yen_k_shortest_paths does not remove the edge when SimpleWeightGraph is used. https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/shortestpaths/yen.jl#L53

And, in this case, I solved this issue by doing the following.

pathstate = yen_k_shortest_paths(SimpleGraph(g), 2, 8, weights(g), 2)

If you do like this, you will get the expected result.

About the source code for `yen_k_shortest_paths`

It would be best if the SimpleWeightGraph bug was fixed, but how about using the following in l.36.

gcopy = deepcopy(SimpleGraph(g))

or

gcopy = deepcopy(SimpleDiGraph(g))

and having separate functions for graph::SimpleWeightedGraph and graph::SimpleWeightedDiGraph by using multiple dispatch. https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/shortestpaths/yen.jl#L19 https://github.com/JuliaGraphs/LightGraphs.jl/blob/2a644c2b15b444e7f32f73021ec276aa9fc8ba30/src/shortestpaths/yen.jl#L36

vlandau commented 3 years ago

Nice work @yucho147! Thanks for that detailed explanation. JuliaGraphs members, should we close this issue in favor of the existing one in SimpleWeightedGraphs.jl? In the mean time, this workaround should be sufficient to get things running at least.

sbromberger / LightGraphs.jl