Class: Hungarian

Inherits:
Object
  • Object
show all
Defined in:
lib/hungarian.rb

Overview

Written by: Evan Senter

          • U S A G E - - - - -

hungarian = Hungarian.new(matrix_to_solve) solution = hungarian.solve

…or…

hungarian = Hungarian.new solution = hungarian.solve(matrix_to_solve)

The method solve returns an array of cell locations such that the assignment problem is solved. See en.wikipedia.org/wiki/Hungarian_algorithm for more information on this problem.

Adapted from: www.public.iastate.edu/~ddoty/HungarianAlgorithm.html

Constant Summary collapse

EMPTY = 
0
STAR = 
1
PRIME = 
2

Instance Method Summary collapse

Constructor Details

#initialize(matrix = nil) ⇒ Hungarian

Returns a new instance of Hungarian.



23
 
# File 'lib/hungarian.rb', line 23

def initialize(matrix = nil); setup(matrix) if matrix; end

Instance Method Details

#solve(matrix = nil) ⇒ Object

Raises:

  • (ArgumentError) 


25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/hungarian.rb', line 25

def solve(matrix = nil)
  setup(matrix) if matrix
  raise(ArgumentError, "You must provide a matrix to solve.") unless @matrix
  
  method = :minimize_rows
  while method != :finished
    method = self.send(*method)
  end
  
  return assignment
end