B
Brian Schröder
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 =3D PriorityQueue.new
q["node1"] =3D 0
q["node2"] =3D 1
q.min #=3D> "node1"
q[q.min] #=3D> 0
q.min_value #=3D> 0
q["node2"] =3D -1
q.delete_min #=3D> "node2", 1
q["node2"] #=3D nil
q["node3"] =3D 1
q.delete("node3") #=3D> "node3", 1
q.delete("node2") #=3D> nil
## Dijkstras shortest path algorithm:
def dijkstra(start_node)
# Nodes that may have neighbours wich can be relaxed further
active =3D PriorityQueue.new
# Best distances found so far
distances =3D Hash.new { 1.0 / 0.0 }
# Parent pointers describing shortest paths for all nodes
parents =3D Hash.new
# Initialize with start node
active[start_node] =3D 0
until active.empty?
u, distance =3D active.delete_min
distances =3D distance
d =3D distance + 1
u.neighbours.each do | v |
next unless d < distances[v] # we can't relax this one
active[v] =3D distances[v] =3D d
parents[v] =3D 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?
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 =3D PriorityQueue.new
q["node1"] =3D 0
q["node2"] =3D 1
q.min #=3D> "node1"
q[q.min] #=3D> 0
q.min_value #=3D> 0
q["node2"] =3D -1
q.delete_min #=3D> "node2", 1
q["node2"] #=3D nil
q["node3"] =3D 1
q.delete("node3") #=3D> "node3", 1
q.delete("node2") #=3D> nil
## Dijkstras shortest path algorithm:
def dijkstra(start_node)
# Nodes that may have neighbours wich can be relaxed further
active =3D PriorityQueue.new
# Best distances found so far
distances =3D Hash.new { 1.0 / 0.0 }
# Parent pointers describing shortest paths for all nodes
parents =3D Hash.new
# Initialize with start node
active[start_node] =3D 0
until active.empty?
u, distance =3D active.delete_min
distances =3D distance
d =3D distance + 1
u.neighbours.each do | v |
next unless d < distances[v] # we can't relax this one
active[v] =3D distances[v] =3D d
parents[v] =3D 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?