Class: BipartiteGraph::HungarianAlgorithm::Labelling

Inherits:
Object
  • Object
show all
Defined in:
lib/bipartite_graph/hungarian_algorithm.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ Labelling 



55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
# 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

Instance Attribute Details

#equality_graph ⇒ Object (readonly)

subgraph of edges where weight = sum of end labels



53
54
55
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 53

def equality_graph
  @equality_graph
end

#graph ⇒ Object (readonly)

subgraph of edges where weight = sum of end labels



53
54
55
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 53

def graph
  @graph
end

#labels ⇒ Object (readonly)

subgraph of edges where weight = sum of end labels



53
54
55
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 53

def labels
  @labels
end

Instance Method Details

#label_for(node) ⇒ Object 



73
74
75
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 73

def label_for(node)
  @labels[node]
end

#recalculate_equality_graph ⇒ Object 



81
82
83
84
85
86
87
 
# 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 ⇒ Object 



77
78
79
 
# 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) ⇒ Object 



89
90
91
92
93
94
95
 
# 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