Class: GraphMatching::Algorithm::MWMGeneral

Inherits:
MatchingAlgorithm show all
Defined in:
lib/graph_matching/algorithm/mwm_general.rb

Overview

‘MWMGeneral` implements Maximum Weighted Matching in general graphs.

Constant Summary collapse

LBL_FREE =

If b is a top-level blossom, label is 0 if b is unlabeled (free);

1 if b is an S-vertex/blossom;
2 if b is a T-vertex/blossom.

0
LBL_S = 
1
LBL_T = 
2
LBL_CRUMB = 
5
LBL_NAMES = 
%w[Free S T Crumb].freeze

Instance Attribute Summary

Attributes inherited from MatchingAlgorithm

#g

Instance Method Summary collapse

Methods inherited from MatchingAlgorithm

#assert

Constructor Details

#initialize(graph) ⇒ MWMGeneral

Returns a new instance of MWMGeneral.



22
23
24
25
26
27
 
# File 'lib/graph_matching/algorithm/mwm_general.rb', line 22

def initialize(graph)
  assert(graph).is_a(Graph::WeightedGraph)
  super
  init_graph_structures
  init_algorithm_structures
end

Instance Method Details

#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.



38
39
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
 
# File 'lib/graph_matching/algorithm/mwm_general.rb', line 38

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