001 /**
002 * Copyright (C) 2007-2011, Jens Lehmann
003 *
004 * This file is part of DL-Learner.
005 *
006 * DL-Learner is free software; you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation; either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * DL-Learner is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program. If not, see <http://www.gnu.org/licenses/>.
018 */
019
020 package org.dllearner.refinementoperators;
021
022 import java.util.Collection;
023 import java.util.HashSet;
024 import java.util.Iterator;
025 import java.util.LinkedList;
026 import java.util.List;
027 import java.util.Map;
028 import java.util.Set;
029 import java.util.SortedSet;
030 import java.util.Stack;
031 import java.util.TreeMap;
032 import java.util.TreeSet;
033
034 import org.dllearner.algorithms.el.ELDescriptionEdge;
035 import org.dllearner.algorithms.el.ELDescriptionNode;
036 import org.dllearner.algorithms.el.ELDescriptionTree;
037 import org.dllearner.core.AbstractReasonerComponent;
038 import org.dllearner.core.owl.Description;
039 import org.dllearner.core.owl.Intersection;
040 import org.dllearner.core.owl.NamedClass;
041 import org.dllearner.core.owl.ObjectProperty;
042 import org.dllearner.core.owl.ObjectPropertyHierarchy;
043 import org.dllearner.core.owl.ClassHierarchy;
044 import org.dllearner.core.owl.Thing;
045
046 /**
047 * EL downward refinement operator constructed by Jens Lehmann
048 * and Christoph Haase. It takes an EL description tree as input
049 * and outputs a set of EL description trees.
050 *
051 * <p>Properties:
052 * <ul>
053 * <li>complete? (still open)</li>
054 * <li>proper</li>
055 * <li>finite</li>
056 * <li>uses class/property hierarchy</li>
057 * <li>takes domain/range into account</li>
058 * <li>uses disjoint classes/classes without common instances</li>
059 * </ul>
060 *
061 * @author Jens Lehmann
062 *
063 */
064 @SuppressWarnings("unused")
065 public class ELDown extends RefinementOperatorAdapter {
066
067 // private static Logger logger = Logger.getLogger(ELDown.class);
068
069 private AbstractReasonerComponent rs;
070
071 // hierarchies
072 private ClassHierarchy subsumptionHierarchy;
073 private ObjectPropertyHierarchy opHierarchy;
074
075 // domains and ranges
076 private Map<ObjectProperty,Description> opDomains = new TreeMap<ObjectProperty,Description>();
077 private Map<ObjectProperty,Description> opRanges = new TreeMap<ObjectProperty,Description>();
078
079 // app_A set of applicable properties for a given class
080 private Map<Description, Set<ObjectProperty>> app = new TreeMap<Description, Set<ObjectProperty>>();
081
082 // most general applicable properties
083 private Map<Description,Set<ObjectProperty>> mgr = new TreeMap<Description,Set<ObjectProperty>>();
084
085 // utility class
086 private Utility utility;
087
088 public ELDown(AbstractReasonerComponent rs) {
089 this.rs = rs;
090 utility = new Utility(rs);
091 subsumptionHierarchy = rs.getClassHierarchy();
092 opHierarchy = rs.getObjectPropertyHierarchy();
093
094 // query reasoner for domains and ranges
095 // (because they are used often in the operator)
096 for(ObjectProperty op : rs.getObjectProperties()) {
097 opDomains.put(op, rs.getDomain(op));
098 opRanges.put(op, rs.getRange(op));
099 }
100 }
101
102 /* (non-Javadoc)
103 * @see org.dllearner.refinementoperators.RefinementOperator#refine(org.dllearner.core.owl.Description)
104 */
105 @Override
106 public Set<Description> refine(Description concept) {
107 ELDescriptionTree tree = new ELDescriptionTree(rs, concept);
108 Set<ELDescriptionTree> refinementTrees = refine(tree);
109 // System.out.println("Refinements finished.");
110 Set<Description> refinements = new HashSet<Description>();
111 for(ELDescriptionTree refinementTree : refinementTrees) {
112 refinements.add(refinementTree.transformToDescription());
113 }
114 return refinements;
115 }
116
117 /**
118 * Performs downward refinement for the given tree. The operator
119 * works directly on EL description trees (which differ from the
120 * the tree structures build by descriptions).
121 *
122 * @param tree Input EL description tree.
123 * @return Set of refined EL description trees.
124 */
125 public Set<ELDescriptionTree> refine(ELDescriptionTree tree) {
126 return refine(tree, tree.getRootNode(), new Thing(), true);
127 }
128
129 private Set<ELDescriptionTree> refine(ELDescriptionTree tree, ELDescriptionNode node, Description index, boolean minimize) {
130 // the set of all refinements, which we will return
131 Set<ELDescriptionTree> refinements = new HashSet<ELDescriptionTree>();
132 // the position of the node within the tree (needed for getting
133 // the corresponding node in a cloned tree)
134 int[] position = node.getCurrentPosition();
135
136 // option 1: label extension
137 Set<NamedClass> candidates = utility.getClassCandidates(index, node.getLabel());
138 for(NamedClass nc : candidates) {
139 // clone operation
140 ELDescriptionTree clonedTree = tree.clone();
141 ELDescriptionNode clonedNode = clonedTree.getNode(position);
142 // extend label
143 clonedNode.extendLabel(nc);
144 refinements.add(clonedTree);
145 }
146
147
148 // option 2: label refinement
149 // loop through all classes in label
150 for(NamedClass nc : node.getLabel()) {
151 // find all more special classes for the given label
152 for(Description moreSpecial : rs.getSubClasses(nc)) {
153 if(moreSpecial instanceof NamedClass) {
154 // clone operation
155 ELDescriptionTree clonedTree = tree.clone();
156 ELDescriptionNode clonedNode = clonedTree.getNode(position);
157
158 // System.out.println("tree: " + tree);
159 // System.out.println("cloned tree: " + clonedTree);
160 // System.out.println("node: " + node);
161 // System.out.println("cloned unmodified: " + clonedNode);
162
163 // create refinements by replacing class
164 clonedNode.replaceInLabel(nc, (NamedClass) moreSpecial);
165
166 // System.out.println("cloned modified: " + clonedNode);
167 refinements.add(clonedTree);
168 }
169 }
170 }
171
172 // option 3: new edge
173 SortedSet<ObjectProperty> appOPs = utility.computeApplicableObjectProperties(index);
174 Set<ObjectProperty> mgr = utility.computeMgr(appOPs);
175 // temporary set of all concepts, which still have to pass the equivalence check
176 Stack<ELDescriptionTree> stack = new Stack<ELDescriptionTree>();
177 for(ObjectProperty op : mgr) {
178 // clone operation
179 ELDescriptionTree clonedTree = tree.clone();
180 ELDescriptionNode clonedNode = clonedTree.getNode(position);
181 // add a new node and edge
182 ELDescriptionNode newNode = new ELDescriptionNode(clonedNode, op, new TreeSet<NamedClass>());
183 stack.add(clonedTree);
184
185 // recurse if concept is equivalent
186 while(stack.size() != 0) {
187 // we pick an arbitrary tree and remove it from the stack
188 ELDescriptionTree testTree = stack.pop();
189 // test equivalence (we found out that we can use the
190 // minimality test for equivalence in this case)
191 boolean equivalent = !testTree.isMinimal();
192 // if the tree is equivalent, we need to populate the
193 // stack with refinements (which are later tested for
194 // equivalence)
195 if(equivalent) {
196 // edge refinement
197 // we know that the edge we added is the last one for this node
198 int edgeNr = node.getEdges().size() - 1;
199 ELDescriptionEdge edge = node.getEdges().get(edgeNr);
200 // all refinements of this edge are added to the stack
201 // (set 1 in article)
202 refineEdge(stack, tree, node, position, edgeNr);
203 // perform node refinements in non-minimize-mode
204 // (set 2 in article)
205 // commented out, because didn't make sense to me
206 // refinements.addAll(refineEdges(tree, newNode, position));
207 stack.addAll(refine(tree, newNode, opRanges.get(edge), false));
208 } else {
209 // tree is not equivalent, i.e. a proper refinement
210 refinements.add(testTree);
211 }
212 }
213 }
214
215 // option 4: edge refinement
216 refinements.addAll(refineEdges(tree, node, position));
217
218 // option 5: child refinement
219 for(ELDescriptionEdge edge : node.getEdges()) {
220 // recursive call on child node and property range as index
221 Description range = rs.getRange(edge.getLabel());
222 // System.out.println(tree + "\nrecurse to:\n" + edge.getTree());
223 refinements.addAll(refine(tree, edge.getNode(), range, minimize));
224 }
225
226 // we found out that, in case we start from the TOP concept
227 // (which is assumed in the current implementation), we can
228 // simply throw away all non-minimal concepts
229 if(minimize) {
230 Iterator<ELDescriptionTree> it = refinements.iterator();
231 while(it.hasNext()) {
232 if(!it.next().isMinimal()) {
233 it.remove();
234 }
235 }
236 }
237
238 return refinements;
239 }
240
241 private Set<ELDescriptionTree> refineEdges(ELDescriptionTree tree, ELDescriptionNode node, int[] position) {
242 Set<ELDescriptionTree> refinements = new HashSet<ELDescriptionTree>();
243 for(int edgeNumber = 0; edgeNumber < node.getEdges().size(); edgeNumber++) {
244 refineEdge(refinements, tree, node, position, edgeNumber);
245 }
246 return refinements;
247 }
248
249 private void refineEdge(Collection<ELDescriptionTree> refinements, ELDescriptionTree tree, ELDescriptionNode node, int[] position, int edgeNumber) {
250 ELDescriptionEdge edge = node.getEdges().get(edgeNumber);
251 ObjectProperty op = edge.getLabel();
252 // find all more special properties
253 for(ObjectProperty op2 : rs.getSubProperties(op)) {
254 // we check whether the range of this property is not disjoint
255 // with the existing child node (we do not perform a full disjointness
256 // check, but only compare with the flattened concept to keep the number
257 // of possible disjointness checks finite)
258 if(!utility.isDisjoint(getFlattenedConcept(edge.getNode()), opRanges.get(op2))) {
259 // clone operation
260 ELDescriptionTree clonedTree = tree.clone();
261 // find cloned edge and replace its label
262 clonedTree.getNode(position).refineEdge(edgeNumber, op2);
263 // ELDescriptionEdge clonedEdge = clonedTree.getNode(position).getEdges().get(edgeNumber);
264 // clonedEdge.setLabel(op2);
265 refinements.add(clonedTree);
266 }
267
268 }
269 }
270
271 // simplifies a potentially nested tree in a flat conjunction by taking
272 // the domain of involved roles, e.g. for
273 // C = Professor \sqcap \exists hasChild.Student
274 // the result would be Professor \sqcap Human (assuming Human is the domain
275 // of hasChild)
276 private Description getFlattenedConcept(ELDescriptionNode node) {
277 Intersection i = new Intersection();
278
279 // add all named classes to intersection
280 for(NamedClass nc : node.getLabel()) {
281 i.addChild(nc);
282 }
283 // add domain of all roles to intersection
284 for(ELDescriptionEdge edge : node.getEdges()) {
285 i.addChild(opDomains.get(edge.getLabel()));
286 }
287
288 // if the intersection has just one element, we return
289 // the element itself instead
290 if(i.getChildren().size() == 1) {
291 return i.getChild(0);
292 }
293
294 return i;
295 }
296
297 // private void computeMg(Description index) {
298 // // compute the applicable properties if this has not been done yet
299 // if(app.get(index) == null)
300 // app.put(index, utility.computeApplicableObjectProperties(index));
301 //
302 // mgr.put(index, new TreeSet<ObjectProperty>());
303 //
304 //
305 // }
306
307 }