Module: GraphMatching::Algorithm::MWMGDeltaAssertions

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

Overview

Can be mixed into MWMGeneral to add runtime assertions about the data structures used for delta2/delta3 calculations.

> Check delta2/delta3 computation after every substage; > only works on integer weights, slows down the algorithm to O(n^4). > (Van Rantwijk, mwmatching.py, line 34)

Instance Method Summary collapse

Instance Method Details

#calc_delta_with_assertions(*args) ⇒ Object 



13
14
15
16
17
18
19
 
# File 'lib/graph_matching/algorithm/mwmg_delta_assertions.rb', line 13

def calc_delta_with_assertions(*args)
  # > Verify data structures for delta2/delta3 computation.
  # > (Van Rantwijk, mwmatching.py, line 739)
  check_delta2
  check_delta3
  calc_delta_without_assertions(*args)
end

#check_delta2 ⇒ Object

> Check optimized delta2 against a trivial computation. > (Van Rantwijk, mwmatching.py, line 580)



23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/graph_matching/algorithm/mwmg_delta_assertions.rb', line 23

def check_delta2
  (0...@nvertex).each do |v|
    next unless @label[@in_blossom[v]] == MWMGeneral::LBL_FREE
    bd = nil
    bk = nil
    @neighb_end[v].each do |p|
      k = p / 2 # Note: floor division
      w = @endpoint[p]
      next unless @label[@in_blossom[w]] == MWMGeneral::LBL_S
      d = slack(k)
      if bk.nil? || d < bd
        bk = k
        bd = d
      end
    end
    option1 = bk.nil? && @best_edge[v].nil?
    option2 = !@best_edge[v].nil? && bd == slack(@best_edge[v])
    unless option1 || option2
      raise "Assertion failed: Free vertex #{v}"
    end
  end
end

#check_delta3 ⇒ Object

> Check optimized delta3 against a trivial computation. > (Van Rantwijk, mwmatching.py, line 598)



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
 
# File 'lib/graph_matching/algorithm/mwmg_delta_assertions.rb', line 48

def check_delta3
  bk = nil
  bd = nil
  tbk = nil
  tbd = nil
  (0...2 * @nvertex).each do |b|
    next unless @blossom_parent[b].nil? && @label[b] == MWMGeneral::LBL_S
    blossom_leaves(b).each do |v|
      @neighb_end[v].each do |p|
        k = p / 2 # Note: floor division
        w = @endpoint[p]
        unless @in_blossom[w] != b &&
            @label[@in_blossom[w]] == MWMGeneral::LBL_S
          next
        end
        d = slack(k)
        if bk.nil? || d < bd
          bk = k
          bd = d
        end
      end
    end
    next if @best_edge[b].nil?
    i, j = @edges[@best_edge[b]].to_a
    unless @in_blossom.values_at(i, j).include?(b)
      raise 'Assertion failed'
    end
    unless @in_blossom[i] != b || @in_blossom[j] != b
      raise 'Assertion failed'
    end
    unless @label[@in_blossom[i]] == MWMGeneral::LBL_S &&
        @label[@in_blossom[j]] == MWMGeneral::LBL_S
      raise 'Assertion failed'
    end
    if tbk.nil? || slack(@best_edge[b]) < tbd
      tbk = @best_edge[b]
      tbd = slack(@best_edge[b])
    end
  end
  unless bd == tbd
    raise 'Assertion failed'
  end
end