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.core.owl;
021
022 import java.util.Set;
023 import java.util.SortedSet;
024 import java.util.TreeMap;
025 import java.util.TreeSet;
026 import java.util.Map.Entry;
027
028 import org.apache.log4j.Logger;
029 import org.dllearner.utilities.owl.ConceptComparator;
030
031 /**
032 * Represents a subsumption hierarchy (ignoring equivalent concepts).
033 *
034 * @author Jens Lehmann
035 *
036 */
037 public class ClassHierarchy {
038
039 public static Logger logger = Logger.getLogger(ClassHierarchy.class);
040
041 ConceptComparator conceptComparator = new ConceptComparator();
042 TreeMap<Description, SortedSet<Description>> subsumptionHierarchyUp;
043 TreeMap<Description, SortedSet<Description>> subsumptionHierarchyDown;
044
045 /**
046 * The arguments specify the superclasses and subclasses of each class. This
047 * is used to build the subsumption hierarchy.
048 * @param subsumptionHierarchyUp Contains super classes for each class.
049 * @param subsumptionHierarchyDown Contains sub classes for each class.
050 */
051 public ClassHierarchy(
052 TreeMap<Description, SortedSet<Description>> subsumptionHierarchyUp,
053 TreeMap<Description, SortedSet<Description>> subsumptionHierarchyDown) {
054
055 this.subsumptionHierarchyUp = subsumptionHierarchyUp;
056 this.subsumptionHierarchyDown = subsumptionHierarchyDown;
057
058 }
059
060 public SortedSet<Description> getSuperClasses(Description concept) {
061 SortedSet<Description> result = subsumptionHierarchyUp.get(concept);
062 if(result == null) {
063 logger.error("Query for super class of " + concept + " in subsumption hierarchy, but the class is not contained in the (upward) hierarchy, e.g. because the class does not exist or is ignored. Returning empty result instead.");
064 return new TreeSet<Description>();
065 }
066
067 // we copy all concepts before returning them such that they cannot be
068 // modified externally
069 return new TreeSet<Description>(result);
070 }
071
072 public SortedSet<Description> getSubClasses(Description concept) {
073 SortedSet<Description> result = subsumptionHierarchyDown.get(concept);
074 if(result == null) {
075 logger.error("Query for sub class of " + concept + " in subsumption hierarchy, but the class is not contained in the (downward) hierarchy, e.g. because the class does not exist or is ignored. Returning empty result instead.");
076 return new TreeSet<Description>();
077 }
078
079 return new TreeSet<Description>(result);
080
081 // commented out, because these hacks just worked around a problem
082 // if (subsumptionHierarchyDown == null) {
083 // return new TreeSet<Description>();
084 // } else if (subsumptionHierarchyDown.get(concept) == null) {
085 // return new TreeSet<Description>();
086 // } else {
087 // return (TreeSet<Description>) subsumptionHierarchyDown.get(concept).clone();
088 // }
089 }
090
091 /**
092 * Computes the siblings of the specified descriptions. Siblings are all those
093 * classes, which are subclasses of a parent of a class and not equal to the
094 * class itself. Note that retrieving siblings is computationally more
095 * expensive than descending/ascending the hierarchy as siblings are computed
096 * when required and not cached.
097 * @param description A named class.
098 * @return A set of named classes, which are siblings of the given class.
099 */
100 public SortedSet<Description> getSiblingClasses(Description description) {
101 Set<Description> superClasses = subsumptionHierarchyUp.get(description);
102 TreeSet<Description> siblingClasses = new TreeSet<Description>(conceptComparator);
103 for(Description superClass : superClasses) {
104 siblingClasses.addAll(subsumptionHierarchyDown.get(superClass));
105 }
106 siblingClasses.remove(description);
107 return siblingClasses;
108 }
109
110 /**
111 * This method modifies the subsumption hierarchy such that for each class,
112 * there is only a single path to reach it via upward and downward
113 * refinement respectively.
114 */
115 public void thinOutSubsumptionHierarchy() {
116 TreeMap<Description, SortedSet<Description>> hierarchyDownNew = new TreeMap<Description, SortedSet<Description>>(
117 conceptComparator);
118 TreeMap<Description, SortedSet<Description>> hierarchyUpNew = new TreeMap<Description, SortedSet<Description>>(
119 conceptComparator);
120
121 Set<Description> conceptsInSubsumptionHierarchy = new TreeSet<Description>(conceptComparator);
122 conceptsInSubsumptionHierarchy.addAll(subsumptionHierarchyUp.keySet());
123 conceptsInSubsumptionHierarchy.addAll(subsumptionHierarchyDown.keySet());
124
125 // add empty sets for each concept
126 for (Description c : conceptsInSubsumptionHierarchy) {
127 hierarchyDownNew.put(c, new TreeSet<Description>(conceptComparator));
128 hierarchyUpNew.put(c, new TreeSet<Description>(conceptComparator));
129 }
130
131 for (Description c : conceptsInSubsumptionHierarchy) {
132 // look whether there are more general concepts
133 // (if yes, pick the first one)
134 SortedSet<Description> moreGeneral = subsumptionHierarchyUp.get(c);
135 if (moreGeneral != null && moreGeneral.size() != 0) {
136 Description chosenParent = moreGeneral.first();
137 hierarchyDownNew.get(chosenParent).add(c);
138 }
139 }
140
141 for (Description c : conceptsInSubsumptionHierarchy) {
142 SortedSet<Description> moreSpecial = subsumptionHierarchyDown.get(c);
143 if (moreSpecial != null && moreSpecial.size() != 0) {
144 Description chosenParent = moreSpecial.first();
145 hierarchyUpNew.get(chosenParent).add(c);
146 }
147 }
148
149 subsumptionHierarchyDown = hierarchyDownNew;
150 subsumptionHierarchyUp = hierarchyUpNew;
151 }
152
153 /**
154 * Implements a subsumption check using the hierarchy (no further reasoning
155 * checks are used).
156 *
157 * @param subClass
158 * The (supposedly) more special class.
159 * @param superClass
160 * The (supposedly) more general class.
161 * @return True if <code>subClass</code> is a subclass of
162 * <code>superclass</code>.
163 */
164 public boolean isSubclassOf(NamedClass subClass, NamedClass superClass) {
165 if (subClass.equals(superClass)) {
166 return true;
167 } else {
168 for (Description moreGeneralClass : subsumptionHierarchyUp.get(subClass)) {
169
170 // search the upper classes of the subclass
171 if (moreGeneralClass instanceof NamedClass) {
172 if (isSubclassOf((NamedClass) moreGeneralClass, superClass)) {
173 return true;
174 }
175 // we reached top, so we can return false (if top is a
176 // direct upper
177 // class, then no other upper classes can exist)
178 } else {
179 return false;
180 }
181 }
182 // we cannot reach the class via any of the upper classes,
183 // so it is not a super class
184 return false;
185 }
186 }
187
188 @Override
189 public String toString() {
190 return toString(false);
191 }
192
193 public String toString(boolean showUpwardHierarchy) {
194 if (showUpwardHierarchy) {
195 String str = "downward subsumption:\n";
196 str += toString(subsumptionHierarchyDown, new Thing(), 0);
197 str += "upward subsumption:\n";
198 str += toString(subsumptionHierarchyUp, new Nothing(), 0);
199 return str;
200 } else {
201 return toString(subsumptionHierarchyDown, new Thing(), 0);
202 }
203 }
204
205 private String toString(TreeMap<Description, SortedSet<Description>> hierarchy,
206 Description concept, int depth) {
207 String str = "";
208 for (int i = 0; i < depth; i++)
209 str += " ";
210 str += concept.toString() + "\n";
211 Set<Description> tmp = hierarchy.get(concept);
212 if (tmp != null) {
213 for (Description c : tmp)
214 str += toString(hierarchy, c, depth + 1);
215 }
216 return str;
217 }
218
219 @Override
220 public ClassHierarchy clone() {
221 return new ClassHierarchy(subsumptionHierarchyUp, subsumptionHierarchyDown);
222 }
223
224 /**
225 * The method computes a new class hierarchy, which is a copy of this
226 * one, but only the specified classes are allowed to occur. For instance,
227 * if we have subclass relationships between 1sYearStudent, Student, and
228 * Person, but Student is not allowed, then there a is a subclass relationship
229 * between 1stYearStudent and Person.
230 * Currently, owl:Thing and owl:Nothing are always allowed for technical
231 * reasons.
232 * @param allowedClasses The classes, which are allowed to occur in the new
233 * class hierarchy.
234 * @return A copy of this hierarchy, which is restricted to a certain set
235 * of classes.
236 */
237 public ClassHierarchy cloneAndRestrict(Set<NamedClass> allowedClasses) {
238 // currently TOP and BOTTOM are always allowed
239 // (TODO would be easier if Thing/Nothing were declared as named classes)
240 Set<Description> allowed = new TreeSet<Description>(conceptComparator);
241 allowed.addAll(allowedClasses);
242 allowed.add(Thing.instance);
243 allowed.add(Nothing.instance);
244
245 // create new maps
246 TreeMap<Description, SortedSet<Description>> subsumptionHierarchyUpNew
247 = new TreeMap<Description, SortedSet<Description>>(conceptComparator);
248 TreeMap<Description, SortedSet<Description>> subsumptionHierarchyDownNew
249 = new TreeMap<Description, SortedSet<Description>>(conceptComparator);
250
251 for(Entry<Description, SortedSet<Description>> entry : subsumptionHierarchyUp.entrySet()) {
252 Description key = entry.getKey();
253 // we only store mappings for allowed classes
254 if(allowed.contains(key)) {
255 // copy the set of all super classes (we consume them until
256 // they are empty)
257 TreeSet<Description> superClasses = new TreeSet<Description>(entry.getValue());
258 // storage for new super classes
259 TreeSet<Description> newSuperClasses = new TreeSet<Description>(conceptComparator);
260
261 while(!superClasses.isEmpty()) {
262 // pick and remove the first element
263 Description d = superClasses.pollFirst();
264 // case 1: it is allowed, so we add it
265 if(allowed.contains(d)) {
266 newSuperClasses.add(d);
267 // case 2: it is not allowed, so we try its super classes
268 } else {
269 Set<Description> tmp = subsumptionHierarchyUp.get(d);
270 superClasses.addAll(tmp);
271 }
272 }
273
274 subsumptionHierarchyUpNew.put(key, newSuperClasses);
275 }
276 }
277
278 // downward case is analogous
279 for(Entry<Description, SortedSet<Description>> entry : subsumptionHierarchyDown.entrySet()) {
280 Description key = entry.getKey();
281 if(allowed.contains(key)) {
282 TreeSet<Description> subClasses = new TreeSet<Description>(entry.getValue());
283 TreeSet<Description> newSubClasses = new TreeSet<Description>(conceptComparator);
284
285 while(!subClasses.isEmpty()) {
286 Description d = subClasses.pollFirst();
287 if(allowed.contains(d)) {
288 newSubClasses.add(d);
289 } else {
290 subClasses.addAll(subsumptionHierarchyDown.get(d));
291 }
292 }
293
294 subsumptionHierarchyDownNew.put(key, newSubClasses);
295 }
296 }
297
298 return new ClassHierarchy(subsumptionHierarchyUpNew, subsumptionHierarchyDownNew);
299 }
300 }