Union Find Algorithm Implementation in Ruby

来源:互联网 时间:1970-01-01

Recently I was taking the Princeton Algorithms class (Part 1) on Coursera and decided it would be easier to do the Week 1 Exercises if I had an implementation of the Union Find algorithm. Below is the quick prototype I built in Ruby.

02 require 'pry' 04 class UnionFind 05 attr_accessor :nodes, :data_pairs 07 def initialize(n=10, data_set="3-6 4-5") 08 @nodes = [] 09 (0..n-1).each { |i| @nodes[i] = i } 10 @data_pairs = DataPairs.new(data_set) 11 end 13 def root(p) 14 until nodes[p]==p 15 p = nodes[p] 16 end 17 nodes[p] 18 end 20 def connected?(p, q) 21 root(p) == root(q) 22 end 24 def build_union 25 raise 'No data pairs available' if data_pairs.nil? || data_pairs.data_set.nil? 26 data_pairs.data_set.each do |pair| 27 union(pair[0], pair[1]) 28 end 29 end 30 end 32 class QuickUnionFind < UnionFind 34 def union(p, q) 35 return if connected?(p, q) 36 pid = nodes[p].to_i 37 qid = nodes[q].to_i 38 (0..nodes.length-1).each do |i| 39 nodes[i] = qid if nodes[i] == pid 40 end 41 end 43 end 45 class WeightedQuickUnionFind < UnionFind 47 attr_accessor :set_size 49 def initialize(n=10, data_set="3-6 4-5") 50 @set_size = [1]*n 51 super(n, data_set) 52 end 54 def union(p, q) 55 return if connected?(p, q) 56 i = root(p) 57 j = root(q) 58 return if i==j 59 if (set_size[i] < set_size[j]) 60 nodes[i] = j 61 set_size[j] += set_size[i] 62 else 63 nodes[j] = i 64 set_size[i] += set_size[j] 65 end 66 end 68 end 70 class DataPairs 72 attr_accessor :data_set 74 def initialize(set="3-6 4-5") 75 @data_set ||= [] 76 @data_set = make_pairs(set) 77 end 79 def make_pairs(set) 80 number_sets = set.split(" ") 81 number_sets.each do |number_set| 82 data_set << number_set.split("-").map { |x| x.to_i } 83 end 84 data_set 85 end 87 end 89 quf = QuickUnionFind.new(10, "3-6 4-5 9-4 7-0 9-0 3-7") 90 #quf = QuickUnionFind.new(10, "2-7 9-0 4-8 5-4 5-9 2-0") 91 quf.build_union 92 puts "Quick Union: #{quf.nodes.join(" ")}" 94 wquf = WeightedQuickUnionFind.new(10, "7-2 6-9 5-8 1-3 2-6 8-1 9-4 1-4 3-0") 95 wquf.build_union 96 puts "Weighted Quick Union: #{wquf.nodes.join(" ")}"


相关阅读:
Top