class StableMatching::Roommate::PhaseIIIRunner
Public Class Methods
new(preference_table, opts = {})
click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 100 def initialize(preference_table, opts = {}) @preference_table = preference_table @logger = opts.fetch(:logger) end
Public Instance Methods
run()
click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 105 def run # The output of previous phase may have resulted in a complete # table, in which case this step doesn't need to be run return @preference_table if @preference_table.complete? while table_is_stable? && !@preference_table.complete? x = [@preference_table.members_with_multiple_preferences.first] y = [nil] until any_repeats?(x) # require 'pry'; binding.pry if x.last.second_preference.nil? y << x.last.second_preference x << y.last.last_preference end detect_and_reject_cycles(x, y) end end
Private Instance Methods
any_repeats?(arr)
click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 126 def any_repeats?(arr) arr.uniq.count != arr.count end
detect_and_reject_cycles(x, y)
click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 130 def detect_and_reject_cycles(x, y) x, y = retrieve_cycle(x, y) msg = "Found cycle: " y.each_with_index { |_, i| msg << "(#{x[i].name}, #{y[i].name})" } @logger.debug(msg) x.each_with_index do |r1, i| r2 = y[i] @logger.debug("Mutually rejecting '#{r1.name}', '#{r2.name}'") r2.reject!(r1) end end
retrieve_cycle(x, y)
click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 144 def retrieve_cycle(x, y) repeated_member = x.detect { |i| x.count(i) > 1 } first_index = 1 last_index = x.count - x.reverse.index(repeated_member) - 1 [x[first_index..last_index], y[first_index..last_index]] end
table_is_stable?()
click to toggle source
# File lib/stable-matching/roommate/phase_iii_runner.rb, line 153 def table_is_stable? return true if @preference_table.stable? raise StableMatching::NoStableSolutionError, "No stable match found!" end