From: "Brian Schröder" <ruby.brian@...>
Date: 2005-10-28T06:56:31+09:00
Subject: [ANN] priority-queue 0.1.2

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/