[ANN] priority-queue 0.1.2

Discussion in 'Ruby' started by Brian Schröder, Oct 27, 2005.

  1. 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?



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

    Stringed instrument chords: http://chordlist.brian-schroeder.de/
     
    Brian Schröder, Oct 27, 2005
    #1
    1. Advertising

  2. Brian Schröder

    Tom Copeland Guest

    Tom Copeland, Oct 28, 2005
    #2
    1. Advertising

  3. ------=_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--
     
    Daniel Amelang, Oct 29, 2005
    #3
  4. On 29/10/05, Daniel Amelang <> 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/
     
    Brian Schröder, Oct 29, 2005
    #4
  5. 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/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.

    --=20
    vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407
     
    Joel VanderWerf, Oct 29, 2005
    #5
  6. On 29/10/05, Joel VanderWerf <> 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/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
    >
    >


    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/
     
    Brian Schröder, Oct 29, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    728
    Russell Warren
    Jun 27, 2006
  2. Marcel Müller
    Replies:
    3
    Views:
    595
    Marcel Müller
    Apr 27, 2009
  3. Kris
    Replies:
    0
    Views:
    538
  4. Brian Schröder

    [ANN] Priority Queue 0.0.0 Homepage

    Brian Schröder, Aug 30, 2005, in forum: Ruby
    Replies:
    0
    Views:
    112
    Brian Schröder
    Aug 30, 2005
  5. Brian Schröder
    Replies:
    0
    Views:
    99
    Brian Schröder
    Oct 31, 2005
Loading...

Share This Page