Class: StableMatching::Roommate

Inherits:
Object
  • Object
show all
Includes:
LoggingHelper
Defined in:
lib/stable-matching/roommate.rb,
lib/stable-matching/roommate/validator.rb,
lib/stable-matching/roommate/phase_i_runner.rb,
lib/stable-matching/roommate/phase_ii_runner.rb,
lib/stable-matching/roommate/phase_iii_runner.rb,
lib/stable-matching/roommate/preference_table.rb

Overview

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"}

Defined Under Namespace

Classes: PhaseIIIRunner, PhaseIIRunner, PhaseIRunner, PreferenceTable, Validator

Class Method Summary collapse

Instance Method Summary collapse

Methods included from LoggingHelper

#set_logger

Constructor Details

#initialize(preference_table, opts = {}) ⇒ Roommate

Initializes a ‘StableMatching::Roommate` object.

Inputs:

preference_table

A Hash of Array values specifying the preferences of the group. Array can contain String or Integer entries.

opts[:logger]

Logger instance to use for logging

Output:

StableMatching::Roommate instance



67
68
69
70
 
# File 'lib/stable-matching/roommate.rb', line 67

def initialize(preference_table, opts = {})
  @orig_preference_table = preference_table
  set_logger(opts)
end

Class Method Details

.solve!(preference_table) ⇒ Object

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 of Array values specifying the preferences of the group

Output: A Hash mapping members to other members.



49
50
51
 
# File 'lib/stable-matching/roommate.rb', line 49

def self.solve!(preference_table)
  new(preference_table).solve!
end

Instance Method Details

#solve! ⇒ Object

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



89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
# 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