Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner:[1415] trunk/src/dl-learner/org/dllearner
|
From: <Jen...@us...> - 2008-10-23 08:44:04
|
Revision: 1415
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1415&view=rev
Author: JensLehmann
Date: 2008-10-23 08:43:03 +0000 (Thu, 23 Oct 2008)
Log Message:
-----------
EL refinement ctd.
Modified Paths:
--------------
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java
trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-10-23 07:41:02 UTC (rev 1414)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-10-23 08:43:03 UTC (rev 1415)
@@ -71,11 +71,11 @@
// simulation information (list or set?)
protected Set<ELDescriptionNode> in = new HashSet<ELDescriptionNode>();
- private Set<ELDescriptionNode> inSC1 = new HashSet<ELDescriptionNode>();
- private Set<ELDescriptionNode> inSC2 = new HashSet<ELDescriptionNode>();
+ protected Set<ELDescriptionNode> inSC1 = new HashSet<ELDescriptionNode>();
+ protected Set<ELDescriptionNode> inSC2 = new HashSet<ELDescriptionNode>();
protected Set<ELDescriptionNode> out = new HashSet<ELDescriptionNode>();
- private Set<ELDescriptionNode> outSC1 = new HashSet<ELDescriptionNode>();
- private Set<ELDescriptionNode> outSC2 = new HashSet<ELDescriptionNode>();
+ protected Set<ELDescriptionNode> outSC1 = new HashSet<ELDescriptionNode>();
+ protected Set<ELDescriptionNode> outSC2 = new HashSet<ELDescriptionNode>();
/**
* Constructs an EL description tree with empty root label.
@@ -98,7 +98,7 @@
tree.rootNode = this;
tree.addNodeToLevel(this, level);
- // TODO simulation update
+ // TODO simulation initialization
}
public ELDescriptionNode(ELDescriptionNode parentNode, ObjectProperty parentProperty, NavigableSet<NamedClass> label) {
@@ -126,16 +126,16 @@
}
- if(inSC1.contains(w) && checkSC2(this, w)) {
- extendSimulation(this, w);
+ if(inSC1.contains(w) && tree.checkSC2(this, w)) {
+ tree.extendSimulation(this, w);
update.add(w.parent);
}
}
// loop over all nodes in out set
for(ELDescriptionNode w : out) {
- if(!checkSC1(this, w)) {
- shrinkSimulation(this, w);
+ if(!tree.checkSC1(this, w)) {
+ tree.shrinkSimulation(this, w);
update.add(w.parent);
}
}
@@ -299,16 +299,16 @@
Set<ELDescriptionNode> tmp = Helper.difference(nodes, in);
for(ELDescriptionNode w : tmp) {
// we only need to recompute SC2
- if(inSC1.contains(w) && checkSC2(this, w)) {
- extendSimulation(this, w);
+ if(inSC1.contains(w) && tree.checkSC2(this, w)) {
+ tree.extendSimulation(this, w);
update.add(w.parent);
}
}
// loop over all nodes in out set
for(ELDescriptionNode w : out) {
- if(!checkSC1(this, w)) {
- shrinkSimulation(this, w);
+ if(!tree.checkSC1(this, w)) {
+ tree.shrinkSimulation(this, w);
update.add(w.parent);
}
}
@@ -316,89 +316,36 @@
// apply updates recursively top-down
tree.updateSimulation(update);
}
-
- // SC satisfied if both SC1 and SC2 satisfied
- private boolean checkSC(ELDescriptionNode node1, ELDescriptionNode node2) {
- return checkSC1(node1, node2) && checkSC2(node1, node2);
- }
-
- // tests simulation condition 1 (SC1)
- private boolean checkSC1(ELDescriptionNode node1, ELDescriptionNode node2) {
- return isSublabel(node1.label, node2.label);
- }
-
- private boolean isSublabel(NavigableSet<NamedClass> subLabel, NavigableSet<NamedClass> superLabel) {
- // implemented according to definition in article
- // (TODO can probably be done more efficiently)
- for(NamedClass nc : superLabel) {
- if(!containsSubclass(nc, subLabel)) {
- return false;
- }
- }
- return true;
- }
-
- private boolean containsSubclass(NamedClass superClass, NavigableSet<NamedClass> label) {
- for(NamedClass nc : label) {
- if(tree.subsumptionHierarchy.isSubclassOf(nc, superClass)) {
- return true;
- }
- }
- return false;
- }
-
- // tests simulation condition 2 (SC2)
- private boolean checkSC2(ELDescriptionNode node1, ELDescriptionNode node2) {
- List<ELDescriptionEdge> edges1 = node1.getEdges();
- List<ELDescriptionEdge> edges2 = node2.getEdges();
+
+ public void refineEdge(int edgeNumber, ObjectProperty op) {
+ edges.get(edgeNumber).setLabel(op);
- for(ELDescriptionEdge edge : edges1) {
- // try to find an edge satisfying SC2 in the set
- if(!checkSC2Edge(edge, edges2)) {
- return false;
+ // compute the nodes, which need to be updated
+ Set<ELDescriptionNode> update = new TreeSet<ELDescriptionNode>();
+
+ // loop over all nodes on the same level, which are not in the in set
+ Set<ELDescriptionNode> nodes = tree.getNodesOnLevel(level);
+ Set<ELDescriptionNode> tmp = Helper.difference(nodes, in);
+ for(ELDescriptionNode w : tmp) {
+ // we only need to recompute SC1
+ if(inSC2.contains(w) && tree.checkSC1(this, w)) {
+ tree.extendSimulation(this, w);
+ update.add(w.parent);
}
}
- return true;
- }
-
- // check whether edges contains an element satisfying SC2
- private boolean checkSC2Edge(ELDescriptionEdge edge, List<ELDescriptionEdge> edges) {
- ObjectProperty op1 = edge.getLabel();
- ELDescriptionNode node1 = edge.getTree();
-
- for(ELDescriptionEdge edge2 : edges) {
- ObjectProperty op2 = edge2.getLabel();
- // we first check the condition on the properties
- if(tree.roleHierarchy.isSubpropertyOf(op1, op2)) {
- // check condition on simulations of referred nodes
- ELDescriptionNode node2 = edge2.getTree();
- if(node1.in.contains(node2) || node2.in.contains(node1)) {
- // we found a node satisfying the condition, so we can return
- return true;
- }
+ // loop over all nodes in out set
+ for(ELDescriptionNode w : out) {
+ if(!tree.checkSC2(this, w)) {
+ tree.shrinkSimulation(this, w);
+ update.add(w.parent);
}
}
- // none of the edges in the set satisfies the 2nd simulation criterion
- // wrt. the first edge
- return false;
+ // apply updates recursively top-down
+ tree.updateSimulation(update);
}
-
- // adds (node1,node2) to simulation, takes care of all helper sets
- private void extendSimulation(ELDescriptionNode node1, ELDescriptionNode node2) {
- node1.out.add(node2);
- node2.in.add(node1);
- // TODO: SC1, SC2 sets ?
- }
- // removes (node1,node2) from simulation, takes care of all helper sets
- private void shrinkSimulation(ELDescriptionNode node1, ELDescriptionNode node2) {
- node1.out.remove(node2);
- node2.in.remove(node1);
- // TODO: SC1, SC2 sets ?
- }
-
/**
* Gets the label of this node. Do not modify the returned object,
* but use the provided methods instead!
@@ -443,4 +390,8 @@
}
return str;
}
+
+ public ELDescriptionNode getParent() {
+ return parent;
+ }
}
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-10-23 07:41:02 UTC (rev 1414)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-10-23 08:43:03 UTC (rev 1415)
@@ -23,7 +23,9 @@
import java.util.HashSet;
import java.util.List;
import java.util.Map;
+import java.util.NavigableSet;
import java.util.Set;
+import java.util.Stack;
import java.util.TreeSet;
import org.dllearner.core.ReasoningService;
@@ -222,16 +224,118 @@
}
protected void updateSimulation(Set<ELDescriptionNode> nUpdate) {
-// for(ELDescriptionNode node : nodes) {
-//
-// }
- Set<ELDescriptionNode> update;
- while(nUpdate.size() != 0) {
- update = nUpdate; // TODO: clone
-
+ // create a stack and initialize it with the nodes to be updated
+ Stack<ELDescriptionNode> stack = new Stack<ELDescriptionNode>();
+ stack.addAll(nUpdate);
+
+ while(stack.size() != 0) {
+ // take element from bottom of stack (to ensure that all nodes on the
+ // same level are tested before any node of a lower level is tested)
+ ELDescriptionNode v = stack.peek(); // TODO: lookup whether peek is correct (had no Javadoc here)
+ // loop through all nodes on same level
+ for(ELDescriptionNode w : levelNodeMapping.get(v.getLevel())) {
+ if(!v.out.contains(w) && v.outSC1.contains(w) && checkSC2(v,w)) {
+ extendSimulation(v,w);
+ stack.add(v.getParent());
+ stack.add(w.getParent());
+ }
+ if(!w.out.contains(v) && w.outSC1.contains(v) && checkSC2(w,v)) {
+ extendSimulation(w,v);
+ stack.add(v.getParent());
+ stack.add(w.getParent());
+ }
+ }
}
}
+ // SC satisfied if both SC1 and SC2 satisfied
+ public boolean checkSC(ELDescriptionNode node1, ELDescriptionNode node2) {
+ return checkSC1(node1, node2) && checkSC2(node1, node2);
+ }
+
+ // tests simulation condition 1 (SC1)
+ public boolean checkSC1(ELDescriptionNode node1, ELDescriptionNode node2) {
+ return isSublabel(node1.getLabel(), node2.getLabel());
+ }
+
+ private boolean isSublabel(NavigableSet<NamedClass> subLabel, NavigableSet<NamedClass> superLabel) {
+ // implemented according to definition in article
+ // (TODO can probably be done more efficiently)
+ for(NamedClass nc : superLabel) {
+ if(!containsSubclass(nc, subLabel)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private boolean containsSubclass(NamedClass superClass, NavigableSet<NamedClass> label) {
+ for(NamedClass nc : label) {
+ if(subsumptionHierarchy.isSubclassOf(nc, superClass)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ // tests simulation condition 2 (SC2)
+ public boolean checkSC2(ELDescriptionNode node1, ELDescriptionNode node2) {
+ List<ELDescriptionEdge> edges1 = node1.getEdges();
+ List<ELDescriptionEdge> edges2 = node2.getEdges();
+
+ for(ELDescriptionEdge edge : edges1) {
+ // try to find an edge satisfying SC2 in the set
+ if(!checkSC2Edge(edge, edges2)) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ // check whether edges contains an element satisfying SC2
+ private boolean checkSC2Edge(ELDescriptionEdge edge, List<ELDescriptionEdge> edges) {
+ ObjectProperty op1 = edge.getLabel();
+ ELDescriptionNode node1 = edge.getTree();
+
+ for(ELDescriptionEdge edge2 : edges) {
+ ObjectProperty op2 = edge2.getLabel();
+ // we first check the condition on the properties
+ if(roleHierarchy.isSubpropertyOf(op1, op2)) {
+ // check condition on simulations of referred nodes
+ ELDescriptionNode node2 = edge2.getTree();
+ if(node1.in.contains(node2) || node2.in.contains(node1)) {
+ // we found a node satisfying the condition, so we can return
+ return true;
+ }
+ }
+ }
+
+ // none of the edges in the set satisfies the 2nd simulation criterion
+ // wrt. the first edge
+ return false;
+ }
+
+ // adds (node1,node2) to simulation, takes care of all helper sets
+ public void extendSimulation(ELDescriptionNode node1, ELDescriptionNode node2) {
+ node1.out.add(node2);
+ node1.outSC1.add(node2);
+ node1.outSC2.add(node2);
+ node2.in.add(node1);
+ node2.inSC1.add(node1);
+ node2.inSC2.add(node1);
+ }
+
+ // removes (node1,node2) from simulation, takes care of all helper sets
+ public void shrinkSimulation(ELDescriptionNode node1, ELDescriptionNode node2) {
+ node1.out.remove(node2);
+ node1.outSC1.remove(node2);
+ node1.outSC2.remove(node2);
+ node2.in.remove(node1);
+ node2.inSC1.remove(node1);
+ node2.inSC2.remove(node1);
+ }
+
@Override
public ELDescriptionTree clone() {
// create a new reference tree
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-10-23 07:41:02 UTC (rev 1414)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-10-23 08:43:03 UTC (rev 1415)
@@ -259,9 +259,9 @@
// clone operation
ELDescriptionTree clonedTree = tree.clone();
// find cloned edge and replace its label
- ELDescriptionEdge clonedEdge = clonedTree.getNode(position).getEdges().get(edgeNumber);
- clonedEdge.setLabel(op2);
- // TODO simulation update
+ clonedTree.getNode(position).refineEdge(edgeNumber, op2);
+// ELDescriptionEdge clonedEdge = clonedTree.getNode(position).getEdges().get(edgeNumber);
+// clonedEdge.setLabel(op2);
refinements.add(clonedTree);
}
Modified: trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java 2008-10-23 07:41:02 UTC (rev 1414)
+++ trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java 2008-10-23 08:43:03 UTC (rev 1415)
@@ -34,6 +34,7 @@
import org.dllearner.parser.ParseException;
import org.dllearner.reasoning.FastInstanceChecker;
import org.dllearner.refinementoperators.ELDown;
+import org.dllearner.utilities.Helper;
import org.dllearner.utilities.owl.ConceptComparator;
import org.dllearner.utilities.owl.ConceptTransformation;
import org.junit.Test;
@@ -75,6 +76,7 @@
// input description
Description input = KBParser.parseConcept("(human AND EXISTS has.animal)");
+ System.out.println("refining: " + input);
// create reasoner
KBFile source = new KBFile(kb);
@@ -114,14 +116,21 @@
}
// perform refinement and compare solutions
+ long startTime = System.nanoTime();
Set<Description> refinements = operator.refine(input);
+ long runTime = System.nanoTime() - startTime;
+ System.out.println("Refinement step took " + Helper.prettyPrintNanoSeconds(runTime, true, true) + ".");
+ startTime = System.nanoTime();
+ refinements = operator.refine(input);
+ runTime = System.nanoTime() - startTime;
+ System.out.println("Identical 2nd refinement step took " + Helper.prettyPrintNanoSeconds(runTime, true, true) + ".");
// number of refinements has to be correct and each produced
// refinement must be in the set of desired refinements
// assertTrue(refinements.size() == desired.size());
for(Description refinement : refinements) {
System.out.println(refinement);
- assertTrue(desired.contains(refinement));
+// assertTrue(desired.contains(refinement));
}
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
