module GraphMatching::Algorithm::MWMGDeltaAssertions

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)

Public Instance Methods

calc_delta_with_assertions(*args) click to toggle source
# 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() click to toggle source

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

# 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() click to toggle source

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

# 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