Graphs.jl icon indicating copy to clipboard operation
Graphs.jl copied to clipboard

[BUG] `yen_k_shortest_paths` doesn't work with Unitful (i.e., `Number`) weights

Open filchristou opened this issue 1 year ago • 1 comments

Description of bug Passing an array of Unitful.jl doesn't work with yen_k_shortest_paths. It's because no method is defined to accept weights of AbstractMatrix{<:Number}, since now only AbstractMatrix{<:Real} is accepted.

How to reproduce

julia> using Graphs, Unitful

julia> g = SimpleGraph(5)

julia> ws = [v1 == v2 ? 0.0u"km" : (v1+v2)*1.0u"km" for v1 in vertices(g), v2 in vertices(g)]

julia> yen_k_shortest_paths(g, 1, 2, ws)
ERROR: MethodError: no method matching yen_k_shortest_paths(::SimpleGraph{Int64}, ::Int64, ::Int64, ::Matrix{Qu
antity{Float64, 𝐋, Unitful.FreeUnits{(km,), 𝐋, nothing}}})

Closest candidates are:
  yen_k_shortest_paths(::AbstractGraph, ::U, ::U) where U<:Integer
   @ Graphs ~/.julia/packages/Graphs/FXxqo/src/shortestpaths/yen.jl:26
  yen_k_shortest_paths(::AbstractGraph, ::U, ::U, ::AbstractMatrix{T}) where {U<:Integer, T<:Real}
   @ Graphs ~/.julia/packages/Graphs/FXxqo/src/shortestpaths/yen.jl:26
  yen_k_shortest_paths(::AbstractGraph, ::U, ::U, ::AbstractMatrix{T}, ::Int64; maxdist) where {U<:Integer, T<:
Real}
   @ Graphs ~/.julia/packages/Graphs/FXxqo/src/shortestpaths/yen.jl:26

Stacktrace:
 [1] top-level scope
   @ REPL[10]:1

Expected behavior Unitful.jl should work.

Actual behavior Throws a Method not found error.

Version information

julia> versioninfo()
Julia Version 1.9.4
Commit 8e5136fa297 (2023-11-14 08:46 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 12 × 12th Gen Intel(R) Core(TM) i5-1235U
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, alderlake)
  Threads: 1 on 12 virtual cores
(anissue) pkg> st
Status `~/code/julia/anissue/Project.toml`
  [86223c79] Graphs v1.9.0
  [1986cc42] Unitful v1.19.0

Solution I guess we could just substitute all <:Real to <:Number. Any obvious problems if we do so and is there a reason it's a Real in the first place ?

filchristou avatar Dec 05 '23 15:12 filchristou

I guess some algorithms would fail with more generic numbers, e.g. because things like comparison go missing. But then again my opinion is that the user should know not to compute a shortest path with complex weights. So I would approve a find and replace of all such <:Real. Sounds like a quick win PR

gdalle avatar Dec 06 '23 19:12 gdalle