Comments (6)
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?
from rgl.
@monora failing test added.
from rgl.
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.
from rgl.
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 :)
from rgl.
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.
from rgl.
Thanks. I love the FLOSS way :)
from rgl.
Related Issues (20)
- Automate release process HOT 4
- Fix links in README link section
- Fix link to LICENSE in CONTRIBUTING.md
- dependency on pairing_heap would downgrade from v3.0.1 to v0.3.0 HOT 1
- Licence specification HOT 2
- set_to_begin incorrect for graph iterator
- Unclear how to use bellman_ford_shortest_paths method HOT 2
- The License of the Project is Unclear HOT 6
- how i can use this in laravel ? HOT 2
- `depth_first_search` Doesn't work HOT 1
- Remove superfluous :GRAY assignment in depth first visit
- Support Ruby 3.2
- doc: Fix bad badge for codeclimate
- Fix wrong module and class comments in generated documentation
- How can I add a subgraph? HOT 2
- each_in_neighbor() does not call a passed block
- each_in_neighbor() raises exception on unconnected vertices
- Refactor edge/vertex settings to no longer require individual options initialization HOT 1
- undefined method `set_vertex_options' HOT 7
- calling require inside a mehtod is causing memory bloat if this method is called multiple times. HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from rgl.