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

new(preference_table, opts = {}) click to toggle source

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

# File lib/stable-matching/roommate.rb, line 67
def initialize(preference_table, opts = {})
  @orig_preference_table = preference_table
  set_logger(opts)
end
solve!(preference_table) click to toggle source

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.

# File lib/stable-matching/roommate.rb, line 49
def self.solve!(preference_table)
  new(preference_table).solve!
end

Public Instance Methods

solve!() click to toggle source

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

build_solution() click to toggle source
# 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
preference_table() click to toggle source
# File lib/stable-matching/roommate.rb, line 110
def preference_table
  @preference_table ||= PreferenceTable.new(@orig_preference_table)
end
validate!() click to toggle source
# File lib/stable-matching/roommate.rb, line 106
def validate!
  Validator.validate!(@orig_preference_table)
end