Method: GraphMatching::Algorithm::MWMGeneral#match

Defined in:
lib/graph_matching/algorithm/mwm_general.rb

#match(max_cardinality) ⇒ Object

> As in Problem 3, the algorithm consists of O(n) stages. > In each stage we look for an augmenting path using the > labeling R12 and the two cases C1, C2 as in the simple > algorithm for Problem 2, except that we only use edges > with π<sub>ij</sub> = 0. (Galil, 1986, p. 32)

Van Rantwijk’s implementation (and, consequently, this port) supports both maximum cardinality maximum weight matching and MWM irrespective of cardinality.



40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/graph_matching/algorithm/mwm_general.rb', line 40

def match(max_cardinality)
  return Matching.new if g.num_edges == 0

  # Iterative *stages*.  Each stage augments the matching.
  # There can be at most n stages, where n is num. vertexes.
  loop do
    init_stage

    # *sub-stages* either augment or scale the duals.
    augmented = false
    loop do
      # > The search is conducted by scanning the S-vertices
      # > in turn. (Galil, 1986, p. 26)
      until augmented || @queue.empty?
        augmented = scan_vertex(@queue.pop)
      end

      break if augmented

      # > There is no augmenting path under these constraints;
      # > compute delta and reduce slack in the optimization problem.
      # > (Van Rantwijk, mwmatching.py, line 732)
      delta, d_type, d_edge, d_blossom = calc_delta(max_cardinality)
      update_duals(delta)
      optimum = act_on_minimum_delta(d_type, d_edge, d_blossom)
      break if optimum
    end

    # > Stop when no more augmenting path can be found.
    # > (Van Rantwijk, mwmatching.py)
    break unless augmented

    expand_tight_s_blossoms
  end

  Matching.from_endpoints(@endpoint, @mate)
end