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}