yen_k_shortest_paths with k=2 returns same path twice

[vlandau]

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]

Can reproduce locally.

[sbromberger]

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

[Thuener]

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

[yucho147]

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]

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.