class StableMatching::Roommate
Provides a solution to the Stable Roommate
problem by implementing the Irving algorithm
Takes as input the preferences of each member and produces a mathematically optimal matching/pairing between members.
Example Input:
preferences = { "A" => ["B", "D", "C"], "B" => ["D", "A", "C"], "C" => ["D", "A", "B"], "D" => ["C", "A", "B"] }
Example Output:
{"A"=>"B", "B"=>"A", "C"=>"D", "D"=>"C"}
Public Class Methods
Initializes a `StableMatching::Roommate` object.
Inputs:
preference_table
-
A
Hash
ofArray
values specifying the preferences of the group.Array
can containString
orInteger
entries. opts[:logger]
-
Logger
instance to use for logging
Output:
StableMatching::Roommate
instance
# File lib/stable-matching/roommate.rb, line 67 def initialize(preference_table, opts = {}) @orig_preference_table = preference_table set_logger(opts) end
Runs the algorithm with the specified inputs.
This is a class level shortcut to initialize a new StableMatching::Roommate
instance and calls solve!
on it.
Inputs:
preference_table
-
A
Hash
ofArray
values specifying the preferences of the group
Output: A Hash
mapping members to other members.
# File lib/stable-matching/roommate.rb, line 49 def self.solve!(preference_table) new(preference_table).solve! end
Public Instance Methods
Runs the algorithm on the preference_table. Also validates the preference_table
and raises an error if invalid.
The roommate algorithm is not guranteed to find a solution in all cases and will raise an error if a solution is mathematically unstable (does not exist).
Output:
A Hash
mapping members to other members.
Raises:
StableMatching::InvalidPreferences
-
When
preference_table
is of invalid format StableMatching::NoStableSolutionError
-
When no mathematically stable solution can be found
# File lib/stable-matching/roommate.rb, line 89 def solve! validate! @logger.debug("Running Phase I") PhaseIRunner.new(preference_table, logger: @logger).run @logger.debug("Running Phase II") PhaseIIRunner.new(preference_table, logger: @logger).run @logger.debug("Running Phase III") PhaseIIIRunner.new(preference_table, logger: @logger).run build_solution end
Private Instance Methods
# File lib/stable-matching/roommate.rb, line 114 def build_solution solution = {} preference_table.members.each do |member| solution[member.name] = member.first_preference.name end solution end
# File lib/stable-matching/roommate.rb, line 110 def preference_table @preference_table ||= PreferenceTable.new(@orig_preference_table) end
# File lib/stable-matching/roommate.rb, line 106 def validate! Validator.validate!(@orig_preference_table) end