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