From: <jen...@us...> - 2008-08-04 09:01:48
|
Revision: 1047 http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1047&view=rev Author: jenslehmann Date: 2008-08-04 09:01:44 +0000 (Mon, 04 Aug 2008) Log Message: ----------- structural change in EL trees Modified Paths: -------------- trunk/src/dl-learner/org/dllearner/algorithms/el/Simulation.java trunk/src/dl-learner/org/dllearner/algorithms/el/TreeTuple.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/ELDescriptionEdge.java trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java Removed Paths: ------------- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java trunk/src/dl-learner/org/dllearner/algorithms/el/Edge.java Copied: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionEdge.java (from rev 1046, trunk/src/dl-learner/org/dllearner/algorithms/el/Edge.java) =================================================================== --- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionEdge.java (rev 0) +++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionEdge.java 2008-08-04 09:01:44 UTC (rev 1047) @@ -0,0 +1,62 @@ +/** + * 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 org.dllearner.core.owl.ObjectProperty; + +/** + * A (directed) edge in an EL description tree. It consists of an edge + * label, which is an object property, and the EL description tree + * the edge points to. + * + * @author Jens Lehmann + * + */ +public class ELDescriptionEdge { + + private ObjectProperty label; + + private ELDescriptionNode tree; + + /** + * Constructs and edge given a label and an EL description tree. + * @param label The label of this edge. + * @param tree The tree the edge points to (edges are directed). + */ + public ELDescriptionEdge(ObjectProperty label, ELDescriptionNode tree) { + this.label = label; + this.tree = tree; + } + + /** + * @return The label of this edge. + */ + public ObjectProperty getLabel() { + return label; + } + + /** + * @return The EL description tree + */ + public ELDescriptionNode getTree() { + return tree; + } + +} Copied: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java (from rev 1046, trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java) =================================================================== --- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java (rev 0) +++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-08-04 09:01:44 UTC (rev 1047) @@ -0,0 +1,198 @@ +/** + * 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.LinkedList; +import java.util.List; +import java.util.SortedSet; +import java.util.TreeSet; + +import org.dllearner.core.owl.Description; +import org.dllearner.core.owl.Intersection; +import org.dllearner.core.owl.NamedClass; +import org.dllearner.core.owl.ObjectSomeRestriction; +import org.dllearner.core.owl.Thing; +import org.dllearner.core.owl.UnsupportedLanguageException; + +/** + * Represents an EL description tree, which corresponds to a + * description in the EL description logic. Note that an EL description tree + * can be a subtree of another EL description tree. In general, + * an EL description tree is a tree where the node label is a set + * of named classes and the edges are labelled with a property. + * + * In the documentation below "this node" refers to the root node + * of this EL description (sub-)tree. One tree cannot be reused, + * i.e. used as subtree in several description trees, as some of + * the associated variables (level, simulation) depend on the overall + * tree. + * + * @author Jens Lehmann + * + */ +public class ELDescriptionNode { + + private SortedSet<NamedClass> label; + + private List<ELDescriptionEdge> edges; + + private int level; + + // 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. + */ + public ELDescriptionNode() { + this(new TreeSet<NamedClass>(), new LinkedList<ELDescriptionEdge>()); +// simulation = new Simulation(); + } + + /** + * 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>()); + } + + /** + * 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; + } + + /** + * Constructs an EL description tree from an EL description. + * @param description A description + */ + public ELDescriptionNode(Description description) { + // TODO not implemented + // throw an exception if the description is not in EL + throw new UnsupportedLanguageException(description.toString(), "EL"); + } + + /** + * Checks whether this node has a parent. If the parent link + * is null, the node is considered to be a root node. + * @return True of this is the root node and false otherwise. + */ + public boolean isRoot() { + return parent == null; + } + + /** + * Traverses the EL description tree upwards until it finds + * the root and returns it. + * @return The root node of this EL description tree. + */ + public ELDescriptionNode getRoot() { + ELDescriptionNode root = this; + while(root.parent != null) { + root = parent; + } + return root; + } + + /** + * Traverses the tree until the root node and counts how + * many edges are traversed. If this node does not have a parent, + * zero is returned. This method is used for checking the integrity + * of the tree in unit tests. Use {@link #getLevel()} to get the + * level of the tree. + * @return The level of this node (or more specifically the root + * node of this subtree) within the overall EL description tree. + */ + public int computeLevel() { + ELDescriptionNode root = this; + int level = 0; + while(root.parent != null) { + root = parent; + level++; + } + return level; + } + + /** + * This method transform the tree to an EL description. The + * node labels are transformed to an {@link Intersection} + * of {@link NamedClass}. Each edges is transformed to an + * {@link ObjectSomeRestriction}, where the property is the edge + * label and the child description the subtree the edge points + * to. Edges are also added to the intersection. If the intersection + * is empty, {@link Thing} is returned. + * @return The description corresponding to this EL description tree. + */ + public Description transformToDescription() { + if(label.size()==0 && edges.size()==0) { + return new Thing(); + } else { + Intersection is = new Intersection(); + for(NamedClass nc : label) { + is.addChild(nc); + } + for(ELDescriptionEdge edge : edges) { + Description child = edge.getTree().transformToDescription(); + ObjectSomeRestriction osr = new ObjectSomeRestriction(edge.getLabel(),child); + is.addChild(osr); + } + return is; + } + } + + /** + * @return The label of root node of this subtree. + */ + public SortedSet<NamedClass> getLabel() { + return label; + } + + /** + * @return The outgoing edges of this subtree. + */ + public List<ELDescriptionEdge> getEdges() { + return edges; + } + + /** + * @return The level of the (root node of) this subtree in the overall tree. + */ + public int getLevel() { + return level; + } + + @Override + public ELDescriptionNode clone() { + // TODO implement efficient tree cloning + return null; + } + +} Deleted: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java =================================================================== --- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-08-04 08:43:26 UTC (rev 1046) +++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-08-04 09:01:44 UTC (rev 1047) @@ -1,198 +0,0 @@ -/** - * 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.LinkedList; -import java.util.List; -import java.util.SortedSet; -import java.util.TreeSet; - -import org.dllearner.core.owl.Description; -import org.dllearner.core.owl.Intersection; -import org.dllearner.core.owl.NamedClass; -import org.dllearner.core.owl.ObjectSomeRestriction; -import org.dllearner.core.owl.Thing; -import org.dllearner.core.owl.UnsupportedLanguageException; - -/** - * Represents an EL description tree, which corresponds to a - * description in the EL description logic. Note that an EL description tree - * can be a subtree of another EL description tree. In general, - * an EL description tree is a tree where the node label is a set - * of named classes and the edges are labelled with a property. - * - * In the documentation below "this node" refers to the root node - * of this EL description (sub-)tree. One tree cannot be reused, - * i.e. used as subtree in several description trees, as some of - * the associated variables (level, simulation) depend on the overall - * tree. - * - * @author Jens Lehmann - * - */ -public class ELDescriptionTree { - - private SortedSet<NamedClass> label; - - private List<Edge> edges; - - private int level; - - // parent node in the tree; - // null indicates that this node is a root node - private ELDescriptionTree 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. - */ - public ELDescriptionTree() { - this(new TreeSet<NamedClass>(), new LinkedList<Edge>()); -// simulation = new Simulation(); - } - - /** - * Constructs an EL description tree given its root label. - * @param label Label of the root node. - */ - public ELDescriptionTree(SortedSet<NamedClass> label) { - this(label, new LinkedList<Edge>()); - } - - /** - * 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 ELDescriptionTree(SortedSet<NamedClass> label, List<Edge> edges) { - this.label = label; - this.edges = edges; - } - - /** - * Constructs an EL description tree from an EL description. - * @param description A description - */ - public ELDescriptionTree(Description description) { - // TODO not implemented - // throw an exception if the description is not in EL - throw new UnsupportedLanguageException(description.toString(), "EL"); - } - - /** - * Checks whether this node has a parent. If the parent link - * is null, the node is considered to be a root node. - * @return True of this is the root node and false otherwise. - */ - public boolean isRoot() { - return parent == null; - } - - /** - * Traverses the EL description tree upwards until it finds - * the root and returns it. - * @return The root node of this EL description tree. - */ - public ELDescriptionTree getRoot() { - ELDescriptionTree root = this; - while(root.parent != null) { - root = parent; - } - return root; - } - - /** - * Traverses the tree until the root node and counts how - * many edges are traversed. If this node does not have a parent, - * zero is returned. This method is used for checking the integrity - * of the tree in unit tests. Use {@link #getLevel()} to get the - * level of the tree. - * @return The level of this node (or more specifically the root - * node of this subtree) within the overall EL description tree. - */ - public int computeLevel() { - ELDescriptionTree root = this; - int level = 0; - while(root.parent != null) { - root = parent; - level++; - } - return level; - } - - /** - * This method transform the tree to an EL description. The - * node labels are transformed to an {@link Intersection} - * of {@link NamedClass}. Each edges is transformed to an - * {@link ObjectSomeRestriction}, where the property is the edge - * label and the child description the subtree the edge points - * to. Edges are also added to the intersection. If the intersection - * is empty, {@link Thing} is returned. - * @return The description corresponding to this EL description tree. - */ - public Description transformToDescription() { - if(label.size()==0 && edges.size()==0) { - return new Thing(); - } else { - Intersection is = new Intersection(); - for(NamedClass nc : label) { - is.addChild(nc); - } - for(Edge edge : edges) { - Description child = edge.getTree().transformToDescription(); - ObjectSomeRestriction osr = new ObjectSomeRestriction(edge.getLabel(),child); - is.addChild(osr); - } - return is; - } - } - - /** - * @return The label of root node of this subtree. - */ - public SortedSet<NamedClass> getLabel() { - return label; - } - - /** - * @return The outgoing edges of this subtree. - */ - public List<Edge> getEdges() { - return edges; - } - - /** - * @return The level of the (root node of) this subtree in the overall tree. - */ - public int getLevel() { - return level; - } - - @Override - public ELDescriptionTree clone() { - // TODO implement efficient tree cloning - return null; - } - -} Deleted: trunk/src/dl-learner/org/dllearner/algorithms/el/Edge.java =================================================================== --- trunk/src/dl-learner/org/dllearner/algorithms/el/Edge.java 2008-08-04 08:43:26 UTC (rev 1046) +++ trunk/src/dl-learner/org/dllearner/algorithms/el/Edge.java 2008-08-04 09:01:44 UTC (rev 1047) @@ -1,62 +0,0 @@ -/** - * 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 org.dllearner.core.owl.ObjectProperty; - -/** - * A (directed) edge in an EL description tree. It consists of an edge - * label, which is an object property, and the EL description tree - * the edge points to. - * - * @author Jens Lehmann - * - */ -public class Edge { - - private ObjectProperty label; - - private ELDescriptionTree tree; - - /** - * Constructs and edge given a label and an EL description tree. - * @param label The label of this edge. - * @param tree The tree the edge points to (edges are directed). - */ - public Edge(ObjectProperty label, ELDescriptionTree tree) { - this.label = label; - this.tree = tree; - } - - /** - * @return The label of this edge. - */ - public ObjectProperty getLabel() { - return label; - } - - /** - * @return The EL description tree - */ - public ELDescriptionTree getTree() { - return tree; - } - -} Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/Simulation.java =================================================================== --- trunk/src/dl-learner/org/dllearner/algorithms/el/Simulation.java 2008-08-04 08:43:26 UTC (rev 1046) +++ trunk/src/dl-learner/org/dllearner/algorithms/el/Simulation.java 2008-08-04 09:01:44 UTC (rev 1047) @@ -36,15 +36,15 @@ private List<TreeTuple> relation; // { w | (v,w) \in S } for all w - private Map<ELDescriptionTree,List<ELDescriptionTree>> in; + private Map<ELDescriptionNode,List<ELDescriptionNode>> in; // { v | (v,w) \in S } for all v - private Map<ELDescriptionTree,List<ELDescriptionTree>> out; + private Map<ELDescriptionNode,List<ELDescriptionNode>> out; public Simulation() { relation = new LinkedList<TreeTuple>(); - in = new HashMap<ELDescriptionTree,List<ELDescriptionTree>>(); - out = new HashMap<ELDescriptionTree,List<ELDescriptionTree>>(); + in = new HashMap<ELDescriptionNode,List<ELDescriptionNode>>(); + out = new HashMap<ELDescriptionNode,List<ELDescriptionNode>>(); } /** @@ -59,7 +59,7 @@ if(in.containsKey(tuple.getTree2())) { in.get(tuple.getTree2()).add(tuple.getTree1()); } else { - List<ELDescriptionTree> list = new LinkedList<ELDescriptionTree>(); + List<ELDescriptionNode> list = new LinkedList<ELDescriptionNode>(); list.add(tuple.getTree1()); in.put(tuple.getTree2(), list); } @@ -67,7 +67,7 @@ if(out.containsKey(tuple.getTree1())) { out.get(tuple.getTree1()).add(tuple.getTree2()); } else { - List<ELDescriptionTree> list = new LinkedList<ELDescriptionTree>(); + List<ELDescriptionNode> list = new LinkedList<ELDescriptionNode>(); list.add(tuple.getTree2()); out.put(tuple.getTree1(), list); } @@ -99,11 +99,11 @@ return relation; } - public List<ELDescriptionTree> in(ELDescriptionTree tree) { + public List<ELDescriptionNode> in(ELDescriptionNode tree) { return in.get(tree); } - public List<ELDescriptionTree> out(ELDescriptionTree tree) { + public List<ELDescriptionNode> out(ELDescriptionNode tree) { return out.get(tree); } } Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/TreeTuple.java =================================================================== --- trunk/src/dl-learner/org/dllearner/algorithms/el/TreeTuple.java 2008-08-04 08:43:26 UTC (rev 1046) +++ trunk/src/dl-learner/org/dllearner/algorithms/el/TreeTuple.java 2008-08-04 09:01:44 UTC (rev 1047) @@ -27,11 +27,11 @@ */ public class TreeTuple { - private ELDescriptionTree tree1; + private ELDescriptionNode tree1; - private ELDescriptionTree tree2; + private ELDescriptionNode tree2; - public TreeTuple(ELDescriptionTree tree1, ELDescriptionTree tree2) { + public TreeTuple(ELDescriptionNode tree1, ELDescriptionNode tree2) { this.tree1 = tree1; this.tree2 = tree2; } @@ -40,7 +40,7 @@ * Gets first tree. * @return - first tree */ - public ELDescriptionTree getTree1() { + public ELDescriptionNode getTree1() { return tree1; } @@ -48,7 +48,7 @@ * Gets second tree. * @return - second tree */ - public ELDescriptionTree getTree2() { + public ELDescriptionNode getTree2() { return tree2; } Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java =================================================================== --- trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-08-04 08:43:26 UTC (rev 1046) +++ trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown.java 2008-08-04 09:01:44 UTC (rev 1047) @@ -24,7 +24,7 @@ import java.util.Set; import java.util.TreeMap; -import org.dllearner.algorithms.el.ELDescriptionTree; +import org.dllearner.algorithms.el.ELDescriptionNode; import org.dllearner.core.ReasoningService; import org.dllearner.core.owl.Description; import org.dllearner.core.owl.NamedClass; @@ -95,10 +95,10 @@ 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); - Set<ELDescriptionTree> refinementTrees = refine(tree); + ELDescriptionNode tree = new ELDescriptionNode(concept); + Set<ELDescriptionNode> refinementTrees = refine(tree); Set<Description> refinements = new HashSet<Description>(); - for(ELDescriptionTree refinementTree : refinementTrees) { + for(ELDescriptionNode refinementTree : refinementTrees) { refinements.add(refinementTree.transformToDescription()); } return refinements; @@ -112,12 +112,12 @@ * @param tree Input EL description tree. * @return Set of refined EL description trees. */ - public Set<ELDescriptionTree> refine(ELDescriptionTree tree) { + public Set<ELDescriptionNode> refine(ELDescriptionNode tree) { return refine(tree, new Thing()); } - private Set<ELDescriptionTree> refine(ELDescriptionTree tree, Description index) { - Set<ELDescriptionTree> refinements = new HashSet<ELDescriptionTree>(); + private Set<ELDescriptionNode> refine(ELDescriptionNode tree, Description index) { + Set<ELDescriptionNode> refinements = new HashSet<ELDescriptionNode>(); // option 1: label extension // option 2: label refinement @@ -126,7 +126,7 @@ // find all more special classes for the given label for(Description moreSpecial : rs.getMoreSpecialConcepts(nc)) { // create refinements by replacing class - ELDescriptionTree tmp = tree.clone(); + ELDescriptionNode tmp = tree.clone(); // TODO replace class in label } } Modified: trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java =================================================================== --- trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java 2008-08-04 08:43:26 UTC (rev 1046) +++ trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java 2008-08-04 09:01:44 UTC (rev 1047) @@ -21,7 +21,7 @@ import static org.junit.Assert.*; -import org.dllearner.algorithms.el.ELDescriptionTree; +import org.dllearner.algorithms.el.ELDescriptionNode; import org.dllearner.algorithms.el.Simulation; import org.dllearner.algorithms.el.TreeTuple; import org.junit.Test; @@ -38,8 +38,8 @@ @Test public void simulationTest() { Simulation s = new Simulation(); - ELDescriptionTree t1 = new ELDescriptionTree(); - ELDescriptionTree t2 = new ELDescriptionTree(); + ELDescriptionNode t1 = new ELDescriptionNode(); + ELDescriptionNode t2 = new ELDescriptionNode(); TreeTuple tuple1 = new TreeTuple(t1,t2); s.addTuple(tuple1); assertTrue(s.in(t2).size() == 1); This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |