Class: BipartiteGraph::HungarianAlgorithm::Matching
- Inherits:
-
Object
- Object
- BipartiteGraph::HungarianAlgorithm::Matching
- Defined in:
- lib/bipartite_graph/hungarian_algorithm.rb
Instance Attribute Summary collapse
-
#edges ⇒ Object
readonly
Returns the value of attribute edges.
-
#graph ⇒ Object
readonly
Returns the value of attribute graph.
Instance Method Summary collapse
- #add_edge(edge) ⇒ Object
- #apply_alternating_path(path) ⇒ Object
- #delete_edge(edge) ⇒ Object
- #edge_for(node) ⇒ Object
- #has_node?(node) ⇒ Boolean
-
#initialize(graph) ⇒ Matching
constructor
A new instance of Matching.
- #perfect? ⇒ Boolean
- #sources ⇒ Object
- #weight ⇒ Object
Constructor Details
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
110 111 112 |
# File 'lib/bipartite_graph/hungarian_algorithm.rb', line 110 def has_node?(node) !!edge_for(node) end |
#perfect? ⇒ 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 |