Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner:[1263] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2008-09-26 10:27:36
|
Revision: 1263
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1263&view=rev
Author: jenslehmann
Date: 2008-09-26 10:27:24 +0000 (Fri, 26 Sep 2008)
Log Message:
-----------
preparations for computing simulations
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/kb/manipulator/DBpediaNavigatorFilterRule.java
trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java
trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.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-09-26 08:42:12 UTC (rev 1262)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-09-26 10:27:24 UTC (rev 1263)
@@ -20,18 +20,22 @@
package org.dllearner.algorithms.el;
import java.util.ArrayList;
+import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.NavigableSet;
+import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
+import org.dllearner.core.ReasoningService;
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.utilities.Helper;
/**
* Represents an EL description tree, which corresponds to a
@@ -66,12 +70,12 @@
private ELDescriptionNode parent = null;
// simulation information (list or set?)
- protected List<ELDescriptionNode> in = new ArrayList<ELDescriptionNode>();
- private List<ELDescriptionNode> inSC1 = new ArrayList<ELDescriptionNode>();
- private List<ELDescriptionNode> inSC2 = new ArrayList<ELDescriptionNode>();
- protected List<ELDescriptionNode> out = new ArrayList<ELDescriptionNode>();
- private List<ELDescriptionNode> outSC1 = new ArrayList<ELDescriptionNode>();
- private List<ELDescriptionNode> outSC2 = new ArrayList<ELDescriptionNode>();
+ protected Set<ELDescriptionNode> in = new HashSet<ELDescriptionNode>();
+ private Set<ELDescriptionNode> inSC1 = new HashSet<ELDescriptionNode>();
+ private 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>();
/**
* Constructs an EL description tree with empty root label.
@@ -92,6 +96,9 @@
parent = null;
// this is the root node of the overall tree
tree.rootNode = this;
+ tree.addNodeToLevel(this, level);
+
+ // TODO simulation update
}
public ELDescriptionNode(ELDescriptionNode parentNode, ObjectProperty parentProperty, NavigableSet<NamedClass> label) {
@@ -107,6 +114,8 @@
parent.edges.add(edge);
// we need to update the set of nodes on a particular level
tree.addNodeToLevel(this, level);
+
+ // TODO simulation update
}
/**
@@ -240,14 +249,102 @@
public void replaceInLabel(NamedClass oldClass, NamedClass newClass) {
label.remove(oldClass);
label.add(newClass);
+
+ // simulation update
+
+
+ Set<ELDescriptionNode> nodes = tree.getNodesOnLevel(level);
+ Set<ELDescriptionNode> tmp = Helper.difference(nodes, in);
+ for(ELDescriptionNode node : tmp) {
+ if(isSublabel(label, node.label)) {
+ // TODO continue later
+ }
+ }
+
}
+ // 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();
+
+ 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(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;
+ }
+ }
+ }
+
+ // 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
+ private void extendSimulation(ELDescriptionNode node1, ELDescriptionNode node2) {
+ node1.out.add(node2);
+ node2.in.add(node1);
+ }
+
/**
* Adds an entry to the node label.
* @param newClass Class to add to label.
*/
public void extendLabel(NamedClass newClass) {
label.add(newClass);
+
+ // TODO simulation update
}
/**
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-09-26 08:42:12 UTC (rev 1262)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-09-26 10:27:24 UTC (rev 1263)
@@ -31,7 +31,9 @@
import org.dllearner.core.owl.Intersection;
import org.dllearner.core.owl.NamedClass;
import org.dllearner.core.owl.ObjectProperty;
+import org.dllearner.core.owl.ObjectPropertyHierarchy;
import org.dllearner.core.owl.ObjectSomeRestriction;
+import org.dllearner.core.owl.SubsumptionHierarchy;
import org.dllearner.core.owl.Thing;
import org.dllearner.core.owl.UnsupportedLanguageException;
@@ -49,14 +51,25 @@
// attach a simulation relation to the description tree
// private Simulation simulation;
- private int maxLevel = 1;
+ // max level = 0 means that there is no tree at all
+ // (max level = 1 means the root node exists)
+ private int maxLevel = 0;
protected ELDescriptionNode rootNode;
private Map<Integer, Set<ELDescriptionNode>> levelNodeMapping = new HashMap<Integer, Set<ELDescriptionNode>>();
- public ELDescriptionTree() {
-
+ // the background knowledge (we need to have it explicitly here,
+ // since we store simulation information in the tree and simulation
+ // updates depend on background knowledge)
+ protected ReasoningService rs;
+ protected SubsumptionHierarchy subsumptionHierarchy;
+ protected ObjectPropertyHierarchy roleHierarchy;
+
+ public ELDescriptionTree(ReasoningService rs) {
+ this.rs = rs;
+ subsumptionHierarchy = rs.getSubsumptionHierarchy();
+ roleHierarchy = rs.getRoleHierarchy();
}
/**
@@ -65,7 +78,8 @@
* @param description
* A description
*/
- public ELDescriptionTree(Description description) {
+ public ELDescriptionTree(ReasoningService rs, Description description) {
+ this(rs);
// construct root node and recursively build the tree
rootNode = new ELDescriptionNode(this);
constructTree(description, rootNode);
@@ -117,11 +131,14 @@
}
// checks whether this tree is minimal wrt. background knowledge
- public boolean isMinimal(ReasoningService rs) {
+ public boolean isMinimal() {
+// System.out.println(this);
+// System.out.println(levelNodeMapping);
// loop through all levels starting from root (level 1)
for(int i=1; i<=maxLevel; i++) {
// get all nodes of this level
Set<ELDescriptionNode> nodes = levelNodeMapping.get(i);
+// System.out.println("level " + i + ": " + nodes);
for(ELDescriptionNode node : nodes) {
List<ELDescriptionEdge> edges = node.getEdges();
// we need to compare all combination of edges
@@ -207,7 +224,7 @@
@Override
public ELDescriptionTree clone() {
// create a new reference tree
- ELDescriptionTree treeClone = new ELDescriptionTree();
+ ELDescriptionTree treeClone = new ELDescriptionTree(rs);
// create a root node attached to this reference tree
ELDescriptionNode rootNodeClone = new ELDescriptionNode(treeClone, new TreeSet<NamedClass>(
rootNode.getLabel()));
Modified: trunk/src/dl-learner/org/dllearner/kb/manipulator/DBpediaNavigatorFilterRule.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/kb/manipulator/DBpediaNavigatorFilterRule.java 2008-09-26 08:42:12 UTC (rev 1262)
+++ trunk/src/dl-learner/org/dllearner/kb/manipulator/DBpediaNavigatorFilterRule.java 2008-09-26 10:27:24 UTC (rev 1263)
@@ -27,11 +27,7 @@
import org.dllearner.utilities.datastructures.RDFNodeTuple;
import org.dllearner.utilities.owl.OWLVocabulary;
-import com.hp.hpl.jena.rdf.model.Literal;
-import com.hp.hpl.jena.rdf.model.RDFNode;
-import com.hp.hpl.jena.rdf.model.impl.ResourceImpl;
-
public class DBpediaNavigatorFilterRule extends Rule{
@@ -42,13 +38,13 @@
@Override
public SortedSet<RDFNodeTuple> applyRule(Node subject, SortedSet<RDFNodeTuple> tuples){
- RDFNode clazz = null;
+// RDFNode clazz = null;
RDFNodeTuple typeTuple = null;
List<RDFNodeTuple> toRemove=new LinkedList<RDFNodeTuple>();
for (RDFNodeTuple tuple : tuples) {
if (tuple.a.toString().equals(OWLVocabulary.RDF_TYPE)){
- clazz = tuple.b;
+// clazz = tuple.b;
typeTuple = tuple;
}
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-09-26 08:42:12 UTC (rev 1262)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-09-26 10:27:24 UTC (rev 1263)
@@ -21,6 +21,7 @@
import java.util.Collection;
import java.util.HashSet;
+import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
@@ -103,9 +104,7 @@
*/
@Override
public Set<Description> refine(Description concept) {
- // TODO according to the specification, we need to minimise
- // the tree (not yet implemented)
- ELDescriptionTree tree = new ELDescriptionTree(concept);
+ ELDescriptionTree tree = new ELDescriptionTree(rs, concept);
Set<ELDescriptionTree> refinementTrees = refine(tree);
// System.out.println("Refinements finished.");
Set<Description> refinements = new HashSet<Description>();
@@ -171,7 +170,6 @@
}
// option 3: new edge
- // TODO incomplete, it is still open how to construct this refinement !!
SortedSet<ObjectProperty> appOPs = utility.computeApplicableObjectProperties(index);
Set<ObjectProperty> mgr = utility.computeMgr(appOPs);
// temporary set of all concepts, which still have to pass the equivalence check
@@ -182,25 +180,34 @@
ELDescriptionNode clonedNode = clonedTree.getNode(position);
// add a new node and edge
ELDescriptionNode newNode = new ELDescriptionNode(clonedNode, op, new TreeSet<NamedClass>());
-// refinements.add(clonedTree);
stack.add(clonedTree);
// recurse if concept is equivalent
- // TODO: efficient equivalence check needs to be implemented !!
while(stack.size() != 0) {
// we pick an arbitrary tree and remove it from the stack
ELDescriptionTree testTree = stack.pop();
- // test equivalence
- boolean equivalent = false;
- // TODO equivalence check
+ // test equivalence (we found out that we can use the
+ // minimality test for equivalence in this case)
+ boolean equivalent = !testTree.isMinimal();
+ // if the tree is equivalent, we need to populate the
+ // stack with refinements (which are later tested for
+ // equivalence)
if(equivalent) {
// edge refinement
// we know that the edge we added is the last one for this node
int edgeNr = node.getEdges().size() - 1;
+ ELDescriptionEdge edge = node.getEdges().get(edgeNr);
// all refinements of this edge are added to the stack
+ // (set 1 in article)
refineEdge(stack, tree, node, position, edgeNr);
// perform node refinements in non-minimize-mode
- refinements.addAll(refineEdges(tree, newNode, position));
+ // (set 2 in article)
+// commented out, because didn't make sense to me
+// refinements.addAll(refineEdges(tree, newNode, position));
+ stack.addAll(refine(tree, newNode, opRanges.get(edge), false));
+ } else {
+ // tree is not equivalent, i.e. a proper refinement
+ refinements.add(testTree);
}
}
}
@@ -216,6 +223,17 @@
refinements.addAll(refine(tree, edge.getTree(), range, minimize));
}
+ // we found out that, in case we start from the TOP concept
+ // (which is assumed in the current implementation), we can
+ // simply throw away all non-minimal concepts
+ if(minimize) {
+ Iterator<ELDescriptionTree> it = refinements.iterator();
+ while(it.hasNext()) {
+ if(!it.next().isMinimal()) {
+ it.remove();
+ }
+ }
+ }
return refinements;
}
@@ -233,18 +251,17 @@
ObjectProperty op = edge.getLabel();
// find all more special properties
for(ObjectProperty op2 : rs.getMoreSpecialRoles(op)) {
- // TODO we need to check whether the range of this property is disjoint
- // with the current child node;
- // not implemented, because disjointness checks can only be done on descriptions
-
// we check whether the range of this property is not disjoint
- // with the existing child node
+ // with the existing child node (we do not perform a full disjointness
+ // check, but only compare with the flattened concept to keep the number
+ // of possible disjointness checks finite)
if(!utility.isDisjoint(getFlattenedConcept(edge.getTree()), opRanges.get(op2))) {
// 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
refinements.add(clonedTree);
}
Modified: trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java 2008-09-26 08:42:12 UTC (rev 1262)
+++ trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java 2008-09-26 10:27:24 UTC (rev 1263)
@@ -48,8 +48,9 @@
@Test
public void simulationTest() {
Simulation s = new Simulation();
- ELDescriptionTree tree1 = new ELDescriptionTree();
- ELDescriptionTree tree2 = new ELDescriptionTree();
+ // TODO we need to add background knowledge (possibly empty)
+ ELDescriptionTree tree1 = null; // new ELDescriptionTree();
+ ELDescriptionTree tree2 = null; // new ELDescriptionTree();
ELDescriptionNode t1 = new ELDescriptionNode(tree1);
ELDescriptionNode t2 = new ELDescriptionNode(tree2);
TreeTuple tuple1 = new TreeTuple(t1,t2);
@@ -67,7 +68,8 @@
public void cloneTest() throws ParseException {
Description d = KBParser.parseConcept("(male AND (human AND EXISTS hasChild.(female AND EXISTS hasChild.male)))");
ConceptTransformation.cleanConcept(d);
- ELDescriptionTree tree = new ELDescriptionTree(d);
+ // TODO needs to be updated (trees now require background knowledge)
+ ELDescriptionTree tree = null; // new ELDescriptionTree(rs, d);
ELDescriptionTree treeCloned = tree.clone();
ELDescriptionTreeComparator comparator = new ELDescriptionTreeComparator();
assertTrue(comparator.compare(tree, treeCloned) == 0);
Modified: trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java 2008-09-26 08:42:12 UTC (rev 1262)
+++ trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java 2008-09-26 10:27:24 UTC (rev 1263)
@@ -121,7 +121,7 @@
// 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.
|
