Hello Group,
I finally released a polished up version of my priority queue extension.
A priority-queue is usefull for algorithms like "dijkstras shortest
path algorithm" that finds shortest paths in a graph.
The extension now includes a pure ruby and a c extension. The runtime
behaviour can be seen at
http://ruby.brian-schroeder.de/priority-queue/
which happens to be the project homepage.
I also added a rubyforge project and packed up the extension using
setup.rb and as a gem, so you should be able to do:
gem install PriorityQueue
and have it working. But that is not reality as only version 0.1.0 has
found its way into the gem lists. I have asked tom what I did wrong,
so please be patient.
I would be very interested in feedback from people testing the
extension under exotic systems like aix and windows that I do not have
available at home.
I hope this will be usefull,
Brian
# Links:
http://ruby.brian-schroeder.de/priority-queue/
http://rubyforge.org/projects/priority-queue/
# Usage:
## Use it like a hash
require 'priority_queue'
q = PriorityQueue.new
q["node1"] = 0
q["node2"] = 1
q.min #=> "node1"
q[q.min] #=> 0
q.min_value #=> 0
q["node2"] = -1
q.delete_min #=> "node2", 1
q["node2"] #= nil
q["node3"] = 1
q.delete("node3") #=> "node3", 1
q.delete("node2") #=> nil
## Dijkstras shortest path algorithm:
def dijkstra(start_node)
# Nodes that may have neighbours wich can be relaxed further
active = PriorityQueue.new
# Best distances found so far
distances = Hash.new { 1.0 / 0.0 }
# Parent pointers describing shortest paths for all nodes
parents = Hash.new
# Initialize with start node
active[start_node] = 0
until active.empty?
u, distance = active.delete_min
distances[u] = distance
d = distance + 1
u.neighbours.each do | v |
next unless d < distances[v] # we can't relax this one
active[v] = distances[v] = d
parents[v] = u
end
end
parents
end
PS: The raa entry is not updated as I have forgotten my password. I
already asked the admins to reset it, so I hope this will reflect
correct information soon. On a sidenote, what became of the plans to
synchronize rubyforge entries to raa?
···
--
http://ruby.brian-schroeder.de/
Stringed instrument chords: http://chordlist.brian-schroeder.de/