JuliaGraphs
two sided dijkstra
Implemented the Two sided Dijkstra algorithm, still requires documentation and tests
Tests are failing because of #271 which has now been merged. If we merge the JuliaGraphs:master branch of into Dolgalad:bidij this should work
I think your modification to Dijkstra somehow broke a test in the centrality part of the package. My two propositions:
- revert your modifications to only implement bidirectional Dijkstra without changing the original
- investigate why you broke centrality
The error comes from the following test:
# test #1405 / #1406
g = GenericGraph(grid([50, 50]))
z = betweenness_centrality(g; normalize=false)
@test maximum(z) < nv(g) * (nv(g) - 1)
and it looks like this:
Betweenness: Test Failed at /home/runner/work/Graphs.jl/Graphs.jl/test/centrality/betweenness.jl:95
Expression: maximum(z) < nv(g) * (nv(g) - 1)
Evaluated: 3.193572232997055e10 < 6247500
It is related to the following issue in the old LightGraphs.jl package https://github.com/sbromberger/LightGraphs.jl/issues/1405
It also look to me, as if those changes might make the algorithm perform slower than before, but I only checked this single case: before:
julia> @btime dijkstra_shortest_paths($(grid([50, 50])), 1);
548.740 μs (81 allocations: 165.11 KiB)
after
julia> @btime dijkstra_shortest_paths($(grid([50, 50])), 1);
585.437 μs (83 allocations: 184.72 KiB)
