Ruby References
Revision as of 12:10, 18 March 2010 by PeterHarding (talk | contribs)
Dijkstra’s Algorithm in Ruby
http://blog.linkedin.com/2008/09/19/implementing-di/
require 'pqueue' class Algorithm INFINITY = 1 << 32 def self.dijkstra(source, edges, weights, n) visited = Array.new(n, false) shortest_distances = Array.new(n, INFINITY) previous = Array.new(n, nil) pq = PQueue.new(proc {|x,y| shortest_distances[x] < shortest_distances[y]}) pq.push(source) visited = true shortest_distances = 0 while pq.size != 0 v = pq.pop visited[v] = true if edges[v] edges[v].each do |w| if !visited[w] and shortest_distances[w] > shortest_distances[v] + weights[v][w] shortest_distances[w] = shortest_distances[v] + weights[v][w] previous[w] = v pq.push(w) end end end end return [shortest_distances, previous] end end
pqueue
http://www.math.kobe-u.ac.jp/~kodama/tips-ruby-pqueue.html
# Priority queue with array based heap. # # This is distributed freely in the sence of # GPL(GNU General Public License). # # K.Kodama 2005/09/01. push_array, pop_array # Rick Bradley 2003/02/02. patch for Ruby 1.6.5. Thank you! # K.Kodama 2001/03/10. 1st version class PQueue attr_accessor :qarray # format: [nil, e1, e2, ..., en] attr_reader :size # number of elements attr_reader :gt # compareProc def initialize(compareProc=lambda{|x,y| x>y}) # By default, retrieves maximal elements first. @qarray=[nil]; @size=0; @gt=compareProc; make_legal end private :initialize def upheap(k) k2=k.div(2); v=@qarray[k]; while ((k2>0)and(@gt[v,@qarray[k2]])); @qarray[k]=@qarray[k2]; k=k2; k2=k2.div(2) end; @qarray[k]=v; end private :upheap def downheap(k) v=@qarray[k]; q2=@size.div(2) loop{ if (k>q2); break; end; j=k+k; if ((j<@size)and(@gt[@qarray[j+1],@qarray[j]])); j=j+1; end; if @gt[v,@qarray[j]]; break; end; @qarray[k]=@qarray[j]; k=j; } @qarray[k]=v; end; private :downheap def make_legal for k in 2..@size do; upheap(k); end; end; def empty? return (0==@size) end def clear @qarray.replace([nil]); @size=0; end; def replace_array(arr=[]) # Use push_array. @qarray.replace([nil]+arr); @size=arr.size; make_legal end; def clone q=new; q.qarray=@qarray.clone; q.size=@size; q.gt=@gt; return q; end; def push(v) @size=@size+1; @qarray[@size]=v; upheap(@size); end; def push_array(arr=[]) @qarray[@size+1,arr.size]=arr; arr.size.times{@size+=1; upheap(@size)} end; def pop # return top element. nil if queue is empty. if @size>0; res=@qarray[1]; @qarray[1]=@qarray[@size]; @size=@size-1; downheap(1); return res; else return nil end; end; def pop_array(n=@size) # return top n-element as an sorted array. (i.e. The obtaining array is decreasing order.) # See also to_a. a=[] n.times{a.push(pop)} return a end; def to_a # array sorted as increasing order. # See also pop_array. res=@qarray[1..@size]; res.sort!{|x,y| if @gt[x,y]; 1;elsif @gt[y,x]; -1; else 0; end;} return res end def top # top element. not destructive. if @size>0; return @qarray[1]; else return nil; end; end; def replace_top_low(v) # replace top element if v<top element. if @size>0; @qarray[0]=v; downheap(0); return @qarray[0]; else @qarray[1]=v; return nil; end; end; def replace_top(v) # replace top element if @size>0; res=@qarray[1]; @qarray[1]=v; downheap(1); return res; else @qarray[1]=v; return nil; end; end; def each_pop # iterate pop. destructive. Use as self.each_pop{|x| ... }. while(@size>0); yield self.pop; end; end; def each_with_index # Not ordered. Use as self.each_with_index{|e,i| ... }. for i in 1..@size do; yield @qarray[i],i; end; end end # class pqueue if $0 == __FILE__ pq=PQueue.new(proc{|x,y| x>y}) pq.push(2) pq.push(3) pq.push(4) pq.push(3) pq.push(2) pq.push(4) pq.push_array([3,5,4]) print "size: "+pq.size.to_s+"\n" print "heap: "; pq.each_with_index{|x,y| print x.to_s+" "}; print "\n" print "to_a: "+pq.to_a.to_s+"\n" # a=pq.pop_array; p a.to_s print "pop : ";pq.each_pop{|x| print x.to_s+" "}; print "\n" end;