001/**
002 * Copyright (C) 2007 - 2016, Jens Lehmann
003 *
004 * This file is part of DL-Learner.
005 *
006 * DL-Learner is free software; you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation; either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * DL-Learner is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
018 */
019package org.dllearner.algorithms.qtl.heuristics;
020
021import java.util.List;
022
023import org.dllearner.algorithms.qtl.QueryTreeUtils;
024import org.dllearner.algorithms.qtl.datastructures.impl.RDFResourceTree;
025import org.dllearner.algorithms.qtl.operations.lgg.LGGGenerator;
026import org.dllearner.algorithms.qtl.operations.lgg.LGGGeneratorSimple;
027
028public class QueryTreeEditDistance {
029
030    public static <T> double getDistance(RDFResourceTree tree1, RDFResourceTree tree2) {
031        double distance = 0;
032
033        // compare root node
034        // null vs. null
035        if (tree1 == null && tree2 == null) {
036            return distance;
037
038        // null vs. node
039        } else if (tree1 == null) {
040            distance += 1;
041            for (RDFResourceTree child : tree2.getChildren()) {
042                distance += getDistance(null, child);
043            }
044            return distance;
045
046        // node vs. null
047        } else if (tree2 == null) {
048            distance += 1;
049            for (RDFResourceTree child : tree1.getChildren()) {
050                distance += getDistance(child, null);
051            }
052            return distance;
053
054        // node vs. node
055        } else {
056            distance += tree1.getData().equals(tree2.getData()) ? 0 : 1;
057        }
058
059        List<RDFResourceTree> tree1queue = tree1.getChildren();
060        List<RDFResourceTree> tree2queue = tree2.getChildren();
061
062        // make tree1queue the longer queue
063        if (tree1queue.size() < tree2queue.size()) {
064            List<RDFResourceTree> tmp = tree1queue;
065            tree1queue = tree2queue;
066            tree2queue = tmp;
067        }
068
069        while (tree1queue.size() > 0) {
070            double minDistance = Double.MAX_VALUE;
071            RDFResourceTree minDistanceTree1Child = null;
072            RDFResourceTree minDistanceTree2Child = null;
073
074            // try all combinations of tree 1 and tree 2 children and chose
075            // those with the smallest distance as 'match'
076            for (RDFResourceTree queryTree1 : tree1queue) {
077                double tmpDistance;
078
079                // case 1: tree 2 queue is empty:
080                if (tree2queue.isEmpty()) {
081                    tmpDistance = getDistance(queryTree1, null);
082
083                    if (tmpDistance < minDistance) {
084                        minDistance = tmpDistance;
085                        minDistanceTree1Child = queryTree1;
086                    }
087
088                // case 2: tree 2 queue is not empty:
089                } else {
090                    for (RDFResourceTree queryTree2 : tree2queue) {
091                        tmpDistance = getDistance(queryTree1, queryTree2);
092
093                        if (tmpDistance <= minDistance) {
094                            minDistance = tmpDistance;
095                            minDistanceTree1Child = queryTree1;
096                            minDistanceTree2Child = queryTree2;
097                        }
098                    }
099                }
100            }
101
102            distance += minDistance;
103            tree1queue.remove(minDistanceTree1Child);
104            if (minDistanceTree2Child != null) {
105                tree2queue.remove(minDistanceTree2Child);
106            }
107        }
108
109        return distance;
110    }
111
112    /**
113     * Returns a distance between <code>tree1</code> and <code>tree2</code> based
114     *  on the LGG of both.
115     * @param tree1
116     * @param tree2
117     * @return
118     */
119        public static <T> double getDistanceApprox(RDFResourceTree tree1, RDFResourceTree tree2) {
120                LGGGenerator lggGenerator = new LGGGeneratorSimple();
121
122                // compute the LGG of tree1 and tree2
123                RDFResourceTree lgg = lggGenerator.getLGG(tree1, tree2);
124
125                // we define the distance as the maximum difference between the complexity
126                // of tree1 to LGG and tree2 to LGG
127                double complexityLGG = QueryTreeUtils.getComplexity(lgg);
128                double complexityTree1 = QueryTreeUtils.getComplexity(tree1);
129                double complexityTree2 = QueryTreeUtils.getComplexity(tree2);
130
131                double distance = Math.max(
132                                complexityTree1 - complexityLGG,
133                                complexityTree2 - complexityLGG);
134
135//              System.out.println(tree1.getStringRepresentation());
136//              System.out.println(complexityTree1);
137//              System.out.println(tree2.getStringRepresentation());
138//              System.out.println(complexityTree2);
139//              System.out.println(lgg.getStringRepresentation());
140//              System.out.println(complexityLGG);
141                return distance;
142        }
143}