Class: BipartiteGraph::HungarianAlgorithm

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

Defined Under Namespace

Classes: Labelling, Matching

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ HungarianAlgorithm

Returns a new instance of HungarianAlgorithm.



5
6
7
8
9
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 5

def initialize(graph)
  @graph = 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

Instance Method Details

#add_to_matching(root) ⇒ Object 



125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 125

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 



149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 149

def augment_labelling_using(tree)
  target_edges = graph.edges.from(tree.sources).not_to(tree.sinks)

  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 



12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 12

def create_initial_matching
  eq_graph = labelling.equality_graph

  matching = Matching.new(graph)

  eq_graph.sources.each do |source|
    eq_graph.edges.from(source).each do |edge|
      included = matching.has_node?(edge.to)

      if !included
        matching.add_edge(edge)
        next
      end
    end
  end
  matching
end

#equality_graph ⇒ Object 



121
122
123
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 121

def equality_graph
  labelling.equality_graph
end

#solution ⇒ Object 



112
113
114
115
116
117
118
119
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 112

def solution
  while !matching.perfect?
    root = (graph.sources - matching.sources).first
    add_to_matching(root)
  end

  matching
end