A* Star is problematic when working with SimpleWeightedGraph

[mzy2240]

The MWE is modified from the test:

using Graphs, SimpleWeightedGraphs

g = SimpleWeightedGraph(3)
add_edge!(g, 1, 2, 0.5)
add_edge!(g, 2, 3, 0.8)
add_edge!(g, 1, 3, 2.0)
a_star(g, 1, 3)

and the return does not match the actual edge weight

2-element Vector{SimpleWeightedEdge{Int64, Float64}}:
 Edge 1 => 2 with weight 1.0  # should be 0.5
 Edge 2 => 3 with weight 1.0  # should be 0.8

Querying the weight using SimpleWeightedGraphs.weight on the vector returned by a_star would give the default weight 1.0, which can be observed by running SimpleWeightedGraphs.weight(a_star(g, 1, 3)[1]) == 1.0.

[gdalle]

Good catch!
The history here is that A* used to fail with SimpleWeightedGraphs. I fixed it in JuliaGraphs/Graphs.jl#125 but still the algorithm calls edgetype_to_return(u, v) to construct the sequence of edges in the path. As a result, the default weight of 1 is used instead of the true weight. This probably should be documented as a caveat.
If you have a better, non-breaking solution, feel free to suggest it.

[gdalle]

One solution might be to call a_star with edgetype_to_return = (u, v) -> SimpleWeightedEdge(u, v, get_weight(g, u, v)) or something like it (haven't tested)

[mzy2240]

thanks for the prompt reply! unfortunately it does not work, feels Graphs.jl needs to be changed in order to pass the function instead of the Type

[gdalle]

Well then you need to do the post processing yourself to re-assign the weights to the returned edges. Think of the result of A* as an unweighted path

[mzy2240]

yeah I have a post process already, just want to flag it as a potential bug, or caveat as you call it

[gdalle]

If you want to contribute a PR explaining this in the docs of Graphs.a_star, it will be welcome

[gdalle]

Fixed it in Graphs.jl