[ANN] priority-queue 0.1.2

[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 = 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/

[Tom Copeland]

On Fri, 2005-10-28 at 06:56 +0900, Brian Schröder wrote:
> On a sidenote, what became of the plans to
> synchronize rubyforge entries to raa?

Haven't looked at that in a while... but any updates will be posted
here:

http://rubyforge.org/tracker/index.php?func=detail&aid=196&group_id=5&atid=104

if/when they occur...

Yours,

Tom

[Daniel Amelang]

Cool Brian! So, from what I can tell, you're providing (or could provide)
some of the same functionality as rbtree. How does your creation compare?

Dan Amelang

[Brian Schröder]

Hello Dan,

I have not looked very deep into rbtree. Maybe it is possible to
implement a priority queue on top of rbtree. But generally it seems
inverse to a priority queue. It orders by key, while a priority queue
orders by priority (value in hash terms).

A priority queue offers another (not a real subset) set of functions
than an rbtree. The complexity of the operations available in both
datastructures differs.

From the rbtree homepage:

"... the complexity for insert, search and delete is O(log N) in
expected and worst case."

while the complexities for the interesting operations in this priority
queue implementation are

insert O(1)
delete O(1) average
delete_min O(log n) average
change priority O(1) average

These properties allow for example to create an O(m + n log n)
shortest path algorithm where m is the number of edges and n the
number of nodes in the graph.

So to summerize, theses datastructures are different and are usefull
for different algorithms.

best regards,

Brian

[Joel VanderWerf]

Brian Schröder wrote:
> I have not looked very deep into rbtree. Maybe it is possible to
> implement a priority queue on top of rbtree. But generally it seems
> inverse to a priority queue. It orders by key, while a priority queue
> orders by priority (value in hash terms).

I've been using this PriorityQueue based on rbtree:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/133202

but, Brian, your implementation sounds like it is better suited to being
a priority queue. Also, I think you said there is a pure ruby as well as
extension version of it, which is useful in some situations. I will
check it out when I get a chance, and maybe do some benchmarks.

--
vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

[Brian Schröder]

That would be great. Please feed back your experiences with the queue.

cheers,