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.



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

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

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



99
100
101
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 99

def edges
  @edges
end

#graph ⇒ Object (readonly)

Returns the value of attribute graph.



99
100
101
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 99

def graph
  @graph
end

Instance Method Details

#add_edge(edge) ⇒ Object 



126
127
128
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 126

def add_edge(edge)
  edges << edge
end

#apply_alternating_path(path) ⇒ Object 



134
135
136
137
138
 
# 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) ⇒ Object 



130
131
132
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 130

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

#edge_for(node) ⇒ Object 



106
107
108
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


110
111
112
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 110

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

#perfect? ⇒ Boolean

Returns:

  • (Boolean) 


118
119
120
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 118

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

#sources ⇒ Object 



114
115
116
 
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 114

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

#weight ⇒ Object 



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

def weight
  edges.inject(0) {|sum, e| sum + e.weight }
end