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