dijkstra_shortest_path strangely fails to find a path

[gorn]

There is some really strange error in dijkstra_shortest_path (or I am missing something very obvious).

irb(main):001:0> require 'rgl/adjacency'
=> true
irb(main):002:0> require 'rgl/dijkstra'
=> true
irb(main):003:0> g = RGL::AdjacencyGraph[2,53, 2,3, 3,8, 3,28, 3,39, 29,58, 8,35, 12,39, 10,29, 62,15, 15,32,  32,58, 58,44, 44,53]
=> #<RGL::AdjacencyGraph:0x00000001c6ff88 @edgelist_class=Set, @vertices_dict={2=>#<Set: {53, 3}>, 53=>#<Set: {2, 44}>, 3=>#<Set: {2, 8, 28, 39}>, 8=>#<Set: {3, 35}>, 28=>#<Set: {3}>, 39=>#<Set: {3, 12}>, 29=>#<Set: {58, 10}>, 58=>#<Set: {29, 32, 44}>, 35=>#<Set: {8}>, 12=>#<Set: {39}>, 10=>#<Set: {29}>, 62=>#<Set: {15}>, 15=>#<Set: {62, 32}>, 32=>#<Set: {15, 58}>, 44=>#<Set: {58, 53}>}>
irb(main):004:0> g.dijkstra_shortest_path(Hash.new(1),53,62)
=> nil

But there is a path [53, 44, 58, 32, 15, 62]. I tried to minimalize the graph furher, but strangely after removing any edge it suddenly behaves correctly (either finds path or not when there is not one).

PS: I can fork the repo and request pull with the test, if it helps.

[monora]

PS: I can fork the repo and request pull with the test, if it helps.
That would be helpful.
@KL-7 Could you have a look at this?

[gorn]

@monora failing test added.

[KL-7]

I have a feeling that you hit a bug in the heap implementation we're using (from algorithms gem).

If you add logging for heap push and pop commands in dijkstra.rb and run your test case in a console you'll get the following:

$ irb -Ilib -rrgl/base -rrgl/adjacency -rrgl/dijkstra
> graph = RGL::AdjacencyGraph[2,53, 2,3, 3,8, 3,28, 3,39, 29,58, 8,35, 12,39, 10,29, 62,15, 15,32,  32,58, 58,44, 44,53]
> graph.dijkstra_shortest_path(Hash.new(1), 53, 62)

push 53
poped 53
push 2
push 44
poped 2
push 3
poped 44
push 58
poped 3
push 8
push 28
push 39
poped 58
push 29
push 32
poped 8
push 35
poped 39
push 12
poped 32
push 15
poped 29
push 10
poped 28
poped 10
poped 35
poped 12
poped 12

The way Dijkstra's algorithm executes in this case, it should complete the path on the last step by relaxing the edge [15, 62]. But as you can see from the log, even though we put vertex 15 into the heap, we never get to pop it. Instead, for some reason, vertex 12 is poped twice.

I was able to reproduce this behavior of the heap outside of Dijkstra algorithm: on the last step, even though it has the right node stored inside of it (with the correct vertex), on the last step it just pops the wrong value.

I'm not that familiar with this particular implementation of a heap, so I'll need more time to investigate the issue. You can also take a look, if you're interested.

[gorn]

According to github the project seems to be little inactive, so unless you have time to take over, you may consider using different heap implementation. See kanwei/algorithms#23 which is about similar problem, it seems to be as trivial as errors with heaps longer then 10 :)

[KL-7]

Oh, wow. Thanks for tracking down this issue. If I find time, I'll still try to dig into their implementation and see if there's a simple fix for it. If not, we can definitely switch to a different heap implementation.

[gorn]

Thanks. I love the FLOSS way :)