class GraphMatching::Algorithm::MWMBipartite
`MWMBipartite` implements Maximum Weighted Matching
in bipartite graphs. It extends Maximum Cardinality Matching
for `Weighted` graphs.
> In each stage we look for an augmenting path, as in the simple algorithm > for Problem 1 [Maximum Cardinality Matching], except that we use only > edges with zero slack. (Galil, 1986, p. 30)
Public Class Methods
new(graph)
click to toggle source
Calls superclass method
GraphMatching::Algorithm::MCMBipartite::new
# File lib/graph_matching/algorithm/mwm_bipartite.rb, line 17 def initialize(graph) assert(graph).is_a(Graph::WeightedBigraph) super # Optimization: Keeping a reference to the graph's weights # in the instance, instead of calling `Weighted#w` # thousands of times, is twice as fast. @weight = graph.weight end
Public Instance Methods
match()
click to toggle source
# File lib/graph_matching/algorithm/mwm_bipartite.rb, line 27 def match m = [] dogs, cats = g.partition u = init_duals(cats, dogs) # For each stage loop do # Clear all labels and marks # Label all single dogs with S aug_path = nil predecessors = {} t = Set.new s = Set.new(dogs) - m q = s.dup.to_a # While searching loop do break unless aug_path.nil? i = q.pop break unless i # Follow the unmatched edges (if any) to free (unlabeled) # cats. Only consider edges with slack (π) of 0. unlabeled_across_unmatched_edges_from(i, g, m, t).each do |j| next unless slack(u, i, j) == 0 t << j predecessors[j] = i # If `j` has matched edges (other than the one we just traversed, # `i`) then follow each to a dog and label the dog with S. # Otherwise, backtrack to construct an augmenting path. m_dogs = matched_adjacent(j, i, g, m) m_dogs.each do |md| s << md q << md predecessors[md] = j end if m_dogs.empty? aug_path = backtrack_from(j, predecessors) break end end end # We have looked at every S-dog. # If no `aug_path` was found, the search failed. # Adjust the duals and search again. if aug_path.nil? d1 = calc_d1(s, u) d2 = calc_d2(s, t, u) d = [d1, d2].compact.min # If d == d1, then the smallest dual is equal to the # smallest slack, and the duals of all single dogs are # zero. Therefore, we're totally done. # # Otherwise, adjust the duals by subtracting d from S-dog # duals and adding d to T-cat duals. if d == d1 break else s.each do |si| u[si] = u[si] - d end t.each do |ti| u[ti] = u[ti] + d end end else m = augment(m, aug_path) end end Matching.gabow(m) end
Private Instance Methods
assert_weighted_bipartite(graph)
click to toggle source
# File lib/graph_matching/algorithm/mwm_bipartite.rb, line 104 def assert_weighted_bipartite(graph) unless weighted_bipartite?(graph) raise ArgumentError, 'Expected a weighted bipartite graph' end end
calc_d1(s, u)
click to toggle source
Returns d1, min of S-dog duals
# File lib/graph_matching/algorithm/mwm_bipartite.rb, line 111 def calc_d1(s, u) u.values_at(*s).min end
calc_d2(s, t, u)
click to toggle source
Returns d2, the smallest slack between S-dogs and free cats. This is a fairly expensive method, due to the nested loop.
# File lib/graph_matching/algorithm/mwm_bipartite.rb, line 118 def calc_d2(s, t, u) slacks = [] s.each do |s_dog| g.each_adjacent(s_dog) do |cat| unless t.include?(cat) slacks.push slack(u, s_dog, cat) end end end slacks.min end
init_duals(cats, dogs)
click to toggle source
Initialize the “dual” values
# File lib/graph_matching/algorithm/mwm_bipartite.rb, line 131 def init_duals(cats, dogs) u = [] ui = g.max_w dogs.each do |i| u[i] = ui end cats.each do |j| u[j] = 0 end u end
slack(u, i, j)
click to toggle source
Returns the “slack” of an edge (Galil, 1986, p.30), the difference between an edge's duals and its weight.
# File lib/graph_matching/algorithm/mwm_bipartite.rb, line 145 def slack(u, i, j) u[i] + u[j] - @weight[i - 1][j - 1] end
weighted_bipartite?(graph)
click to toggle source
# File lib/graph_matching/algorithm/mwm_bipartite.rb, line 139 def weighted_bipartite?(graph) graph.respond_to?(:partition) && graph.respond_to?(:w) end