Class: BipartiteGraph::HungarianAlgorithm
- Inherits:
-
Object
- Object
- BipartiteGraph::HungarianAlgorithm
- Defined in:
- lib/bipartite_graph/hungarian_algorithm.rb
Defined Under Namespace
Instance Attribute Summary collapse
-
#graph ⇒ Object
readonly
Returns the value of attribute graph.
-
#labelling ⇒ Object
readonly
Returns the value of attribute labelling.
-
#matching ⇒ Object
readonly
Returns the value of attribute matching.
-
#original_graph ⇒ Object
readonly
Returns the value of attribute original_graph.
Instance Method Summary collapse
- #add_to_matching(root) ⇒ Object
- #augment_labelling_using(tree) ⇒ Object
- #create_initial_matching ⇒ Object
- #equality_graph ⇒ Object
-
#initialize(graph) ⇒ HungarianAlgorithm
constructor
A new instance of HungarianAlgorithm.
- #restricted_matching(matching, graph) ⇒ Object
- #solution ⇒ Object
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 |