001 /**
002 * Copyright (C) 2007-2011, 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 */
019
020 package org.dllearner.algorithms.el;
021
022 import java.util.Collection;
023 import java.util.HashMap;
024 import java.util.HashSet;
025 import java.util.LinkedList;
026 import java.util.List;
027 import java.util.Map;
028 import java.util.NavigableSet;
029 import java.util.Set;
030 import java.util.TreeSet;
031 import java.util.Map.Entry;
032
033 import org.apache.log4j.Logger;
034 import org.dllearner.core.AbstractReasonerComponent;
035 import org.dllearner.core.owl.ClassHierarchy;
036 import org.dllearner.core.owl.Description;
037 import org.dllearner.core.owl.Intersection;
038 import org.dllearner.core.owl.NamedClass;
039 import org.dllearner.core.owl.ObjectProperty;
040 import org.dllearner.core.owl.ObjectPropertyHierarchy;
041 import org.dllearner.core.owl.ObjectSomeRestriction;
042 import org.dllearner.core.owl.Thing;
043 import org.dllearner.core.owl.UnsupportedLanguageException;
044
045 /**
046 * Represents an EL description tree. Unlike {@link ELDescriptionNode}, this is
047 * a tree-wide structure, i.e. it does not implement the tree structure itself,
048 * but is used to store information about the tree.
049 *
050 * @author Jens Lehmann
051 *
052 */
053 public class ELDescriptionTree implements Cloneable {
054
055 @SuppressWarnings("unused")
056 private static Logger logger = Logger.getLogger(ELDescriptionTree.class);
057
058 // to simplify equivalence checks and minimisation, we
059 // attach a simulation relation to the description tree
060 // private Simulation simulation;
061
062 // max level = 0 means that there is no tree at all
063 // (max level = 1 means the root node exists)
064 private int maxLevel = 0;
065
066 protected int size = 1;
067
068 protected ELDescriptionNode rootNode;
069
070 // the set of all nodes in the tree
071 private Collection<ELDescriptionNode> nodes = new LinkedList<ELDescriptionNode>();
072
073 // nodes on a given level of the tree
074 private Map<Integer, Set<ELDescriptionNode>> levelNodeMapping = new HashMap<Integer, Set<ELDescriptionNode>>();
075
076 // the background knowledge (we need to have it explicitly here,
077 // since we store simulation information in the tree and simulation
078 // updates depend on background knowledge)
079 protected AbstractReasonerComponent rs;
080 protected ClassHierarchy subsumptionHierarchy;
081 protected ObjectPropertyHierarchy roleHierarchy;
082
083 public ELDescriptionTree(AbstractReasonerComponent rs) {
084 this.rs = rs;
085 subsumptionHierarchy = rs.getClassHierarchy();
086 roleHierarchy = rs.getObjectPropertyHierarchy();
087 }
088
089 /**
090 * Constructs an EL description tree from an EL description.
091 *
092 * @param description
093 * A description
094 */
095 public ELDescriptionTree(AbstractReasonerComponent rs, Description description) {
096 this(rs);
097 // construct root node and recursively build the tree
098 rootNode = new ELDescriptionNode(this);
099 constructTree(description, rootNode);
100 }
101
102 private void constructTree(Description description, ELDescriptionNode node) {
103 if (description instanceof NamedClass) {
104 node.extendLabel((NamedClass) description);
105 } else if (description instanceof ObjectSomeRestriction) {
106 ObjectProperty op = (ObjectProperty) ((ObjectSomeRestriction) description).getRole();
107 ELDescriptionNode newNode = new ELDescriptionNode(node, op, new TreeSet<NamedClass>());
108 constructTree(description.getChild(0), newNode);
109 } else if (description instanceof Thing) {
110 // nothing needs to be done as an empty set is owl:Thing
111 } else if (description instanceof Intersection) {
112 // loop through all elements of the intersection
113 for (Description child : description.getChildren()) {
114 if (child instanceof NamedClass) {
115 node.extendLabel((NamedClass) child);
116 } else if (child instanceof ObjectSomeRestriction) {
117 ObjectProperty op = (ObjectProperty) ((ObjectSomeRestriction) child).getRole();
118 ELDescriptionNode newNode = new ELDescriptionNode(node, op,
119 new TreeSet<NamedClass>());
120 constructTree(child.getChild(0), newNode);
121 } else {
122 throw new UnsupportedLanguageException(description + " specifically " + child,
123 "EL");
124 }
125 }
126 } else {
127 throw new UnsupportedLanguageException(description.toString(), "EL");
128 }
129 }
130
131 /**
132 * Gets the nodes on a specific level of the tree. This information is
133 * cached here for performance reasons.
134 *
135 * @param level
136 * The level (distance from root node).
137 * @return The set of all nodes on the specified level within this tree.
138 */
139 public Set<ELDescriptionNode> getNodesOnLevel(int level) {
140 return levelNodeMapping.get(level);
141 }
142
143 public Description transformToDescription() {
144 return rootNode.transformToDescription();
145 }
146
147 // checks whether this tree is minimal wrt. background knowledge
148 public boolean isMinimal() {
149 // System.out.println(this);
150 // System.out.println(levelNodeMapping);
151 // loop through all levels starting from root (level 1)
152 for(int i=1; i<=maxLevel; i++) {
153 // get all nodes of this level
154 Set<ELDescriptionNode> nodes = levelNodeMapping.get(i);
155 // System.out.println("level " + i + ": " + nodes);
156 for(ELDescriptionNode node : nodes) {
157 List<ELDescriptionEdge> edges = node.getEdges();
158 // we need to compare all combination of edges
159 // (in both directions because subsumption is obviously
160 // not symmetric)
161 for(int j=0; j<edges.size(); j++) {
162 for(int k=0; k<edges.size(); k++) {
163 if(j != k) {
164 // we first check inclusion property on edges
165 ObjectProperty op1 = edges.get(j).getLabel();
166 ObjectProperty op2 = edges.get(k).getLabel();
167 if(rs.getObjectPropertyHierarchy().isSubpropertyOf(op1, op2)) {
168 ELDescriptionNode node1 = edges.get(j).getNode();
169 ELDescriptionNode node2 = edges.get(k).getNode();
170 // check simulation condition
171 if(node1.in.contains(node2)) { // || node2.in.contains(node1)) {
172 // node1 is simulated by node2, i.e. we could remove one
173 // of them, so the tree is not minimal
174 return false;
175 }
176 }
177 }
178 }
179 }
180 }
181 }
182 return true;
183 }
184
185 /**
186 * Internal method for updating the node set and the level node mapping. It must be
187 * called when a new node is added to the tree.
188 *
189 * @param node
190 * The new node.
191 * @param level
192 * Level of the new node.
193 */
194 protected void addNodeToLevel(ELDescriptionNode node, int level) {
195 nodes.add(node);
196 if (level <= maxLevel) {
197 levelNodeMapping.get(level).add(node);
198 } else if (level == maxLevel + 1) {
199 Set<ELDescriptionNode> set = new HashSet<ELDescriptionNode>();
200 set.add(node);
201 levelNodeMapping.put(level, set);
202 maxLevel++;
203 } else {
204 throw new RuntimeException("Inconsistent EL description tree structure.");
205 }
206 }
207
208 /**
209 * @return the maxLevel
210 */
211 public int getMaxLevel() {
212 return maxLevel;
213 }
214
215 /**
216 * @return the rootNode
217 */
218 public ELDescriptionNode getRootNode() {
219 return rootNode;
220 }
221
222 /**
223 * Gets the node at the given position. The list is processed as follows:
224 * Starting with the root node, the first element i of list is read and the
225 * i-th child of root node is selected. This node is set as current node and
226 * the next element j of the list is read and the j-th child of the i-th
227 * child of the root node selected etc.
228 *
229 * @return The node at the specified position.
230 */
231 public ELDescriptionNode getNode(int[] position) {
232 // logger.trace(Helper.arrayContent(position));
233 // logger.trace(this);
234 ELDescriptionNode currentNode = rootNode;
235 for (int i = 0; i < position.length; i++) {
236 currentNode = currentNode.getEdges().get(position[i]).getNode();
237 }
238 return currentNode;
239 }
240
241 protected void updateSimulation(Set<ELDescriptionNode> nUpdate) {
242 // create a stack and initialize it with the nodes to be updated
243 LinkedList<ELDescriptionNode> list = new LinkedList<ELDescriptionNode>();
244 list.addAll(nUpdate);
245
246 while(list.size() != 0) {
247 // take element from bottom of stack (to ensure that all nodes on the
248 // same level are tested before any node of a lower level is tested)
249 ELDescriptionNode v = list.pollFirst();
250 // loop through all nodes on same level
251 Set<ELDescriptionNode> sameLevel = levelNodeMapping.get(v.getLevel());
252 for(ELDescriptionNode w : sameLevel) {
253 if(v != w) {
254
255 // System.out.println(v);
256 // System.out.println(w);
257
258 // we update if SC2 did not hold but does now
259 if(!v.inSC2.contains(w) && checkSC2(v,w)) {
260 // System.out.println("extend sim. after update");
261
262 extendSimulationSC2(v,w);
263 if(v.inSC1.contains(w)) {
264 extendSimulationSC12(v,w);
265 }
266 if(!list.contains(v.getParent())) {
267 list.add(v.getParent());
268 }
269 if(!list.contains(w.getParent())) {
270 list.add(w.getParent());
271 }
272 }
273
274 // similar case, but now possibly shrinking the simulation
275 if(w.inSC2.contains(v) && !checkSC2(w,v)) {
276 // System.out.println("shrink sim. after update");
277
278 shrinkSimulationSC2(w,v);
279 if(w.inSC1.contains(v)) {
280 shrinkSimulationSC12(w,v);
281 }
282 if(!list.contains(v.getParent())) {
283 list.add(v.getParent());
284 }
285 if(!list.contains(w.getParent())) {
286 list.add(w.getParent());
287 }
288 }
289 /*
290 if(!v.out.contains(w) ) {
291 System.out.println("test");
292 if(checkSC2(v,w) && v.outSC1.contains(w)) {
293 extendSimulation(v,w);
294 list.add(v.getParent());
295 list.add(w.getParent());
296 } else {
297 System.out.println("test in");
298 shrinkSimulationSC2(v,w);
299 }
300 }
301 if(!w.out.contains(v) ) {
302 if(checkSC2(w,v) && w.outSC1.contains(v)) {
303 extendSimulation(w,v);
304 list.add(v.getParent());
305 list.add(w.getParent());
306 } else {
307 shrinkSimulationSC2(w,v);
308 }
309 }
310 */
311 }
312 }
313 }
314 }
315
316 // SC satisfied if both SC1 and SC2 satisfied
317 public boolean checkSC(ELDescriptionNode node1, ELDescriptionNode node2) {
318 return checkSC1(node1, node2) && checkSC2(node1, node2);
319 }
320
321 // tests simulation condition 1 (SC1)
322 public boolean checkSC1(ELDescriptionNode node1, ELDescriptionNode node2) {
323 return isSublabel(node1.getLabel(), node2.getLabel());
324 }
325
326 private boolean isSublabel(NavigableSet<NamedClass> subLabel, NavigableSet<NamedClass> superLabel) {
327 // implemented according to definition in article
328 // (TODO can probably be done more efficiently)
329 for(NamedClass nc : superLabel) {
330 if(!containsSubclass(nc, subLabel)) {
331 return false;
332 }
333 }
334 return true;
335 }
336
337 private boolean containsSubclass(NamedClass superClass, NavigableSet<NamedClass> label) {
338 for(NamedClass nc : label) {
339 if(subsumptionHierarchy.isSubclassOf(nc, superClass)) {
340 return true;
341 }
342 }
343 return false;
344 }
345
346 // tests simulation condition 2 (SC2)
347 public boolean checkSC2(ELDescriptionNode node1, ELDescriptionNode node2) {
348 List<ELDescriptionEdge> edges1 = node1.getEdges();
349 List<ELDescriptionEdge> edges2 = node2.getEdges();
350
351 // System.out.println(node1.transformToDescription());
352 // System.out.println(node2.transformToDescription());
353
354 for(ELDescriptionEdge superEdge : edges2) {
355 // try to find an edge satisfying SC2 in the set,
356 // i.e. detect whether superEdge is indeed more general
357 if(!checkSC2Edge(superEdge, edges1)) {
358 // System.out.println("false");
359 return false;
360 }
361 }
362 // System.out.println("true");
363 return true;
364 }
365
366 // check whether edges contains an element satisfying SC2
367 private boolean checkSC2Edge(ELDescriptionEdge superEdge, List<ELDescriptionEdge> edges) {
368 ObjectProperty superOP = superEdge.getLabel();
369 ELDescriptionNode superNode = superEdge.getNode();
370
371 for(ELDescriptionEdge edge : edges) {
372 // System.out.println("superEdge: " + superEdge);
373 // System.out.println("edge: " + edge);
374
375 ObjectProperty op = edge.getLabel();
376 // we first check the condition on the properties
377 if(roleHierarchy.isSubpropertyOf(op, superOP)) {
378 // check condition on simulations of referred nodes
379 ELDescriptionNode node = edge.getNode();
380 // if(superNode.in.contains(node) || node.in.contains(superNode)) {
381 if(node.in.contains(superNode)) {
382 // we found a node satisfying the condition, so we can return
383 return true;
384 }
385 }
386 }
387
388 // none of the edges in the set satisfies the 2nd simulation criterion
389 // wrt. the first edge
390 return false;
391 }
392
393 // adds (node1,node2) to simulation, takes care of all helper sets
394 public void extendSimulation(ELDescriptionNode node1, ELDescriptionNode node2) {
395 node1.in.add(node2);
396 node1.inSC1.add(node2);
397 node1.inSC2.add(node2);
398 node2.out.add(node1);
399 node2.outSC1.add(node1);
400 node2.outSC2.add(node1);
401 }
402
403 public void extendSimulationSC1(ELDescriptionNode node1, ELDescriptionNode node2) {
404 node1.inSC1.add(node2);
405 node2.outSC1.add(node1);
406 }
407
408 public void extendSimulationSC2(ELDescriptionNode node1, ELDescriptionNode node2) {
409 node1.inSC2.add(node2);
410 node2.outSC2.add(node1);
411 }
412
413 public void extendSimulationSC12(ELDescriptionNode node1, ELDescriptionNode node2) {
414 node1.in.add(node2);
415 node2.out.add(node1);
416 }
417
418 // removes (node1,node2) from simulation, takes care of all helper sets
419 public void shrinkSimulation(ELDescriptionNode node1, ELDescriptionNode node2) {
420 node1.in.remove(node2);
421 node1.inSC1.remove(node2);
422 node1.inSC2.remove(node2);
423 node2.out.remove(node1);
424 node2.outSC1.remove(node1);
425 node2.outSC2.remove(node1);
426 }
427
428 public void shrinkSimulationSC1(ELDescriptionNode node1, ELDescriptionNode node2) {
429 node1.inSC1.remove(node2);
430 node2.outSC1.remove(node1);
431 }
432
433 public void shrinkSimulationSC2(ELDescriptionNode node1, ELDescriptionNode node2) {
434 // System.out.println(node2.outSC2);
435 node1.inSC2.remove(node2);
436 node2.outSC2.remove(node1);
437 // System.out.println(node2.outSC2);
438 }
439
440 public void shrinkSimulationSC12(ELDescriptionNode node1, ELDescriptionNode node2) {
441 node1.in.remove(node2);
442 node2.out.remove(node1);
443 }
444
445 public String toSimulationString() {
446 String str = "";
447 for(ELDescriptionNode node : nodes) {
448 str += node.toSimulationString() + "\n";
449 }
450 return str;
451 }
452
453 public String toSimulationString(Map<ELDescriptionNode,String> nodeNames) {
454 String str = "";
455 for(Entry<ELDescriptionNode,String> entry : nodeNames.entrySet()) {
456 String nodeName = entry.getValue();
457 ELDescriptionNode node = entry.getKey();
458 str += nodeName + ":\n";
459 str += node.toSimulationString(nodeNames) + "\n";
460 }
461 return str;
462 }
463
464 @Override
465 @SuppressWarnings("unchecked")
466 public ELDescriptionTree clone() {
467 // Monitor mon = MonitorFactory.start("tree clone");
468 // clone "global" tree
469 ELDescriptionTree treeClone = new ELDescriptionTree(rs);
470
471 // a mapping between "old" and "new" nodes
472 // (hash map should be fast here, but one could also
473 // experiment with TreeMap)
474 Map<ELDescriptionNode, ELDescriptionNode> cloneMap =
475 new HashMap<ELDescriptionNode, ELDescriptionNode>();
476
477 // create a new (empty) node for each node in the tree
478 // (we loop through the level mapping, because it is cheaper
479 // than creating a set of all nodes)
480 for(int i=1; i<=maxLevel; i++) {
481 Set<ELDescriptionNode> tmp = levelNodeMapping.get(i);
482 for(ELDescriptionNode node : tmp) {
483 ELDescriptionNode nodeNew = new ELDescriptionNode();
484 cloneMap.put(node, nodeNew);
485 }
486 }
487
488 ELDescriptionNode newRoot = null;
489
490 // loop through all nodes and perform copy operations
491 for(Entry<ELDescriptionNode, ELDescriptionNode> entry : cloneMap.entrySet()) {
492 ELDescriptionNode oldNode = entry.getKey();
493 ELDescriptionNode newNode = entry.getValue();
494
495 newNode.tree = treeClone;
496 newNode.level = oldNode.level;
497 newNode.label = (TreeSet<NamedClass>) oldNode.label.clone();
498 if(oldNode.parent != null) {
499 newNode.parent = cloneMap.get(oldNode.parent);
500 } else {
501 newRoot = newNode;
502 }
503
504 // simulation information
505 for(ELDescriptionNode node : oldNode.in) {
506 newNode.in.add(cloneMap.get(node));
507 }
508 for(ELDescriptionNode node : oldNode.inSC1) {
509 newNode.inSC1.add(cloneMap.get(node));
510 }
511 for(ELDescriptionNode node : oldNode.inSC2) {
512 newNode.inSC2.add(cloneMap.get(node));
513 }
514 for(ELDescriptionNode node : oldNode.out) {
515 newNode.out.add(cloneMap.get(node));
516 }
517 for(ELDescriptionNode node : oldNode.outSC1) {
518 newNode.outSC1.add(cloneMap.get(node));
519 }
520 for(ELDescriptionNode node : oldNode.outSC2) {
521 newNode.outSC2.add(cloneMap.get(node));
522 }
523
524 // edges
525 for(ELDescriptionEdge edge : oldNode.edges) {
526 // create a new edge with same label and replace the node the edge points to
527 newNode.edges.add(new ELDescriptionEdge(edge.getLabel(), cloneMap.get(edge.getNode())));
528 }
529
530 }
531
532 // update global tree
533 treeClone.rootNode = newRoot;
534 treeClone.maxLevel = maxLevel;
535 treeClone.size = size;
536
537 // nodes
538 treeClone.nodes = new LinkedList<ELDescriptionNode>();
539 for(ELDescriptionNode oldNode : nodes) {
540 treeClone.nodes.add(cloneMap.get(oldNode));
541 }
542
543 // level node mapping
544 for(int i=1; i<=maxLevel; i++) {
545 Set<ELDescriptionNode> oldNodes = levelNodeMapping.get(i);
546 Set<ELDescriptionNode> newNodes = new HashSet<ELDescriptionNode>();
547 for(ELDescriptionNode oldNode : oldNodes) {
548 newNodes.add(cloneMap.get(oldNode));
549 }
550 treeClone.levelNodeMapping.put(i, newNodes);
551 }
552
553 // mon.stop();
554 return treeClone;
555 }
556
557 public ELDescriptionTree cloneOld() {
558 // create a new reference tree
559 ELDescriptionTree treeClone = new ELDescriptionTree(rs);
560 // create a root node attached to this reference tree
561 ELDescriptionNode rootNodeClone = new ELDescriptionNode(treeClone, new TreeSet<NamedClass>(
562 rootNode.getLabel()));
563 cloneRecursively(rootNode, rootNodeClone);
564 return treeClone;
565 }
566
567 // we read from the original structure and write to the new structure
568 private void cloneRecursively(ELDescriptionNode node, ELDescriptionNode nodeClone) {
569 // loop through all edges and clone the subtrees
570 for (ELDescriptionEdge edge : node.getEdges()) {
571 ELDescriptionNode tmp = new ELDescriptionNode(nodeClone, edge.getLabel(),
572 new TreeSet<NamedClass>(edge.getNode().getLabel()));
573 cloneRecursively(edge.getNode(), tmp);
574 }
575 }
576
577 @Override
578 public String toString() {
579 return rootNode.toString();
580 }
581
582 /**
583 * Returns a string of the tree description (without the overhead of converting
584 * the tree into a description).
585 * @return A string for the description the tree stands for.
586 */
587 public String toDescriptionString() {
588 return rootNode.toDescriptionString();
589 }
590
591 /**
592 * @return the nodes
593 */
594 public Collection<ELDescriptionNode> getNodes() {
595 return nodes;
596 }
597
598 public int getDepth() {
599 return maxLevel;
600 }
601
602 /**
603 * size of tree = number of nodes + sum of cardinality of node labels
604 * @return The tree size.
605 */
606 public int getSize() {
607 // int size = nodes.size();
608 // for(ELDescriptionNode node : nodes) {
609 // size += node.getLabel().size();
610 // }
611 return size;
612 }
613 }