Homepage of Stefan Salewski
Ruby bindings for Fibonacci Queue of BOOST library
For Dijkstra's shortest path search we need a Priority Queue with fast "Insert" and "Increase Key" operation. A Fibonacci_Queue may be the best solution, because these Operations have order O(1) for that one -- for other heap data structures order is generally O(log n). (Indeed it seems that the Fibonacci_Queue outperforms other heaps only for very large data structures, due to the constant overhead for O(1) operations. See wikipedia.org and stackoverflow.com.
For Ruby there already exists a C implementation of a Fibonacci_Queue from Brian Schroeder, see PriorityQueue. It is from 2005 and seems to work still fine with Ruby 1.9.x, but I am not sure if it is still maintained.
Recently I wrote Ruby Bindings for the Fibonacci_Queue of the BOOST C++ Library.
For Dijkstra's shortest path search I was in need for a "update or insert" operation, which does update an existing key or insert a new node into the Queue when it does not already exist. That operation is not directly supported by the Boost Library -- there exists no fast check for existing elements. To solve this problem we can used a Hash in parallel to our Fibonacci_Queue. I think the Queue of Brian Schroeder does this -- it is some minimal overhead.
For my first implementation I simply assigned each object a reference (Pointer) to its Queue. This gives us two restrictions: Each object can be only in one Queue at a time, and it can not exist multiple times in the same Queue. A related problem is, that we do not investigate the content of the data inserted in the Queue -- so if our objects are constant strings, we may insert the same string constant multiple times, because it really are different objects.
Last week I created an additional modified version of this Queue supported by a hash lookup -- so q['Alice'] = 17; q['Alice'] = 18 will update her age, instead inserting a duplicate of her name. This new version of the Queue behaves very similar to hashes, values that are regarded the same for hashes are the same for the Queue, i.e if you have an object o you can use a key [o, true] when inserting it in the Queue and access it later again with that array literal -- literal may be a different object with same content. One problem may occur when you modify objects, name = 'bob'; name << 'by' will make it impossible to access the Queue element as it does for the hash.
Used terms: I am using the term key for the value describing the priority (position) in the Queue and the term data for the object itself. Key is a double float number. Of course you need an installed C compiler and BOOST library to use these Ruby bindings -- and the Ruby interpreter, I tested with version 1.9.3 and 2.0
Installation (for Linux) cd RBOOST/Fibonacci_Queue ruby extconf.rb make cd RBOOST/Fibonacci_Queue_Hash ruby extconf.rb make
We can use a Min-Queue (default) or a Max-Queue if we use +1 as parameter for initialization of the Queue. For both cases moving elements to the top has O(1) costs -- the other direction is O(log(n)). For initialization you may use a second parameter, which is the return value for q.key(object) when the object is not included in the Queue. Default is nil.
# test.rb -- basic test script with string objects
# call: ruby test.rb
require_relative 'rboost_fibonacci_queue'
q = BOOST::Fibonacci_Queue.new # .new(1) for Max Queue
a = 'Spring'
b = 'Summer'
c = 'Harvest'
d = 'Winter'
q.push(a, 1)
q.push(b, 2)
q.push(c, 3)
q.push(d, 4)
puts q.top # smallest key for Min Queue
puts q.pop # remove that one
puts q.top_data # => Summer
puts q.top_key # => 2
q.update_or_insert(a, 7) # insert because we removed node a prior
q[a] = 7 # the same operation, but no effect here
These are the supported methods:
q[data] # => key or nil
q[data] = key # == update_or_insert(data, key)
q.clear
q.decrease(data, key)
q.delete(data)
q.delete_top
q.each{|el| puts el[0], el[1]}
q.empty?
q.increase(data, key) # move data to top
q.insert(data, key)
q.key(data)
q.length, q.size
q.pop # => removes and returns [data, key]
q.pop_data
q.pop_key
q.push(data, key) # same as insert
q.to_a # array of [data, key]
q.top # returns [data, key]
q.top_data
q.top_key
q.update(data, key) # data must already exist in Queue
q.update_or_insert(data, key) # updates existing nodes or insert a new one, the same as q[data] = key
For a Min-Queue top() and pop() operations are related to the smallest key, for a Max-Queue to the largest key. Additional to the update() operation, which can be used to increase or decrease the key of an data object, BOOST library offers the decrease() and increase() operation, which does work correctly only for one direction. Increase() can be used, if you are sure that you are moving the data object to the top (O(1) costs) -- for a Min-Queue this means that you assign a smaller key! Decrease works for the opposite direction. Note that increase() and decrease() assigns a new key like update, they do not add or subtract an amount. The update() operation should be not significantly slower, it only has to determine the direction. Moving elements to the top should be always very fast, O(1) order.
I have added the operations q.inc?() and q.dec?() -- inc?() will insert the object if it is not already in the Queue or it will try to move it to the top (Min- or Max_Queue), but will ignore the operation if the new key would move it away from the top. Dec() works for the other direction.
For the Queue without Hash support we have to consider this: Whenever an object is inserted in a Queue, its gets a pointer to that Queue. You have to remove that object from the Queue by operations like pop(), delete() or clear() (clear whole Queue) to reset that pointer to nil before you can again insert that object in another Queue. (The garbage collector can not do it, so q = nil is not sufficient, use q.clear before.)
I think that the version with Hash support will be the best choice for most users. The disadvantage is the additional memory consumption by the Hash, and a minimal slower response due to the additional hash lookup.
Please note, this is the initial release of this software, and I have done only some basics tests. I am using the Queue for my PCB topological router, it seems to work fine, but I am using only a subset of all provided methods.