class BipartiteGraph::HungarianAlgorithm::Labelling
Attributes
equality_graph[R]
subgraph of edges where weight = sum of end labels
graph[R]
subgraph of edges where weight = sum of end labels
labels[R]
subgraph of edges where weight = sum of end labels
Public Class Methods
new(graph)
click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 55 def initialize(graph) @labels = {} @graph = graph @equality_graph = Subgraph.new(graph) graph.sources.each do |node| edges = graph.edges.from(node) max_weight = edges.map(&:weight).max @labels[node] = max_weight end graph.sinks.each do |node| @labels[node] = 0 end recalculate_equality_graph end
Public Instance Methods
label_for(node)
click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 73 def label_for(node) @labels[node] end
recalculate_equality_graph()
click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 81 def recalculate_equality_graph equality_graph.clear graph.edges.select {|e| e.weight == labels[e.from] + labels[e.to]}.each do |edge| equality_graph.add_edge(edge) end end
total()
click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 77 def total graph.nodes.inject(0) {|sum, node| sum + label_for(node) } end
update(nodes_to_increase, nodes_to_decrease, change)
click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 89 def update(nodes_to_increase, nodes_to_decrease, change) raise "Change must be positive" unless change > 0 nodes_to_increase.each { |n| labels[n] += change } nodes_to_decrease.each { |n| labels[n] -= change } recalculate_equality_graph #could be cleverer about this .. end