class BipartiteGraph::HungarianAlgorithm::Matching

Attributes

edges[R]
graph[R]

Public Class Methods

new(graph) click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 101
def initialize(graph)
  @graph = graph
  @edges = EdgeSet.new
end

Public Instance Methods

add_edge(edge) click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 126
def add_edge(edge)
  edges << edge
end
apply_alternating_path(path) click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 134
def apply_alternating_path(path)
  path.each_with_index do |edge, i|
    i.even? ? add_edge(edge) : delete_edge(edge)
  end
end
delete_edge(edge) click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 130
def delete_edge(edge)
  edges.delete(edge)
end
edge_for(node) click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 106
def edge_for(node)
  @edges.find {|edge| edge.to == node || edge.from == node }
end
has_node?(node) click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 110
def has_node?(node)
  !!edge_for(node)
end
perfect?() click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 118
def perfect?
  2 * edges.length == graph.nodes.length
end
sources() click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 114
def sources
  graph.sources.select {|node| has_node?(node) }
end
weight() click to toggle source
# File lib/bipartite_graph/hungarian_algorithm.rb, line 122
def weight
  edges.inject(0) {|sum, e| sum + e.weight }
end