Class: GraphMatching::Algorithm::MWMBipartite

Inherits:
MCMBipartite show all
Defined in:
lib/graph_matching/algorithm/mwm_bipartite.rb

Overview

‘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)

Instance Attribute Summary

Attributes inherited from MatchingAlgorithm

#g

Instance Method Summary collapse

Methods inherited from MatchingAlgorithm

#assert

Constructor Details

#initialize(graph) ⇒ MWMBipartite

Returns a new instance of MWMBipartite.



17
18
19
20
21
22
23
24
25
 
# 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

Instance Method Details

#match ⇒ Object 



27
28
29
30
31
32
33
34
35
36
37
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
# 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