Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > [ANN] priority-queue 0.1.2

Reply
Thread Tools

[ANN] priority-queue 0.1.2

 
 
Brian Schröder
Guest
Posts: n/a
 
      10-27-2005
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[u] =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?



--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/


 
Reply With Quote
 
 
 
 
Tom Copeland
Guest
Posts: n/a
 
      10-28-2005
On Fri, 2005-10-28 at 06:56 +0900, Brian Schr=F6der 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.p...6&group_id=3D=
5&atid=3D104

if/when they occur...

Yours,

Tom




 
Reply With Quote
 
 
 
 
Daniel Amelang
Guest
Posts: n/a
 
      10-29-2005
------=_Part_8936_31777565.1130548966917
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

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

------=_Part_8936_31777565.1130548966917--


 
Reply With Quote
 
Brian Schröder
Guest
Posts: n/a
 
      10-29-2005
On 29/10/05, Daniel Amelang <(E-Mail Removed)> wrote:
> 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
>
>


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
--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/


 
Reply With Quote
 
Joel VanderWerf
Guest
Posts: n/a
 
      10-29-2005
Brian Schr=F6der 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...by-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.

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


 
Reply With Quote
 
Brian Schröder
Guest
Posts: n/a
 
      10-29-2005
On 29/10/05, Joel VanderWerf <(E-Mail Removed)> wrote:
> Brian Schr=F6der 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...by-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
>
>


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

cheers,

Brian

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off




Advertisments