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.operations.nbr.strategy;
020
021import java.util.ArrayList;
022import java.util.Collections;
023import java.util.HashSet;
024import java.util.List;
025import java.util.Set;
026
027import org.apache.log4j.Logger;
028import org.dllearner.algorithms.qtl.QueryTreeUtils;
029import org.dllearner.algorithms.qtl.datastructures.impl.RDFResourceTree;
030
031import org.apache.jena.graph.Node;
032
033/**
034 * 
035 * @author Lorenz Bühmann
036 *
037 */
038public class BruteForceNBRStrategy implements NBRStrategy {
039        
040        private static final Logger logger = Logger.getLogger(BruteForceNBRStrategy.class);
041
042        @Override
043        public RDFResourceTree computeNBR(RDFResourceTree posExampleTree, List<RDFResourceTree> negExampleTrees) {
044                logger.info("Making NBR on");
045                logger.info(posExampleTree.getStringRepresentation());
046                logger.info("with negative examples");
047                for(RDFResourceTree tree : negExampleTrees){
048                        logger.info(tree.getStringRepresentation());
049                }
050                
051                RDFResourceTree nbr = new RDFResourceTree(posExampleTree);
052                if(subsumesTrees(posExampleTree, negExampleTrees)){
053                        logger.info("Warning: Positive example already covers all negative examples. Skipping NBR computation...");
054                        return nbr;
055                }
056                
057                Set<RDFResourceTree> tested = new HashSet<>();
058                Node edge;
059                RDFResourceTree parent;
060                while(!(tested.size() == nbr.getLeafs().size()) ){
061                        for(RDFResourceTree leaf : nbr.getLeafs()){
062                                if(leaf.isRoot()){
063                                        return nbr;
064                                }
065                                parent = leaf.getParent();
066                                edge = parent.getEdgeToChild(leaf);
067                                parent.removeChild(leaf);
068                                boolean isSubsumedBy = false;
069                                for(RDFResourceTree negTree : negExampleTrees){
070                                        isSubsumedBy = QueryTreeUtils.isSubsumedBy(negTree, nbr);
071                                        if(isSubsumedBy){
072                                                break;
073                                        }
074                                }
075                                if(isSubsumedBy){
076                                        tested.add(leaf);
077                                        parent.addChild(leaf, edge);
078                                }
079                                
080                        }
081                }
082                return nbr;
083        }
084
085        @Override
086        public List<RDFResourceTree> computeNBRs(RDFResourceTree posExampleTree,
087                        List<RDFResourceTree> negExampleTrees) {
088                logger.info("Making NBR on");
089                logger.info(posExampleTree.getStringRepresentation());
090                logger.info("with negative examples");
091                for(RDFResourceTree tree : negExampleTrees){
092                        logger.info(tree.getStringRepresentation());
093                }
094                
095                if(subsumesTrees(posExampleTree, negExampleTrees)){
096                        logger.info("Warning: Positive example already covers all negative examples. Skipping NBR computation...");
097                        return Collections.singletonList(posExampleTree);
098                }
099                
100                List<RDFResourceTree> nbrs = new ArrayList<>();
101                
102                compute(posExampleTree, negExampleTrees, nbrs);
103                
104                return nbrs;
105        }
106        
107        private void compute(RDFResourceTree posExampleTree,
108                        List<RDFResourceTree> negExampleTrees, List<RDFResourceTree> nbrs) {
109                
110                RDFResourceTree nbr = new RDFResourceTree(posExampleTree);
111                if(subsumesTrees(posExampleTree, negExampleTrees)){
112//                      nbrs.add(posExampleTree);
113                        return;
114                }
115                
116                for(RDFResourceTree n : nbrs){
117                        removeTree(nbr, n);
118                }
119                
120                if(!subsumesTrees(nbr, negExampleTrees)){
121                        Set<RDFResourceTree> tested = new HashSet<>();
122                        Node edge;
123                        RDFResourceTree parent;
124                        while(!(tested.size() == nbr.getLeafs().size()) ){
125                                for(RDFResourceTree leaf : nbr.getLeafs()){
126                                        parent = leaf.getParent();
127                                        edge = parent.getEdgeToChild(leaf);
128                                        parent.removeChild(leaf);
129                                        boolean isSubsumedBy = false;
130                                        for(RDFResourceTree negTree : negExampleTrees){
131                                                isSubsumedBy = QueryTreeUtils.isSubsumedBy(negTree, nbr);
132                                                if(isSubsumedBy){
133                                                        break;
134                                                }
135                                        }
136                                        if(isSubsumedBy){
137                                                tested.add(leaf);
138                                                parent.addChild(leaf, edge);
139                                        }
140                                        
141                                }
142                        }
143                        nbrs.add(nbr);
144                        compute(posExampleTree, negExampleTrees, nbrs);
145                        
146                }
147                
148        }
149        
150        private boolean subsumesTrees(RDFResourceTree posExampleTree,
151                        List<RDFResourceTree> negExampleTrees){
152                
153                for(RDFResourceTree negTree : negExampleTrees){
154                        boolean subsumesTree = QueryTreeUtils.isSubsumedBy(negTree, posExampleTree);
155                        if(subsumesTree){
156                                return true;
157                        }
158                }
159                return false;
160        }
161        
162        private void removeTree(RDFResourceTree tree, RDFResourceTree node){
163                for(RDFResourceTree child1 : node.getChildren()){
164                        Node edge = node.getEdgeToChild(child1);
165                        for(RDFResourceTree child2 : tree.getChildren(edge)){
166                                if(child1.isLeaf() && child1.getData().equals(child2.getData())){
167                                        child2.getParent().removeChild(child2, edge);
168                                } else {
169                                        removeTree(child2, child1);
170                                }
171                        }
172                }
173        }
174
175}