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

#edgesObject (readonly)

Returns the value of attribute edges.



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

def edges
  @edges
end

#graphObject (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

#sourcesObject



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

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

#weightObject



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

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