[BUG] a_star does not compute path for SimpleDiGraph with sparce adjacency matrix as weights

[FalafelGood]

Description of bug Shortest path algorithm a_star in src/shortestpath/astar.jl does not compute path for a SimpleDiGraph with a sparse adjacency matrix as weights.

How to reproduce g = SimpleWeightedDiGraph(2) add_edge!(g, 1, 2, 3.14) a_star(SimpleDiGraph(g), 1, 2, weights(g))

Expected behavior a_star finds the only possible path: 1-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}: Edge 1 => 2

Actual behavior a_star returns an empty array, having found no path. 0-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}

Version information Julia Version 1.4.2 Commit 44fa15b150* (2020-05-23 18:35 UTC) Platform Info: OS: Linux (x86_64-pc-linux-gnu) CPU: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-8.0.1 (ORCJIT, skylake) Environment: JULIA_EDITOR = atom -a JULIA_NUM_THREADS = 4

Status~/.julia/environments/v1.4/Project.toml [093fc24a] LightGraphs v1.3.4

Additional context First time reporting bug, let me know if I'm being dumb.

[simonschoelly]

I think the problem here seems to be, that the graph gets somehow transposed when it is converted to a SimpleDiGraph:

julia> adjacency_matrix(g)
2×2 SparseArrays.SparseMatrixCSC{Float64, Int64} with 1 stored entry:
  ⋅   3.14
  ⋅    ⋅ 

julia> adjacency_matrix(SimpleDiGraph(g))
2×2 SparseArrays.SparseMatrixCSC{Int64, Int64} with 1 stored entry:
 ⋅  ⋅
 1  ⋅

[FalafelGood]

I think the problem here seems to be, that the graph gets somehow transposed when it is converted to a SimpleDiGraph:

julia> adjacency_matrix(g)
2×2 SparseArrays.SparseMatrixCSC{Float64, Int64} with 1 stored entry:
  ⋅   3.14
  ⋅    ⋅ 

julia> adjacency_matrix(SimpleDiGraph(g))
2×2 SparseArrays.SparseMatrixCSC{Int64, Int64} with 1 stored entry:
 ⋅  ⋅
 1  ⋅

Agreed. Good find! Further evidence for this:

a_star(SimpleDiGraph(g), 2, 1, weights(g)) 1-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}: Edge 2 => 1

Which wouldn't be possible unless the matrix was transposed.

[gdalle]

Could it be due to line 81 of SimpleWeightedGraphs.jl/simpleweighteddigraph.jl?

LightGraphs.SimpleDiGraph(g::SimpleWeightedDiGraph) = SimpleDiGraph(g.weights)

For some reason, weighted digraphs are stored with [dst, src] indexing, so the weights matrix should probably be transposed before conversion into a standard digraph?

[gdalle]

See https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl/issues/67

[gdalle]

@matbesancon what I was just talking about

[matbesancon]

Yes a PR with the transpose fixed is very much welcome