Class: BipartiteGraph::HungarianAlgorithm
- Inherits:
-
Object
- Object
- BipartiteGraph::HungarianAlgorithm
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
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
Returns the value of attribute graph.
3
4
5
|
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 3
def graph
@graph
end
|
#labelling ⇒ Object
Returns the value of attribute labelling.
3
4
5
|
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 3
def labelling
@labelling
end
|
#matching ⇒ Object
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
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
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
|