Class: Munkres

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

Direct Known Subclasses

Problem

Defined Under Namespace

Classes: Problem

Constant Summary collapse

MODE_MINIMIZE_COST = 
1
MODE_MAXIMIZE_UTIL = 
2

Instance Method Summary collapse

Constructor Details

#initialize(matrix = [], mode = MODE_MINIMIZE_COST) ⇒ Munkres

Returns a new instance of Munkres.



5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/munkres.rb', line 5

def initialize(matrix=[], mode=MODE_MINIMIZE_COST)
  @matrix = matrix
  @mode = mode
  @original = Marshal.load(Marshal.dump(@matrix))
  validate_and_pad
  @covered_columns = []
  @covered_rows = []
  @starred_zeros = []
  @primed_zeros = []
  
  class << @matrix
    

    def row(index)
      self[index]
    end

    def column(index)
      self.collect do |row|
        row[index]
      end
    end

    def columns
      result = []
      self.first.each_index do |i|
        result << self.column(i)
      end
      result
    end
    
    def each_column_index &block
      column_indices.each &block
    end
    
    def column_indices
      @column_indices ||= (0...self.first.size).to_a
    end
    
    def row_indices
      @row_indices ||= (0...self.size).to_a
    end
  end
  
end

Instance Method Details

#find_pairings ⇒ Object 



51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/munkres.rb', line 51

def find_pairings
  create_zero_in_rows
  star_zeros
  cover_columns_with_stars
  while not done?
    p = cover_zeros_and_create_more
    find_better_stars p
    #create series
    cover_columns_with_stars
  end
  @pairings = @starred_zeros.delete_if{|row_index,col_index| col_index >= @original.first.size || row_index >= @original.size}
end

#pretty_print ⇒ Object 



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/munkres.rb', line 68

def pretty_print
  print_col_row
  @matrix.each_with_index do |row,row_index|
    print @covered_rows.include?(row_index) ? "-" : " "
    row.each_with_index do |value, col_index|
      print value
      print "*" if @starred_zeros.include? [row_index,col_index]
      print "'" if @primed_zeros.include? [row_index,col_index]
      print "\t"
    end
    print @covered_rows.include?(row_index) ? "-" : " "
    print "\n"
  end
  print_col_row
end

#print_col_row ⇒ Object 



84
85
86
87
88
89
90
91
 
# File 'lib/munkres.rb', line 84

def print_col_row
  print " "
  @matrix.column_indices.each do |col_index|
    print "|" if @covered_columns.include? col_index
    print "\t"
  end
  print "\n"
end

#total_cost_of_pairing ⇒ Object 



64
65
66
 
# File 'lib/munkres.rb', line 64

def total_cost_of_pairing
  @pairings.inject(0) {|total, star| total + @original[star[0]][star[1]]}
end