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.utilities.datastructures; 020 021import org.apache.log4j.Level; 022import org.apache.log4j.Logger; 023import org.dllearner.core.AbstractReasonerComponent; 024import org.dllearner.core.EvaluatedDescription; 025import org.dllearner.core.Score; 026import org.dllearner.learningproblems.EvaluatedDescriptionPosNeg; 027import org.dllearner.utilities.owl.OWLClassExpressionUtils; 028import org.semanticweb.owlapi.model.OWLClassExpression; 029 030import javax.annotation.Nonnull; 031import java.util.*; 032 033/** 034 * This class takes Descritptions and a reasoner and orders the 035 * descriptions by subsumption into a tree, represented by the internal class "Node" 036 * @author Sebastian Hellmann <hellmann@informatik.uni-leipzig.de> 037 * 038 */ 039public class DescriptionSubsumptionTree { 040 private static final Logger logger = Logger.getLogger(DescriptionSubsumptionTree.class); 041 /** 042 * turns on logging 043 */ 044 public static boolean debug = false; 045 046 /** 047 * Datastructure for the tree 048 * @author Sebastian Hellmann <hellmann@informatik.uni-leipzig.de> 049 * 050 */ 051 public class Node implements Comparable<Node> { 052 053 public double accuracy; 054 public boolean root = false; 055 056 // by length? 057 /** 058 * holds descriptions of nodes with equivalent classes 059 * should be ordered by length 060 */ 061 public SortedSet<EvaluatedDescription<? extends Score>> equivalents = new TreeSet<>( 062 new Comparator<EvaluatedDescription<? extends Score>>() { 063 @Override 064 public int compare(EvaluatedDescription<? extends Score> o1, EvaluatedDescription<? extends Score> o2) { 065 int ret = o2.getDescriptionLength() - o1.getDescriptionLength(); 066 return (ret == 0) ? -1 : 0; 067 } 068 }); 069 070 // by accuracy 071 /** 072 * holds the nodes that are subclasses of this node. 073 * ordered by accuracy 074 */ 075 public SortedSet<Node> subClasses = new TreeSet<>(); 076 077 public Node(EvaluatedDescription<? extends Score> ed, boolean root) { 078 this.root = root; 079 if (this.root) { 080 accuracy = 0.0d; 081 }else{ 082 equivalents.add(ed); 083 accuracy = ed.getAccuracy(); 084 } 085 } 086 087 public Node(EvaluatedDescription ed) { 088 this(ed,false); 089 } 090 091 // 092 /** 093 * insert a node into the tree 094 * only used if node is sure to be a subClass of this node 095 * @param node 096 */ 097 public void insert(Node node) { 098 logger.warn("******************"); 099 if (subClasses.isEmpty()) { 100 logger.warn("Adding " + node.getEvalDesc() + "\n\t as subclass of " + this.getEvalDesc()); 101 subClasses.add(node); 102 } else { 103 SortedSet<Node> subClassesTmp = new TreeSet<>(subClasses); 104 for (Node sub : subClassesTmp) { 105 logger.warn("Testing relation between: " + node.getEvalDesc() + "\n\t and " 106 + sub.getEvalDesc()); 107 108 boolean passOn = rc.isSuperClassOf(/* super */sub.getDesc(),/* sub */node.getDesc()); 109 boolean superClass = rc.isSuperClassOf(/* super */node.getDesc(),/* sub */sub.getDesc()); 110 111 // EquivalentClass of subclass 112 if (passOn && superClass) { 113 logger.warn("Adding " + node.getEvalDesc() + "\n\t as EQUIVALENTclass of " 114 + sub.getEvalDesc()); 115// n.parent = sub.parent; 116 sub.equivalents.add(node.getEvalDesc()); 117 // superclass of subclass 118 } else if (superClass) { 119 logger.warn("Adding " + node.getEvalDesc() + "\n\t as SUPERclass of " 120 + sub.getEvalDesc()); 121// n.parent = this; 122// sub.parent = n; 123 subClasses.remove(sub); 124 subClasses.add(node); 125 node.insert(sub); 126 // passOn to next Class 127 } else if (passOn) { 128 logger 129 .warn("Passing " + node.getEvalDesc() + "\n\t as SUBclass to " 130 + sub.getEvalDesc()); 131 sub.insert(node); 132 // add to own subclasses 133 } else { 134 logger 135 .warn("Adding " + node.getEvalDesc() + "\n\t as SUBclass of " 136 + this.getEvalDesc()); 137// n.parent = this; 138 subClasses.add(node); 139 } 140 } 141 } 142 } 143 144 /** 145 * @return the first, i.e. the shortest class expression of this node 146 */ 147 public EvaluatedDescription<?> getEvalDesc() { 148 return (equivalents.isEmpty()) ? null : equivalents.first(); 149 } 150 151 /** 152 * @return the first, i.e. the shortest class OWLClassExpression of this node 153 */ 154 public OWLClassExpression getDesc() { 155 return (equivalents.isEmpty()) ? null : equivalents.first().getDescription(); 156 } 157 158 @Override 159 public String toString() { 160 return "subs/equivs: "+subClasses.size()+"|"+equivalents.size()+" \n"+getEvalDesc().toString()+"\n"+subClasses; 161 } 162 163 /** 164 * a simple recursive implementation of a tree to string conversion 165 * @param tab 166 * @return 167 */ 168 public String _toString(String tab) { 169 StringBuilder ret = new StringBuilder(); 170 ret.append((root) ? "Thing\n" : tab + getEvalDesc() + "\n"); 171 tab += " "; 172 for (Node sub : subClasses) { 173 ret.append(sub._toString(tab)); 174 } 175 return ret.toString(); 176 } 177 178 public List<EvaluatedDescription<? extends Score>> getOrderedBySubsumptionAndAccuracy(boolean distinct){ 179 List<EvaluatedDescription<? extends Score>> l = new ArrayList<>(); 180 for(Node subs:subClasses){ 181 l.add(subs.getEvalDesc()); 182 } 183 184 for(Node subs:subClasses){ 185 if(distinct){ 186 for(EvaluatedDescription<? extends Score> subsubs : subs.getOrderedBySubsumptionAndAccuracy(distinct)){ 187 if(!l.contains(subsubs)){ 188 l.add(subsubs); 189 } 190 } 191 }else{ 192 l.addAll(subs.getOrderedBySubsumptionAndAccuracy(distinct)); 193 } 194 195 } 196 return l; 197 198 } 199 200 public double getAccuracy() { 201 return accuracy; 202 } 203 204 @Override 205 public int compareTo(@Nonnull Node node) { 206 if (this.equals(node)) { 207 return 0; 208 } 209 210 int ret = (int) Math.round(accuracy - node.accuracy); 211 if (ret == 0) { 212 ret = OWLClassExpressionUtils.getLength(node.getDesc()) - OWLClassExpressionUtils.getLength(getDesc()); 213 } 214 if (ret == 0) { 215 ret = -1; 216 } 217 return ret; 218 } 219 220 /** 221 * == is used, important, when removing nodes from subClasses SortedSet 222 * @param node 223 * @return 224 */ 225 public boolean equals(Node node) { 226 return this == node; 227 } 228 229 } 230 231 /* 232 * MAIN CLASS FOLLOWING BELOW 233 * 234 * */ 235 236 private Node rootNode; 237 private final AbstractReasonerComponent rc; 238 239 /** 240 * 241 * @param rc An initialized reasoner component 242 */ 243 public DescriptionSubsumptionTree(AbstractReasonerComponent rc) { 244 logger.trace("Output for DescriptionSubsumptionTree deactivated (in class)"); 245 logger.setLevel((debug) ? Level.WARN : Level.OFF); 246 this.rc = rc; 247 this.rootNode = new Node(null,true); 248 } 249 250 public Node getRootNode(){ 251 return rootNode; 252 } 253 254 public List<EvaluatedDescription<? extends Score>> getMostGeneralDescriptions(boolean distinct){ 255 return rootNode.getOrderedBySubsumptionAndAccuracy(distinct); 256 257 } 258 259 public void insert(Collection<? extends EvaluatedDescription<? extends Score>> evaluatedDescriptions) { 260 for (EvaluatedDescription<? extends Score> evaluatedDescription : evaluatedDescriptions) { 261 logger.warn("Next to insert: " + evaluatedDescription.toString()); 262 Node n = new Node(evaluatedDescription); 263 this.rootNode.insert(n); 264 } 265 } 266 267 /** 268 * Not very well implemented, feel free to write your own 269 * @param evaluatedDescriptions 270 * @param limit 271 * @param accuracyThreshold 272 */ 273 public void insertEdPosNeg(Collection<EvaluatedDescriptionPosNeg> evaluatedDescriptions, int limit, 274 double accuracyThreshold) { 275 276 List<EvaluatedDescription> newSet = new ArrayList<>(); 277 int i = 0; 278 for (EvaluatedDescriptionPosNeg evaluatedDescription : evaluatedDescriptions) { 279 if (i >= evaluatedDescriptions.size() || newSet.size() >= limit) { 280 break; 281 } 282 if (evaluatedDescription.getAccuracy() > accuracyThreshold) { 283 newSet.add(evaluatedDescription); 284 logger.warn(evaluatedDescription); 285 } 286 i++; 287 } 288 289 for (EvaluatedDescription evaluatedDescription : newSet) { 290 logger.warn("Next to insert: " + evaluatedDescription.toString()); 291 Node n = new Node(evaluatedDescription); 292 this.rootNode.insert(n); 293 } 294 logger.warn("Finished Inserting"); 295 296 } 297 298 @Override 299 public String toString() { 300 return rootNode._toString(""); 301 } 302 303// public void insert(List<? extends EvaluatedDescription> currentlyBestEvaluatedDescriptions) { 304// insert(currentlyBestEvaluatedDescriptions); 305// 306// } 307 308}