Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner:[1556] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2008-12-16 16:24:58
|
Revision: 1556
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1556&view=rev
Author: jenslehmann
Date: 2008-12-16 16:24:53 +0000 (Tue, 16 Dec 2008)
Log Message:
-----------
EL refinement operator II ctd.
Modified Paths:
--------------
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionEdge.java
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNodeComparator.java
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithm.java
trunk/src/dl-learner/org/dllearner/core/SchemaReasoner.java
trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java
trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionEdge.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionEdge.java 2008-12-16 10:16:51 UTC (rev 1555)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionEdge.java 2008-12-16 16:24:53 UTC (rev 1556)
@@ -33,7 +33,7 @@
private ObjectProperty label;
- private ELDescriptionNode tree;
+ private ELDescriptionNode node;
/**
* Constructs and edge given a label and an EL description tree.
@@ -42,7 +42,7 @@
*/
public ELDescriptionEdge(ObjectProperty label, ELDescriptionNode tree) {
this.label = label;
- this.tree = tree;
+ this.node = tree;
}
/**
@@ -62,13 +62,13 @@
/**
* @return The EL description tree
*/
- public ELDescriptionNode getTree() {
- return tree;
+ public ELDescriptionNode getNode() {
+ return node;
}
@Override
public String toString() {
- return "--" + label + "--> " + tree.toDescriptionString();
+ return "--" + label + "--> " + node.toDescriptionString();
}
}
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-12-16 10:16:51 UTC (rev 1555)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-12-16 16:24:53 UTC (rev 1556)
@@ -111,7 +111,7 @@
this(parentNode, parentProperty, new TreeSet<NamedClass>(Arrays.asList(label)));
}
- public ELDescriptionNode(ELDescriptionNode parentNode, ObjectProperty parentProperty, TreeSet<NamedClass> label) {
+ public ELDescriptionNode(ELDescriptionNode parentNode, ObjectProperty parentProperty, Set<NamedClass> label) {
// this.label = label;
// we first need to add the edge and update the simulation and then add
// all classes iteratively to the label (each time updating the simulation again)
@@ -261,7 +261,7 @@
return label.first();
} else {
ELDescriptionEdge edge = edges.get(0);
- Description child = edge.getTree().transformToDescription();
+ Description child = edge.getNode().transformToDescription();
return new ObjectSomeRestriction(edge.getLabel(),child);
}
// return an intersection of labels and edges
@@ -271,7 +271,7 @@
is.addChild(nc);
}
for(ELDescriptionEdge edge : edges) {
- Description child = edge.getTree().transformToDescription();
+ Description child = edge.getNode().transformToDescription();
ObjectSomeRestriction osr = new ObjectSomeRestriction(edge.getLabel(),child);
is.addChild(osr);
}
@@ -298,11 +298,12 @@
}
// returns the child number of this node, i.e. whether it is
- // the first, second, third etc. child
+ // the first, second, third etc. child;
+ // TODO: might be a bit faster to store this explicitly
private int getChildNumber() {
int count = 0;
for(ELDescriptionEdge edge : parent.edges) {
- if(edge.getTree() == this) {
+ if(edge.getNode() == this) {
return count;
}
}
@@ -472,7 +473,7 @@
String str = indentString + label.toString() + "\n";
for(ELDescriptionEdge edge : edges) {
str += indentString + "-- " + edge.getLabel() + " -->\n";
- str += edge.getTree().toString(indent + 2);
+ str += edge.getNode().toString(indent + 2);
}
return str;
}
@@ -494,7 +495,7 @@
}
for(ELDescriptionEdge edge : edges) {
str += " AND EXISTS " + edge.getLabel().toString() + ".(";
- str += edge.getTree().toDescriptionString() + ")";
+ str += edge.getNode().toDescriptionString() + ")";
}
return str;
}
@@ -557,6 +558,11 @@
public ELDescriptionNode getParent() {
return parent;
}
+
+ public ELDescriptionEdge getParentEdge() {
+ int childNr = getChildNumber();
+ return parent.edges.get(childNr);
+ }
/**
* @return the in
@@ -599,4 +605,8 @@
public Set<ELDescriptionNode> getOutSC2() {
return outSC2;
}
+
+ public ELDescriptionTree getTree() {
+ return tree;
+ }
}
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNodeComparator.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNodeComparator.java 2008-12-16 10:16:51 UTC (rev 1555)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNodeComparator.java 2008-12-16 16:24:53 UTC (rev 1556)
@@ -78,8 +78,8 @@
return compare;
// compare child nodes
- ELDescriptionNode child1 = node1.getEdges().get(i).getTree();
- ELDescriptionNode child2 = node2.getEdges().get(i).getTree();
+ ELDescriptionNode child1 = node1.getEdges().get(i).getNode();
+ ELDescriptionNode child2 = node2.getEdges().get(i).getNode();
int compare2 = compare(child1, child2);
if(compare2 != 0)
return compare2;
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-12-16 10:16:51 UTC (rev 1555)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-12-16 16:24:53 UTC (rev 1556)
@@ -158,8 +158,8 @@
ObjectProperty op1 = edges.get(j).getLabel();
ObjectProperty op2 = edges.get(k).getLabel();
if(rs.getObjectPropertyHierarchy().isSubpropertyOf(op1, op2)) {
- ELDescriptionNode node1 = edges.get(j).getTree();
- ELDescriptionNode node2 = edges.get(k).getTree();
+ ELDescriptionNode node1 = edges.get(j).getNode();
+ ELDescriptionNode node2 = edges.get(k).getNode();
// check simulation condition
if(node1.in.contains(node2) || node2.in.contains(node1)) {
// node1 is simulated by node2, i.e. we could remove one
@@ -224,7 +224,7 @@
public ELDescriptionNode getNode(int[] position) {
ELDescriptionNode currentNode = rootNode;
for (int i = 0; i < position.length; i++) {
- currentNode = currentNode.getEdges().get(position[i]).getTree();
+ currentNode = currentNode.getEdges().get(position[i]).getNode();
}
return currentNode;
}
@@ -357,7 +357,7 @@
// check whether edges contains an element satisfying SC2
private boolean checkSC2Edge(ELDescriptionEdge superEdge, List<ELDescriptionEdge> edges) {
ObjectProperty superOP = superEdge.getLabel();
- ELDescriptionNode superNode = superEdge.getTree();
+ ELDescriptionNode superNode = superEdge.getNode();
for(ELDescriptionEdge edge : edges) {
// System.out.println("superEdge: " + superEdge);
@@ -367,7 +367,7 @@
// we first check the condition on the properties
if(roleHierarchy.isSubpropertyOf(op, superOP)) {
// check condition on simulations of referred nodes
- ELDescriptionNode node = edge.getTree();
+ ELDescriptionNode node = edge.getNode();
// if(superNode.in.contains(node) || node.in.contains(superNode)) {
if(node.in.contains(superNode)) {
// we found a node satisfying the condition, so we can return
@@ -506,7 +506,7 @@
// edges
for(ELDescriptionEdge edge : oldNode.edges) {
// create a new edge with same label and replace the node the edge points to
- newNode.edges.add(new ELDescriptionEdge(edge.getLabel(), cloneMap.get(edge.getTree())));
+ newNode.edges.add(new ELDescriptionEdge(edge.getLabel(), cloneMap.get(edge.getNode())));
}
}
@@ -514,6 +514,7 @@
// update global tree
treeClone.rootNode = newRoot;
treeClone.maxLevel = maxLevel;
+ treeClone.nodes = new HashSet<ELDescriptionNode>(nodes);
for(int i=1; i<=maxLevel; i++) {
Set<ELDescriptionNode> oldNodes = levelNodeMapping.get(i);
Set<ELDescriptionNode> newNodes = new HashSet<ELDescriptionNode>();
@@ -541,8 +542,8 @@
// 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);
+ new TreeSet<NamedClass>(edge.getNode().getLabel()));
+ cloneRecursively(edge.getNode(), tmp);
}
}
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithm.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithm.java 2008-12-16 10:16:51 UTC (rev 1555)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithm.java 2008-12-16 16:24:53 UTC (rev 1556)
@@ -39,6 +39,7 @@
import org.dllearner.core.owl.Thing;
import org.dllearner.learningproblems.PosNegLP;
import org.dllearner.refinementoperators.ELDown;
+import org.dllearner.refinementoperators.ELDown2;
import org.dllearner.utilities.owl.EvaluatedDescriptionSet;
/**
@@ -55,7 +56,7 @@
private static Logger logger = Logger.getLogger(ELLearningAlgorithm.class);
private ELLearningAlgorithmConfigurator configurator;
- private ELDown operator;
+ private ELDown2 operator;
private boolean isRunning = false;
private boolean stop = false;
@@ -97,7 +98,7 @@
heuristic = new StableHeuristic();
candidates = new TreeSet<SearchTreeNode>(heuristic);
- operator = new ELDown(reasoner);
+ operator = new ELDown2(reasoner);
}
@Override
Modified: trunk/src/dl-learner/org/dllearner/core/SchemaReasoner.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/core/SchemaReasoner.java 2008-12-16 10:16:51 UTC (rev 1555)
+++ trunk/src/dl-learner/org/dllearner/core/SchemaReasoner.java 2008-12-16 16:24:53 UTC (rev 1556)
@@ -101,7 +101,7 @@
public ClassHierarchy getClassHierarchy();
/**
- * Returns more general concepts in the subsumption hierarchy.
+ * Returns direct super classes in the class hierarchy.
*
* @param description
* Atomic concept, top, or bottom.
@@ -110,7 +110,7 @@
public SortedSet<Description> getSuperClasses(Description description);
/**
- * Returns more special concepts in the subsumption hierarchy.
+ * Returns direct sub classes in the class hierarchy.
*
* @param description
* Atomic concept, top, or bottom.
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-12-16 10:16:51 UTC (rev 1555)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-12-16 16:24:53 UTC (rev 1556)
@@ -220,7 +220,7 @@
// recursive call on child node and property range as index
Description range = rs.getRange(edge.getLabel());
// System.out.println(tree + "\nrecurse to:\n" + edge.getTree());
- refinements.addAll(refine(tree, edge.getTree(), range, minimize));
+ refinements.addAll(refine(tree, edge.getNode(), range, minimize));
}
// we found out that, in case we start from the TOP concept
@@ -255,7 +255,7 @@
// 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))) {
+ if(!utility.isDisjoint(getFlattenedConcept(edge.getNode()), opRanges.get(op2))) {
// clone operation
ELDescriptionTree clonedTree = tree.clone();
// find cloned edge and replace its label
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java 2008-12-16 10:16:51 UTC (rev 1555)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java 2008-12-16 16:24:53 UTC (rev 1556)
@@ -20,6 +20,7 @@
package org.dllearner.refinementoperators;
import java.util.Collection;
+import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
@@ -51,7 +52,7 @@
*
* <p>Properties:
* <ul>
- * <li>complete</li>
+ * <li>weakly complete (can be extended to guarantee completeness if desired)</li>
* <li>proper</li>
* <li>finite</li>
* <li>uses class/property hierarchy</li>
@@ -130,55 +131,56 @@
// the transformations can, of course, add new nodes)
Set<ELDescriptionNode> nodes = new HashSet<ELDescriptionNode>(tree.getNodes());
for(ELDescriptionNode v : nodes) {
+ // the position of the node within the tree (needed for getting
+ // the corresponding node in a cloned tree)
+ int[] position = v.getCurrentPosition();
+
// perform operations
- refinements.addAll(extendLabel(tree, v));
- refinements.addAll(refineLabel(tree, v));
- refinements.addAll(refineEdge(tree, v));
- refinements.addAll(attachSubtree(tree, v));
+ refinements.addAll(extendLabel(tree, v, position));
+ refinements.addAll(refineLabel(tree, v, position));
+ refinements.addAll(refineEdge(tree, v, position));
+ refinements.addAll(attachSubtree(tree, v, position));
}
// return refine(tree, tree.getRootNode(), new Thing(), true);
return refinements;
}
-
- private Set<ELDescriptionTree> extendLabel(ELDescriptionTree tree, ELDescriptionNode v) {
- return null;
- }
-
- private Set<ELDescriptionTree> refineLabel(ELDescriptionTree tree, ELDescriptionNode v) {
- return null;
- }
-
- private Set<ELDescriptionTree> refineEdge(ELDescriptionTree tree, ELDescriptionNode v) {
- return null;
- }
-
- private Set<ELDescriptionTree> attachSubtree(ELDescriptionTree tree, ELDescriptionNode v) {
- return null;
- }
-
- private Set<ELDescriptionTree> refine(ELDescriptionTree tree, ELDescriptionNode node, Description index, boolean minimize) {
- // the set of all refinements, which we will return
+
+ // operation 1: label extension
+ private Set<ELDescriptionTree> extendLabel(ELDescriptionTree tree, ELDescriptionNode v, int[] position) {
Set<ELDescriptionTree> refinements = new HashSet<ELDescriptionTree>();
- // the position of the node within the tree (needed for getting
- // the corresponding node in a cloned tree)
- int[] position = node.getCurrentPosition();
+
+ // the index is the range of role in the edge pointing to the parent of this node
+ Description index;
+ if(v.isRoot()) {
+ index = Thing.instance;
+ } else {
+ index = opRanges.get(v.getParentEdge().getLabel());
+ }
- // option 1: label extension
- Set<NamedClass> candidates = utility.getClassCandidates(index, node.getLabel());
+ // call ncc (see paper)
+ Set<NamedClass> candidates = utility.getClassCandidates(index, v.getLabel());
+
for(NamedClass nc : candidates) {
// clone operation
ELDescriptionTree clonedTree = tree.clone();
ELDescriptionNode clonedNode = clonedTree.getNode(position);
// extend label
clonedNode.extendLabel(nc);
- refinements.add(clonedTree);
+ if(clonedTree.isMinimal()) {
+ refinements.add(clonedTree);
+ }
}
+
+ return refinements;
+ }
+
+ // operation 2: label refinement
+ private Set<ELDescriptionTree> refineLabel(ELDescriptionTree tree, ELDescriptionNode v, int[] position) {
+ Set<ELDescriptionTree> refinements = new HashSet<ELDescriptionTree>();
-
- // option 2: label refinement
// loop through all classes in label
- for(NamedClass nc : node.getLabel()) {
+ for(NamedClass nc : v.getLabel()) {
// find all more special classes for the given label
for(Description moreSpecial : rs.getSubClasses(nc)) {
if(moreSpecial instanceof NamedClass) {
@@ -186,117 +188,187 @@
ELDescriptionTree clonedTree = tree.clone();
ELDescriptionNode clonedNode = clonedTree.getNode(position);
-// System.out.println("tree: " + tree);
-// System.out.println("cloned tree: " + clonedTree);
-// System.out.println("node: " + node);
-// System.out.println("cloned unmodified: " + clonedNode);
-
// create refinements by replacing class
clonedNode.replaceInLabel(nc, (NamedClass) moreSpecial);
-// System.out.println("cloned modified: " + clonedNode);
- refinements.add(clonedTree);
+ if(clonedTree.isMinimal()) {
+ refinements.add(clonedTree);
+ }
}
}
}
+
+ return refinements;
+ }
+
+ // operation 3: refine edge
+ private Set<ELDescriptionTree> refineEdge(ELDescriptionTree tree, ELDescriptionNode v, int[] position) {
+ Set<ELDescriptionTree> refinements = new HashSet<ELDescriptionTree>();
+
+ for(int edgeNumber = 0; edgeNumber < v.getEdges().size(); edgeNumber++) {
+ ELDescriptionEdge edge = v.getEdges().get(edgeNumber);
+ ObjectProperty op = edge.getLabel();
+ // find all more special properties
+ for(ObjectProperty op2 : rs.getSubProperties(op)) {
+ // we check whether the range of this property is not disjoint
+ // 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.getNode()), opRanges.get(op2))) {
+ // clone operation
+ ELDescriptionTree clonedTree = tree.clone();
+ // find cloned edge and replace its label
+ clonedTree.getNode(position).refineEdge(edgeNumber, op2);
+// ELDescriptionEdge clonedEdge = clonedTree.getNode(position).getEdges().get(edgeNumber);
+// clonedEdge.setLabel(op2);
+ if(clonedTree.isMinimal()) {
+ refinements.add(clonedTree);
+ }
+ }
+ }
+ }
- // option 3: new edge
+ return refinements;
+ }
+
+ // operation 4: attach tree
+ private Set<ELDescriptionTree> attachSubtree(ELDescriptionTree tree, ELDescriptionNode v, int[] position) {
+ Set<ELDescriptionTree> refinements = new HashSet<ELDescriptionTree>();
+
+ // compute the set of most general roles such that the domain of each role is not disjoint
+ // with the range of the role pointing to this node
+ Description index;
+ if(v.isRoot()) {
+ index = Thing.instance;
+ } else {
+ index = opRanges.get(v.getParentEdge().getLabel());
+ }
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
- Stack<ELDescriptionTree> stack = new Stack<ELDescriptionTree>();
+
+ // TODO: in as ist ein baum t nicht definiert; ersetzen durch t_{C'}
+ // TODO: Einrückung in as nach pick element nicht notwendig
+
+ // loop through most general roles
for(ObjectProperty op : mgr) {
- // clone operation
- ELDescriptionTree clonedTree = tree.clone();
- ELDescriptionNode clonedNode = clonedTree.getNode(position);
- // add a new node and edge
- ELDescriptionNode newNode = new ELDescriptionNode(clonedNode, op, new TreeSet<NamedClass>());
- stack.add(clonedTree);
- // recurse if concept is equivalent
- while(stack.size() != 0) {
- // we pick an arbitrary tree and remove it from the stack
- ELDescriptionTree testTree = stack.pop();
- // 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
- // (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);
- }
- }
+ // a list of subtrees (stored as edges i.e. role + root node which points to tree)
+ // TODO: Do we need to store m at all?
+ LinkedList<ELDescriptionEdge> m = new LinkedList<ELDescriptionEdge>();
+
+ // create tree corresponding to top node
+ ELDescriptionTree topTree = new ELDescriptionTree(rs, Thing.instance);
+
+ // init list with picked role and top node i.e. its root
+ m.add(new ELDescriptionEdge(op, topTree.getRootNode()));
+
+ // iterate until m is empty
+ while(!m.isEmpty()) {
+ // pick and remove first element
+ ELDescriptionEdge edge = m.pollFirst();
+ ObjectProperty r = edge.getLabel();
+ // tp = t' in algorithm description (p stands for prime)
+ ELDescriptionTree tp = edge.getNode().getTree();
+
+ // merge tree into main tree
+ ELDescriptionTree mergedTree = mergeTrees(tree, v, position, r, tp);
+
+ // we check equivalence by a minimality test (TODO: can we still do this?)
+ if(mergedTree.isMinimal()) {
+ // it is not equivalent, i.e. we found a refinement
+ refinements.add(mergedTree);
+ } else {
+ // perform complex check
+ boolean check = asCheck(v);
+
+ if(check) {
+ // refine property
+ for(ObjectProperty subRole : rs.getSubProperties(r)) {
+ m.add(new ELDescriptionEdge(subRole, tp.getRootNode()));
+ }
+ // refine tree using recursive operator call
+ Set<ELDescriptionTree> recRefs = refine(tp);
+ for(ELDescriptionTree tpp : recRefs) {
+ m.add(new ELDescriptionEdge(r, tpp.getRootNode()));
+ }
+ }
+ }
+ }
}
+
+ return refinements;
+ }
+
+ // create a new tree which is obtained by attaching the new tree at the given node in the tree via role r
+ private ELDescriptionTree mergeTrees(ELDescriptionTree tree, ELDescriptionNode node, int[] position, ObjectProperty r, ELDescriptionTree newTree) {
+ // merged tree = tree + new node with role pointing to a new node
+ ELDescriptionTree mergedTree = tree.clone();
+ ELDescriptionNode clonedNode = mergedTree.getNode(position);
+// ELDescriptionNode nodeNew = new ELDescriptionNode(clonedNode, r);
- // option 4: edge refinement
- refinements.addAll(refineEdges(tree, node, position));
+ // create a list of nodes we still need to process
+ LinkedList<ELDescriptionNode> toProcess = new LinkedList<ELDescriptionNode>();
+ toProcess.add(newTree.getRootNode());
- // option 5: child refinement
- for(ELDescriptionEdge edge : node.getEdges()) {
- // recursive call on child node and property range as index
- Description range = rs.getRange(edge.getLabel());
-// System.out.println(tree + "\nrecurse to:\n" + edge.getTree());
- refinements.addAll(refine(tree, edge.getTree(), range, minimize));
- }
+ // map from nodes to cloned nodes
+ Map<ELDescriptionNode,ELDescriptionNode> cloneMap = new HashMap<ELDescriptionNode,ELDescriptionNode>();
+// cloneMap.put(newTree.getRootNode(), nodeNew);
- // 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();
- }
+ // loop until the process list is empty
+ while(!toProcess.isEmpty()) {
+ // process a node
+ ELDescriptionNode v = toProcess.pollFirst();
+ // find parent
+ ELDescriptionNode vp;
+ if(v.isRoot()) {
+ // root is connected to main tree via role r
+ vp = new ELDescriptionNode(clonedNode, r);
+ } else {
+ ELDescriptionNode parent = cloneMap.get(v.getParent());
+ ObjectProperty role = v.getParentEdge().getLabel();
+ Set<NamedClass> label = v.getLabel();
+ // create new node
+ vp = new ELDescriptionNode(parent, role, label);
}
+ cloneMap.put(v, vp);
+ // attach children of node to process list
+ for(ELDescriptionEdge edge : v.getEdges()) {
+ toProcess.add(edge.getNode());
+ }
}
- return refinements;
+ return mergedTree;
}
-
- private Set<ELDescriptionTree> refineEdges(ELDescriptionTree tree, ELDescriptionNode node, int[] position) {
- Set<ELDescriptionTree> refinements = new HashSet<ELDescriptionTree>();
- for(int edgeNumber = 0; edgeNumber < node.getEdges().size(); edgeNumber++) {
- refineEdge(refinements, tree, node, position, edgeNumber);
+
+ private boolean asCheck(ELDescriptionNode v) {
+ // find all edges up to the root node
+ List<ELDescriptionEdge> piVEdges = new LinkedList<ELDescriptionEdge>();
+ ELDescriptionNode tmp = v;
+ while(!tmp.isRoot()) {
+ piVEdges.add(tmp.getParentEdge());
+ tmp = tmp.getParent();
}
- return refinements;
- }
-
- private void refineEdge(Collection<ELDescriptionTree> refinements, ELDescriptionTree tree, ELDescriptionNode node, int[] position, int edgeNumber) {
- ELDescriptionEdge edge = node.getEdges().get(edgeNumber);
- ObjectProperty op = edge.getLabel();
- // find all more special properties
- for(ObjectProperty op2 : rs.getSubProperties(op)) {
- // we check whether the range of this property is not disjoint
- // 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
- clonedTree.getNode(position).refineEdge(edgeNumber, op2);
-// ELDescriptionEdge clonedEdge = clonedTree.getNode(position).getEdges().get(edgeNumber);
-// clonedEdge.setLabel(op2);
- refinements.add(clonedTree);
+
+ // go through all edges
+ for(ELDescriptionEdge piVEdge : piVEdges) {
+ // collect (w,s,w')
+ ELDescriptionNode wp = piVEdge.getNode();
+ ObjectProperty s = piVEdge.getLabel();
+ ELDescriptionNode w = wp.getParent();
+
+ // go through all (w,s,w'') - TODO: s or a new s' ?
+ for(ELDescriptionEdge wEdge : w.getEdges()) {
+ ObjectProperty sp = wEdge.getLabel();
+ ELDescriptionNode wpp = wEdge.getNode();
+ if(s.equals(sp) && wp != wpp) {
+ if(wp.getIn().contains(wpp)) {
+ return false;
+ }
+ }
}
-
}
+
+ return true;
}
// simplifies a potentially nested tree in a flat conjunction by taking
@@ -304,6 +376,7 @@
// C = Professor \sqcap \exists hasChild.Student
// the result would be Professor \sqcap Human (assuming Human is the domain
// of hasChild)
+ // TODO: used in both EL operators => move to utility class
private Description getFlattenedConcept(ELDescriptionNode node) {
Intersection i = new Intersection();
@@ -323,16 +396,6 @@
}
return i;
- }
+ }
-// private void computeMg(Description index) {
-// // compute the applicable properties if this has not been done yet
-// if(app.get(index) == null)
-// app.put(index, utility.computeApplicableObjectProperties(index));
-//
-// mgr.put(index, new TreeSet<ObjectProperty>());
-//
-//
-// }
-
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
