Class: Canon::TreeDiff::Matchers::StructuralPropagator

Inherits:
Object
  • Object
show all
Defined in:
lib/canon/tree_diff/matchers/structural_propagator.rb

Overview

StructuralPropagator extends matches using structural relationships

Based on XyDiff/Cobena (2002, INRIA) propagation strategies:

  • Bottom-up: Match parents of matched children

  • Top-down: Match children of matched parents (lazy propagation)

Propagation depth formula: 1 + (W / W₀) where W = node weight, W₀ = base weight threshold

Features:

  • Conservative propagation (only when safe)

  • Weight-based depth control

  • Handles unique child labels

  • Preserves matching constraints

Constant Summary collapse

BASE_WEIGHT_THRESHOLD =

Base weight threshold for propagation depth

10.0

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tree1, tree2, matching) ⇒ StructuralPropagator

Initialize propagator with trees and existing matching

Parameters:

  • tree1 (TreeNode) —

    First tree root

  • tree2 (TreeNode) —

    Second tree root

  • matching (Core::Matching) —

    Existing matching



35
36
37
38
39
 
# File 'lib/canon/tree_diff/matchers/structural_propagator.rb', line 35

def initialize(tree1, tree2, matching)
  @tree1 = tree1
  @tree2 = tree2
  @matching = matching
end

Instance Attribute Details

#matching ⇒ Object (readonly)

Returns the value of attribute matching.



25
26
27
 
# File 'lib/canon/tree_diff/matchers/structural_propagator.rb', line 25

def matching
  @matching
end

#tree1 ⇒ Object (readonly)

Returns the value of attribute tree1.



25
26
27
 
# File 'lib/canon/tree_diff/matchers/structural_propagator.rb', line 25

def tree1
  @tree1
end

#tree2 ⇒ Object (readonly)

Returns the value of attribute tree2.



25
26
27
 
# File 'lib/canon/tree_diff/matchers/structural_propagator.rb', line 25

def tree2
  @tree2
end

Instance Method Details

#propagate ⇒ Core::Matching

Perform structural propagation

Returns:



44
45
46
47
48
49
50
51
52
 
# File 'lib/canon/tree_diff/matchers/structural_propagator.rb', line 44

def propagate
  # Phase 1: Bottom-up propagation
  propagate_bottom_up

  # Phase 2: Top-down propagation
  propagate_top_down

  @matching
end