Class: StableMatching::Marriage

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

Overview

Provides a solution to the Stable Marriage problem by implementing the Gale-Shapley algorithm

Takes as input the preferences of two groups - alpha and beta - and produces a mathematically optimal matching/pairing between the two groups.

Example Input:

alpha_preferences = {
  "A" => ["M", "N", "L"],
  "B" => ["N", "M", "L"],
  "C" => ["M", "L", "N"],
}

beta_preferences = {
  "L" => ["B", "C", "A"],
  "M" => ["B", "A", "C"],
  "N" => ["A", "C", "B"],
}

Example Output:

{"A"=>"M", "B"=>"N", "C"=>"L", "L"=>"C", "M"=>"A", "N"=>"B"}

Defined Under Namespace

Classes: PhaseIRunner, PreferenceTable, Validator

Class Method Summary collapse

Instance Method Summary collapse

Methods included from LoggingHelper

#set_logger

Constructor Details

#initialize(alpha_preferences, beta_preferences, opts = {}) ⇒ Marriage

Initializes a ‘StableMatching::Marriage` object.

Inputs:

alpha_preferences

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

beta_preferences

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

opts[:logger]

Logger instance to use for logging

Output:

StableMatching::Marriage instance



77
78
79
80
81
82
83
84
85
 
# File 'lib/stable-matching/marriage.rb', line 77

def initialize(alpha_preferences, beta_preferences, opts = {})
  @orig_alpha_preferences = alpha_preferences
  @orig_beta_preferences = beta_preferences

  @alpha_preferences, @beta_preferences =
    PreferenceTable.initialize_pair(alpha_preferences, beta_preferences)

  set_logger(opts)
end

Class Method Details

.solve!(alpha_preferences, beta_preferences) ⇒ Object

Runs the algorithm with the specified inputs.

This is a class level shortcut to initialize a new StableMatching::Marriage instance and calls solve! on it.

Inputs:

alpha_preferences

A Hash of Array values specifying the preferences of the alpha group

beta_preferences

A Hash of Array values specifying the preferences of the beta group

Output: A Hash mapping alpha members to beta and beta members to alpha members.



56
57
58
 
# File 'lib/stable-matching/marriage.rb', line 56

def self.solve!(alpha_preferences, beta_preferences)
  new(alpha_preferences, beta_preferences).solve!
end

Instance Method Details

#solve! ⇒ Object

Runs the algorithm on the alpha and beta preference sets. Also validates the preference sets and raises an error if invalid.

Output:

A Hash mapping alpha members to beta and beta members to alpha members.

Raises:

StableMatching::InvalidPreferences

When alpha or beta preference groups are of invalid format



98
99
100
101
102
103
104
105
 
# File 'lib/stable-matching/marriage.rb', line 98

def solve!
  validate!

  @logger.info("Running Phase I")
  PhaseIRunner.new(alpha_preferences, beta_preferences, logger: @logger).run

  build_solution
end