class BipartiteGraph::HungarianAlgorithm

Attributes

graph[R]
labelling[R]
matching[R]
original_graph[R]

Public Class Methods

new(graph) click to toggle source
# 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

Public Instance Methods

add_to_matching(root) click to toggle source
# 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) click to toggle source
# 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() click to toggle source
# 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() click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 141
def equality_graph
  labelling.equality_graph
end
restricted_matching(matching, graph) click to toggle source
# 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
solution() click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 12
def solution
  while matching.weight != labelling.total
    root = (graph.sources - matching.sources).first
    add_to_matching(root)
  end

  restricted_matching(matching, original_graph)
end