Class: BipartiteGraph::HungarianAlgorithm

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

Defined Under Namespace

Classes: Labelling, Matching

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ HungarianAlgorithm

Returns a new instance of HungarianAlgorithm.



5
6
7
8
9
10
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 5

def initialize(graph)
  @original_graph = graph
  @graph = BipartiteGraph::CompleteGraph.new(graph)
  @labelling = Labelling.new(@graph)
  @matching = create_initial_matching
end

Instance Attribute Details

#graph ⇒ Object (readonly)

Returns the value of attribute graph.



3
4
5
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 3

def graph
  @graph
end

#labelling ⇒ Object (readonly)

Returns the value of attribute labelling.



3
4
5
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 3

def labelling
  @labelling
end

#matching ⇒ Object (readonly)

Returns the value of attribute matching.



3
4
5
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 3

def matching
  @matching
end

#original_graph ⇒ Object (readonly)

Returns the value of attribute original_graph.



3
4
5
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 3

def original_graph
  @original_graph
end

Instance Method Details

#add_to_matching(root) ⇒ Object 



145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 145

def add_to_matching(root)
  tree = AlternatingTree.new(graph, root)
  matching_found = false

  while !matching_found
    new_edge = equality_graph.edges.from(tree.sources).not_to(tree.sinks).first

    if new_edge.nil?
      augment_labelling_using(tree)
    else
      tree.add_edge(new_edge)
      new_sink = new_edge.to

      existing_edge = matching.edge_for(new_sink)
      if existing_edge
        tree.add_edge(existing_edge)
      else
        matching.apply_alternating_path(tree.path_to(new_edge.to))
        matching_found = true
      end
    end
  end
end

#augment_labelling_using(tree) ⇒ Object 



169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 169

def augment_labelling_using(tree)
  target_edges = graph.edges.from(tree.sources).not_to(tree.sinks)

  if target_edges.empty?
    raise "Target edge not found"
  end

  slack = target_edges.map do |edge|
    labelling.label_for(edge.from) + labelling.label_for(edge.to) - edge.weight
  end

  max_decrease = slack.min

  labelling.update(tree.sinks, tree.sources, max_decrease)
end

#create_initial_matching ⇒ Object 



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 31

def create_initial_matching
  eq_graph = labelling.equality_graph

  matching = Matching.new(graph)

  eq_graph.sources.each do |source|
    matched = false
    eq_graph.edges.from(source).each do |edge|
      next if matched
      included = matching.has_node?(edge.to)

      if !included
        matching.add_edge(edge)
        matched = true
      end
    end
  end
  matching
end

#equality_graph ⇒ Object 



141
142
143
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 141

def equality_graph
  labelling.equality_graph
end

#restricted_matching(matching, graph) ⇒ Object 



21
22
23
24
25
26
27
28
29
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 21

def restricted_matching(matching, graph)
  m = Matching.new(graph)

  matching.edges.each do |edge|
    m.add_edge(edge) if edge.weight > 0  # will exclude fake nodes as they're
                                         # only reachable from 0 edges
  end
  m
end

#solution ⇒ Object 



12
13
14
15
16
17
18
19
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 12

def solution
  while matching.weight != labelling.total
    root = (graph.sources - matching.sources).first
    add_to_matching(root)
  end

  restricted_matching(matching, original_graph)
end