class HungarianAlgorithm
Constants
- VERSION
Attributes
matrix[RW]
Public Class Methods
new(nested_array)
click to toggle source
users.cs.duke.edu/~brd/Teaching/Bio/asmb/current/Handouts/munkres.html
# File lib/hungarian_algorithm.rb, line 9 def initialize(nested_array) @matrix = Matrix[*nested_array] @mask_matrix = Matrix.zero(matrix_size) @covered_rows = Array.new(matrix_size, 0) @covered_columns = Array.new(matrix_size, 0) validate end
Public Instance Methods
process()
click to toggle source
# File lib/hungarian_algorithm.rb, line 18 def process p 'Hungarian algo start' minimize_rows star_zeros p 'Hungarian algo end' stars end
Private Instance Methods
assignment_done?()
click to toggle source
# File lib/hungarian_algorithm.rb, line 104 def assignment_done? solved_assigments = @covered_columns.select { |v| v == 1 }.size solved_assigments == matrix_size end
cover_stars()
click to toggle source
# File lib/hungarian_algorithm.rb, line 91 def cover_stars p 'Step 3: cover columns with stars' on_each_mask_cell do |cell, i, j| next unless cell == 1 @covered_columns[j] = 1 end return if assignment_done? prime_zeros end
matrix_size()
click to toggle source
# File lib/hungarian_algorithm.rb, line 56 def matrix_size @matrix_size ||= matrix.row_vectors.size end
minimize_rows()
click to toggle source
Step 1 : Minimize rows/columns
# File lib/hungarian_algorithm.rb, line 61 def minimize_rows p 'Step 1: Minimizing rows' @matrix.row_vectors.each_with_index do |row, i| min = row.min next if min.zero? row.each_with_index { |cell, j| matrix[i, j] = cell - min } end end
minimize_uncovered_values()
click to toggle source
# File lib/hungarian_algorithm.rb, line 180 def minimize_uncovered_values p 'Step 6: Minimize uncovered cells' on_each_cell do |cell, i, j| @matrix[i, j] += @uncovered_min if @covered_rows[i] == 1 @matrix[i, j] -= @uncovered_min if @covered_columns[j] == 0 end prime_zeros end
on_each_cell() { |cell, i, j| ... }
click to toggle source
# File lib/hungarian_algorithm.rb, line 34 def on_each_cell @matrix.each_with_index { |cell, i, j| yield(cell, i, j) } end
on_each_mask_cell() { |cell, i, j| ... }
click to toggle source
# File lib/hungarian_algorithm.rb, line 38 def on_each_mask_cell @mask_matrix.each_with_index { |cell, i, j| yield(cell, i, j) } end
prime_in_row(i)
click to toggle source
# File lib/hungarian_algorithm.rb, line 175 def prime_in_row(i) j = @mask_matrix.row(i).find_index(2) [i, j] unless j.nil? end
prime_zeros()
click to toggle source
# File lib/hungarian_algorithm.rb, line 109 def prime_zeros @uncovered_min ||= matrix.max loop do uncovered_zeros = false p 'Step 4: prime zeros located on rows with starred zeros' on_each_cell do |cell, i ,j| next if @covered_rows[i].nonzero? || @covered_columns[j].nonzero? if cell.nonzero? @uncovered_min = cell if cell < @uncovered_min next end uncovered_zeros = true @mask_matrix[i, j] = 2 if star = star_in_row(i) @covered_rows[i] = 1 @covered_columns[star[1]] = 0 else search_for_optimal_path_from(i, j) return if assignment_done? end end break unless uncovered_zeros end minimize_uncovered_values end
reset_all_primes()
click to toggle source
# File lib/hungarian_algorithm.rb, line 50 def reset_all_primes on_each_mask_cell do |cell, i, j| @mask_matrix[i, j] = 0 if cell == 2 end end
reset_covered_columns()
click to toggle source
# File lib/hungarian_algorithm.rb, line 42 def reset_covered_columns @covered_columns = Array.new(matrix_size, 0) end
reset_covered_rows()
click to toggle source
# File lib/hungarian_algorithm.rb, line 46 def reset_covered_rows @covered_rows = Array.new(matrix_size, 0) end
search_for_optimal_path_from(i, j)
click to toggle source
# File lib/hungarian_algorithm.rb, line 147 def search_for_optimal_path_from(i, j) p 'Step 5: looks for optimal path accross stars and primes' primes_in_path = [[i, j]] stars_in_path = [] loop do if star_after_prime = star_in_column(j) stars_in_path << star_after_prime prime_after_star = prime_in_row(star_after_prime[0]) primes_in_path << prime_after_star i, j = prime_after_star else stars_in_path.each { |i, j| @mask_matrix[i, j] = 0 } primes_in_path.each { |i, j| @mask_matrix[i, j] = 1 } reset_covered_columns reset_covered_rows reset_all_primes break cover_stars end end end
star_cell(i, j)
click to toggle source
# File lib/hungarian_algorithm.rb, line 85 def star_cell(i, j) @mask_matrix[i, j] = 1 @covered_rows[i] = 1 @covered_columns[j] = 1 end
star_in_column(j)
click to toggle source
# File lib/hungarian_algorithm.rb, line 170 def star_in_column(j) i = @mask_matrix.column(j).find_index(1) [i, j] unless i.nil? end
star_in_row(i)
click to toggle source
# File lib/hungarian_algorithm.rb, line 142 def star_in_row(i) j = @mask_matrix.row(i).find_index(1) [i, j] unless j.nil? end
star_zeros()
click to toggle source
Step 2 : Star all zero which are not on a row/coulmn with another already starred zero
# File lib/hungarian_algorithm.rb, line 72 def star_zeros p 'Step 2: star uncovered zeros' on_each_cell do |cell, i, j| next if [@covered_rows[i], @covered_columns[j], cell].any?(&:nonzero?) star_cell(i, j) end reset_covered_columns reset_covered_rows cover_stars end
stars()
click to toggle source
# File lib/hungarian_algorithm.rb, line 191 def stars stars = [] on_each_mask_cell do |cell, i, j| next if cell != 1 stars << [i, j] end stars end
validate()
click to toggle source
# File lib/hungarian_algorithm.rb, line 30 def validate raise NotImplementedError unless matrix.square? end