Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner:[1048] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2008-08-04 11:34:30
|
Revision: 1048
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1048&view=rev
Author: jenslehmann
Date: 2008-08-04 11:34:25 +0000 (Mon, 04 Aug 2008)
Log Message:
-----------
- implemented cache for getting all nodes on a particular level of a tree
- one of five operator steps in EL downward refinement done
Modified Paths:
--------------
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
trunk/src/dl-learner/org/dllearner/core/owl/Description.java
trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java
trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java
Added Paths:
-----------
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-08-04 09:01:44 UTC (rev 1047)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-08-04 11:34:25 UTC (rev 1048)
@@ -27,6 +27,7 @@
import org.dllearner.core.owl.Description;
import org.dllearner.core.owl.Intersection;
import org.dllearner.core.owl.NamedClass;
+import org.dllearner.core.owl.ObjectProperty;
import org.dllearner.core.owl.ObjectSomeRestriction;
import org.dllearner.core.owl.Thing;
import org.dllearner.core.owl.UnsupportedLanguageException;
@@ -49,6 +50,9 @@
*/
public class ELDescriptionNode {
+ // the reference tree for storing values, must not be null
+ private ELDescriptionTree tree;
+
private SortedSet<NamedClass> label;
private List<ELDescriptionEdge> edges;
@@ -58,37 +62,52 @@
// parent node in the tree;
// null indicates that this node is a root node
private ELDescriptionNode parent = null;
-
- // to simplify equivalence checks and minimisation, we
- // attach a simulation relation to the description tree
-// private Simulation simulation;
-
+
/**
- * Constructs an empty EL description tree with the empty set
- * as root label and an empty set of outgoing edges.
+ * Constructs an EL description tree with empty root label.
*/
- public ELDescriptionNode() {
- this(new TreeSet<NamedClass>(), new LinkedList<ELDescriptionEdge>());
-// simulation = new Simulation();
- }
+ public ELDescriptionNode(ELDescriptionTree tree) {
+ this(tree, new TreeSet<NamedClass>());
+ }
/**
* Constructs an EL description tree given its root label.
* @param label Label of the root node.
*/
- public ELDescriptionNode(SortedSet<NamedClass> label) {
- this(label, new LinkedList<ELDescriptionEdge>());
+ public ELDescriptionNode(ELDescriptionTree tree, SortedSet<NamedClass> label) {
+ this.label = label;
+ this.edges = new LinkedList<ELDescriptionEdge>();
+ this.tree = tree;
+ level = 1;
+ parent = null;
}
+ public ELDescriptionNode(ELDescriptionNode parentNode, ObjectProperty parentProperty, SortedSet<NamedClass> label) {
+ this.label = label;
+ this.edges = new LinkedList<ELDescriptionEdge>();
+ parent = parentNode;
+ // the reference tree is the same as for the parent tree
+ tree = parentNode.tree;
+ // level increases by 1
+ level = parentNode.level + 1;
+ // we add an edge from the parent to this node
+ ELDescriptionEdge edge = new ELDescriptionEdge(parentProperty, this);
+ parent.edges.add(edge);
+ // we need to update the set of nodes on a particular level
+ tree.addNodeToLevel(this, level);
+ }
+
/**
* Constructs an EL description tree given its root label and edges.
* @param label Label of the root node.
* @param edges Edges connected to the root node.
*/
- public ELDescriptionNode(SortedSet<NamedClass> label, List<ELDescriptionEdge> edges) {
- this.label = label;
- this.edges = edges;
- }
+// TODO: probably delete as this constructor is not straightforward to
+// implement within the new structure
+// public ELDescriptionNode(SortedSet<NamedClass> label, List<ELDescriptionEdge> edges) {
+// this.label = label;
+// this.edges = edges;
+// }
/**
* Constructs an EL description tree from an EL description.
@@ -167,8 +186,19 @@
return is;
}
}
+
+ /**
+ * Replaces an entry in the node label.
+ * @param oldClass Class to remove from label.
+ * @param newClass Class to add to label.
+ */
+ public void replaceInLabel(NamedClass oldClass, NamedClass newClass) {
+ label.remove(oldClass);
+ label.add(newClass);
+ }
/**
+ * Gets the label of this node. Do not modify the returned object.
* @return The label of root node of this subtree.
*/
public SortedSet<NamedClass> getLabel() {
@@ -176,7 +206,8 @@
}
/**
- * @return The outgoing edges of this subtree.
+ * @return The outgoing edges of this subtree. Do not modify the
+ * returned object.
*/
public List<ELDescriptionEdge> getEdges() {
return edges;
@@ -191,8 +222,22 @@
@Override
public ELDescriptionNode clone() {
- // TODO implement efficient tree cloning
- return null;
+ ELDescriptionNode node = null;
+ try {
+ node = (ELDescriptionNode) super.clone();
+ } catch (CloneNotSupportedException e) {
+ // should never happen
+ throw new InternalError(e.toString());
+ }
+/*
+ // create a deep copy
+ node.children = new LinkedList<Description>();
+ for(Description child : children) {
+ Description clonedChild = (Description) child.clone();
+ node.addChild(clonedChild);
+ }
+*/
+ return node;
}
}
Added: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-08-04 11:34:25 UTC (rev 1048)
@@ -0,0 +1,118 @@
+/**
+ * Copyright (C) 2007-2008, Jens Lehmann
+ *
+ * This file is part of DL-Learner.
+ *
+ * DL-Learner is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * DL-Learner is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+package org.dllearner.algorithms.el;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeSet;
+
+import org.dllearner.core.owl.NamedClass;
+
+/**
+ * Represents an EL description tree. Unlike {@link ELDescriptionNode},
+ * this is a tree-wide structure, i.e. it does not implement the tree
+ * structure itself, but is used to store information about the tree.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class ELDescriptionTree implements Cloneable {
+
+ // to simplify equivalence checks and minimisation, we
+ // attach a simulation relation to the description tree
+// private Simulation simulation;
+
+ private int maxLevel = 1;
+
+ private ELDescriptionNode rootNode;
+
+ private Map<Integer,Set<ELDescriptionNode>> levelNodeMapping = new HashMap<Integer,Set<ELDescriptionNode>>();
+
+ public ELDescriptionTree() {
+
+ }
+
+ /**
+ * Gets the nodes on a specific level of the tree.
+ * This information is cached here for performance
+ * reasons.
+ * @param level The level (distance from root node).
+ * @return The set of all nodes on the specified level within
+ * this tree.
+ */
+ public Set<ELDescriptionNode> getNodesOnLevel(int level) {
+ return levelNodeMapping.get(level);
+ }
+
+ /**
+ * Internal method for updating the level node mapping.
+ * It is called when a new node is added to the tree.
+ * @param node The new node.
+ * @param level Level of the new node.
+ */
+ protected void addNodeToLevel(ELDescriptionNode node, int level) {
+ if(level <= maxLevel) {
+ levelNodeMapping.get(level).add(node);
+ } else if (level == maxLevel + 1) {
+ Set<ELDescriptionNode> set = new HashSet<ELDescriptionNode>();
+ set.add(node);
+ levelNodeMapping.put(level, set);
+ maxLevel++;
+ } else {
+ throw new RuntimeException("Inconsistent EL description tree structure.");
+ }
+ }
+
+ /**
+ * @return the maxLevel
+ */
+ public int getMaxLevel() {
+ return maxLevel;
+ }
+
+ /**
+ * @return the rootNode
+ */
+ public ELDescriptionNode getRootNode() {
+ return rootNode;
+ }
+
+ @Override
+ public ELDescriptionTree clone() {
+ // create a new reference tree
+ ELDescriptionTree treeClone = new ELDescriptionTree();
+ // create a root node attached to this reference tree
+ ELDescriptionNode rootNodeClone = new ELDescriptionNode(treeClone, new TreeSet<NamedClass>(rootNode.getLabel()));
+ cloneRecursively(rootNode, rootNodeClone);
+ return treeClone;
+ }
+
+ // we read from the original structure and write to the new structure
+ private void cloneRecursively(ELDescriptionNode node, ELDescriptionNode nodeClone) {
+ // loop through all edges and clone the subtrees
+ for(ELDescriptionEdge edge : node.getEdges()) {
+ ELDescriptionNode tmp = new ELDescriptionNode(nodeClone, edge.getLabel(), new TreeSet<NamedClass>(edge.getTree().getLabel()));
+ cloneRecursively(edge.getTree(), tmp);
+ }
+ }
+
+}
Modified: trunk/src/dl-learner/org/dllearner/core/owl/Description.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/core/owl/Description.java 2008-08-04 09:01:44 UTC (rev 1047)
+++ trunk/src/dl-learner/org/dllearner/core/owl/Description.java 2008-08-04 11:34:25 UTC (rev 1048)
@@ -101,9 +101,8 @@
/**
* Returns a clone of this description.
*/
- @SuppressWarnings("unchecked")
@Override
- public Object clone() {
+ public Description clone() {
Description node = null;
try {
node = (Description) super.clone();
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-08-04 09:01:44 UTC (rev 1047)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-08-04 11:34:25 UTC (rev 1048)
@@ -125,9 +125,12 @@
for(NamedClass nc : tree.getLabel()) {
// find all more special classes for the given label
for(Description moreSpecial : rs.getMoreSpecialConcepts(nc)) {
- // create refinements by replacing class
- ELDescriptionNode tmp = tree.clone();
- // TODO replace class in label
+ if(moreSpecial instanceof NamedClass) {
+ // create refinements by replacing class
+ ELDescriptionNode tmp = tree.clone();
+ tmp.replaceInLabel(nc, (NamedClass) moreSpecial);
+ refinements.add(tmp);
+ }
}
}
Modified: trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java 2008-08-04 09:01:44 UTC (rev 1047)
+++ trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java 2008-08-04 11:34:25 UTC (rev 1048)
@@ -21,9 +21,14 @@
import static org.junit.Assert.*;
+import java.util.TreeSet;
+
import org.dllearner.algorithms.el.ELDescriptionNode;
+import org.dllearner.algorithms.el.ELDescriptionTree;
import org.dllearner.algorithms.el.Simulation;
import org.dllearner.algorithms.el.TreeTuple;
+import org.dllearner.core.owl.NamedClass;
+import org.dllearner.core.owl.ObjectProperty;
import org.junit.Test;
/**
@@ -38,12 +43,19 @@
@Test
public void simulationTest() {
Simulation s = new Simulation();
- ELDescriptionNode t1 = new ELDescriptionNode();
- ELDescriptionNode t2 = new ELDescriptionNode();
+ ELDescriptionTree tree1 = new ELDescriptionTree();
+ ELDescriptionTree tree2 = new ELDescriptionTree();
+ ELDescriptionNode t1 = new ELDescriptionNode(tree1);
+ ELDescriptionNode t2 = new ELDescriptionNode(tree2);
TreeTuple tuple1 = new TreeTuple(t1,t2);
s.addTuple(tuple1);
assertTrue(s.in(t2).size() == 1);
- assertTrue(s.out(t2).size() == 0);
+// assertTrue(s.out(t2).size() == 0);
+ ObjectProperty p = new ObjectProperty("p");
+ TreeSet<NamedClass> l3 = new TreeSet<NamedClass>();
+ ELDescriptionNode t3 = new ELDescriptionNode(t1,p,l3);
+ assertTrue(t3.getLevel() == 2);
+ assertTrue(tree1.getMaxLevel() == 2);
}
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
