Package com.crawljax.stateabstractions.dom.apted.distance

Class AllPossibleMappingsTED<C extends CostModel,​D>

  • Type Parameters:
    C - type of cost model.
    D - type of node data.
    public class AllPossibleMappingsTED<C extends CostModel,​D>
extends Object
    Implements an exponential algorithm for the tree edit distance. It computes all possible TED mappings between two trees and calculated their minimal cost.

    • Field Detail

      • it2

        private NodeIndexer it2
        Indexer of the destination tree.

      • size1

        private int size1
        The size of the source input tree.

      • size2

        private int size2
        The size of the destination tree.

      • costModel

        private final C extends CostModel costModel
        Cost model to be used for calculating costs of edit operations.

    • Constructor Detail

      • AllPossibleMappingsTED

        public AllPossibleMappingsTED​(C costModel)
        Constructs the AllPossibleMappingsTED algorithm with a specific cost model.
        Parameters:
        costModel - a cost model used in the algorithm.

    • Method Detail

      • computeEditDistance

        public float computeEditDistance​(AptedNode<D> t1,
                                 AptedNode<D> t2)
        Computes the tree edit distance between two trees by trying all possible TED mappings. It uses the specified cost model.
        Parameters:
        t1 - source tree.
        t2 - destination tree.
        Returns:
        the tree edit distance between two trees.

      • init

        public void init​(AptedNode<D> t1,
                 AptedNode<D> t2)
        Indexes the input trees.
        Parameters:
        t1 - source tree.
        t2 - destination tree.

      • generateAllOneToOneMappings

        private ArrayList<ArrayList<int[]>> generateAllOneToOneMappings()
        Generate all possible 1-1 mappings.

        These mappings do not conform to TED conditions (sibling-order and ancestor-descendant).

        A mapping is a list of pairs (arrays) of preorder IDs (identifying nodes).

        Returns:
        set of all 1-1 mappings.

      • removeNonTEDMappings

        private void removeNonTEDMappings​(ArrayList<ArrayList<int[]>> mappings)
        Given all 1-1 mappings, discard these that violate TED conditions (ancestor-descendant and sibling order).
        Parameters:
        mappings - set of all 1-1 mappings.

      • isTEDMapping

        boolean isTEDMapping​(ArrayList<int[]> m)
        Test if a 1-1 mapping is a TED mapping.
        Parameters:
        m - a 1-1 mapping.
        Returns:
        true if m is a TED mapping, and false otherwise.

      • getMinCost

        float getMinCost​(ArrayList<ArrayList<int[]>> tedMappings)
        Given list of all TED mappings, calculate the cost of the minimal-cost mapping.
        Parameters:
        tedMappings - set of all TED mappings.
        Returns:
        the minimal cost among all TED mappings.

      • deepMappingCopy

        private ArrayList<int[]> deepMappingCopy​(ArrayList<int[]> mapping)
        Makes a deep copy of a mapping.
        Parameters:
        mapping - mapping to copy.
        Returns:
        a mapping.

      • deepMappingsCopy

        private ArrayList<ArrayList<int[]>> deepMappingsCopy​(ArrayList<ArrayList<int[]>> mappings)
        Makes a deep copy of a set of mappings.
        Parameters:
        mappings - set of mappings to copy.
        Returns:
        set of mappings.

      • mappingsToString

        private String mappingsToString​(ArrayList<ArrayList<int[]>> mappings)
        Constructs a string representation of a set of mappings.
        Parameters:
        mappings - set of mappings to convert.
        Returns:
        string representation of a set of mappings.

      • removeMappingElement

        private void removeMappingElement​(ArrayList<int[]> m,
                                  int[] e)
        Removes an element (edit operation) from a mapping by its value. In our case the element to remove can be always found in the mapping.
        Parameters:
        m - an edit mapping.
        e - element to remove from m.