class BipartiteGraph::HungarianAlgorithm
Attributes
graph[R]
labelling[R]
matching[R]
original_graph[R]
Public Class Methods
new(graph)
click to toggle source
# 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
Public Instance Methods
add_to_matching(root)
click to toggle source
# 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)
click to toggle source
# 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()
click to toggle source
# 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()
click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 141 def equality_graph labelling.equality_graph end
restricted_matching(matching, graph)
click to toggle source
# 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()
click to toggle source
# 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