yen_k_shortest_paths always returns at least one path [BUG]

[siccegge]

yen_k_shortest_paths will always return at least one path, even if that path is longer than maxdist. This considerably slows down my application that can only use relatively short paths as longer paths are rather slow to find.

julia> cycle_digraph(10)
{10, 10} directed simple Int64 graph

julia> g = cycle_digraph(10)
{10, 10} directed simple Int64 graph

julia> yen_k_shortest_paths(g, 2, 1, weights(g), 2, maxdist=2)
LightGraphs.YenState{Int64,Int64}([9], Array{Int64,1}[[2, 3, 4, 5, 6, 7, 8, 9, 10, 1]])

Version information

Commit c6da87ff4b (2019-08-20 00:03 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin19.0.0)
  CPU: Intel(R) Core(TM) i5-6267U CPU @ 2.90GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

    Status `~/.julia/environments/v1.2/Project.toml`
  [093fc24a] LightGraphs v1.3.0

[sbromberger]

@Thuener - question for you: what is maxdist supposed to do?

[Thuener]

You can define a maximum distance of the path, the algorithm will stop if it found a lower path with higher value then that. There is a bug when there isn't any path lower than maxdist, the code now returns the fist path found by Dijkstra. This can be fixed just verifying the value, however, this will not increase the performance since the algorithm has to construct the path in order to verify the length of it. The alternative is to limit the Dijkstra algorithm but I don't know if it is possible.

[sbromberger]

@Thuener - thanks for jumping in. I don't understand this behavior:

julia> e = [(1,2), (2,3), (3,4), (4,8), (1,5), (5,6), (6,8), (1,7), (7,8)];

julia> g = SimpleDiGraphFromIterator(Edge.(e))
{8, 9} directed simple Int64 graph

julia> yen_k_shortest_paths(g, 1, 8, weights(g), 4; maxdist=1).paths
1-element Array{Array{Int64,1},1}:
 [1, 7, 8]

julia> yen_k_shortest_paths(g, 1, 8, weights(g), 4; maxdist=2).paths
1-element Array{Array{Int64,1},1}:
 [1, 7, 8] # this makes sense given what you said above.

julia> yen_k_shortest_paths(g, 1, 8, weights(g), 4; maxdist=3).paths
2-element Array{Array{Int64,1},1}:
 [1, 7, 8]  
 [1, 5, 6, 8] # this doesn't make sense to me.

julia> yen_k_shortest_paths(g, 1, 8, weights(g), 4; maxdist=4).paths
3-element Array{Array{Int64,1},1}:
 [1, 7, 8]      
 [1, 5, 6, 8]   
 [1, 2, 3, 4, 8] # this doesn't make sense to me

[Thuener]

In your example all edges weights are one, thus:

• The path [1, 5, 6, 8] has 3 edges, dist of 3;
• The [1, 2, 3, 4, 8] has 4 edges, dist of 4.

The path is only rejected if dist > maxdist.

[sbromberger]

@Thuener can you take a look at this bug report? Thank you.

[Thuener]

@sbromberger Should I just implement the solution of verifying the dist of the returned path returned by Dijkstra algorithm and return [] if it is strictly higher then maxdist? I will create some test cases also. There is some way to limit the path distance in dijkstra_shortest_paths?

[sbromberger]

I don't think there's a way to limit the distance in dijkstra right now, but if you wanted to implement it, that'd be great. Please do so in LightGraphs.Experimental.ShortestPaths, though, since we're going to be deprecating the old functions to use the new way of doing things.

[sbromberger]

cc @estelle0500