Class: BipartiteGraph::HungarianAlgorithm::Matching

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) ⇒ Matching

Returns a new instance of Matching.



76
77
78
79
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 76

def initialize(graph)
  @graph = graph
  @edges = EdgeSet.new
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



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

def edges
  @edges
end

#graph ⇒ Object (readonly)

Returns the value of attribute graph.



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

def graph
  @graph
end

Instance Method Details

#add_edge(edge) ⇒ Object 



97
98
99
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 97

def add_edge(edge)
  edges << edge
end

#apply_alternating_path(path) ⇒ Object 



105
106
107
108
109
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 105

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) ⇒ Object 



101
102
103
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 101

def delete_edge(edge)
  edges.delete(edge)
end

#edge_for(node) ⇒ Object 



81
82
83
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 81

def edge_for(node)
  @edges.find {|edge| edge.to == node || edge.from == node }
end

#has_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


85
86
87
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 85

def has_node?(node)
  !!edge_for(node)
end

#perfect? ⇒ Boolean

Returns:

  • (Boolean) 


93
94
95
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 93

def perfect?
  2 * edges.length == graph.nodes.length
end

#sources ⇒ Object 



89
90
91
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 89

def sources
  graph.sources.select {|node| has_node?(node) }
end