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.utilities.owl;
021
022 import java.util.Comparator;
023 import java.util.Set;
024
025 import org.dllearner.core.owl.BooleanValueRestriction;
026 import org.dllearner.core.owl.Constant;
027 import org.dllearner.core.owl.DatatypeProperty;
028 import org.dllearner.core.owl.DatatypeSomeRestriction;
029 import org.dllearner.core.owl.DatatypeValueRestriction;
030 import org.dllearner.core.owl.DoubleMaxValue;
031 import org.dllearner.core.owl.DoubleMinValue;
032 import org.dllearner.core.owl.Individual;
033 import org.dllearner.core.owl.ObjectAllRestriction;
034 import org.dllearner.core.owl.NamedClass;
035 import org.dllearner.core.owl.Nothing;
036 import org.dllearner.core.owl.Description;
037 import org.dllearner.core.owl.ObjectCardinalityRestriction;
038 import org.dllearner.core.owl.ObjectMaxCardinalityRestriction;
039 import org.dllearner.core.owl.ObjectMinCardinalityRestriction;
040 import org.dllearner.core.owl.ObjectSomeRestriction;
041 import org.dllearner.core.owl.Intersection;
042 import org.dllearner.core.owl.ObjectValueRestriction;
043 import org.dllearner.core.owl.SimpleDoubleDataRange;
044 import org.dllearner.core.owl.Union;
045 import org.dllearner.core.owl.Negation;
046 import org.dllearner.core.owl.ObjectQuantorRestriction;
047 import org.dllearner.core.owl.Thing;
048
049 /**
050 * Implements a total order on class descriptions. Note that the
051 * comparator is, of course, inconsistent with equals on class
052 * descriptions, because currently two class descriptions are considered
053 * equal if they refer to the same memory address (Java standard), while
054 * this comparator takes the syntax of class descriptions into account.
055 *
056 * TODO Improve implementation (better not to rely on number of children,
057 * make better use of the class hierarchy to avoid too many instanceof
058 * operations e.g. boolean description [union, intersection, negation],
059 * restrictions [card., quantor], classes [top, named, bottom] could
060 * be the first decision criterion).
061 * TODO Add a description how exactly the order is defined.
062 *
063 * @author Jens Lehmann
064 *
065 */
066 public class ConceptComparator implements Comparator<Description> {
067
068 RoleComparator rc = new RoleComparator();
069
070 // private List<AtomicConcept> atomicConcepts = new LinkedList<AtomicConcept>();
071
072 public ConceptComparator() {
073
074 }
075
076 // Liste von atomaren Konzepten wird übergeben, damit eine Ordnung
077 // auf atomaren Konzepten festgelegt werden kann; also keine Stringvergleiche
078 // auf diesen Konzepten notwendig sind
079 // TODO: erstmal nur mit Stringvergleichen, da diese bei atomaren Konzepten
080 // schnell sein könnten, und dann testen, ob vorgegebene Ordnung Geschwindigkeitsvorteile
081 // bringt
082 public ConceptComparator(Set<NamedClass> atomicConcepts) {
083
084 }
085
086 // es werden Annahmen über Konzepte gemacht:
087 // 1. bestehen aus Top, Bottom, AtomicConcept, Negation, MultiConjunction, MultiDisjunction,
088 // Exists, All
089 // 2. MultiConjunction und MultiDisjunction haben min. 2 Kinder
090 //
091 // beachte: z.B. (male AND female) und (female AND male) sind ungleich; sie sind aber
092 // gleich, wenn sie vorher in ordered negation normal form umgewandelt worden, da
093 // dadurch die Anordnung der Kinder festgelegt wird
094 // 1: Konzept 1 ist gröÃer
095 //
096 // Ordnung für atomare Konzepte: Stringvergleich
097 // Ordnung für atomare Rollen: Stringvergleich
098 public int compare(Description concept1, Description concept2) {
099
100 // test whether Intersection/Union really have more than
101 // one child (wastes some performance, but violating those
102 // restrictions can lead to difficult-to-find bugs);
103 // we test on concept2, which is the problematic case;
104 // comment out if not needed;
105 // note that the code also makes some further assumptions
106 // about how many children certain constructs can have, but
107 // all of those are obvious and unlikely to be cause by
108 // programming errors
109 // TODO: does not work at the moment, because some code
110 // relies on temporarily have these structurs with only
111 // one child
112 // if((concept2 instanceof Intersection || concept2 instanceof Union) && concept2.getChildren().size() < 2) {
113 // throw new Error("Intersection/Union must have at least two children " + concept2);
114 // }
115
116 // classes higher up are in the source code have lower value
117 // (they appear first in class descriptions, because sorted sets
118 // usually use an ascending order)
119 if(concept1 instanceof Nothing) {
120 if(concept2 instanceof Nothing)
121 return 0;
122 else
123 return -1;
124 } else if(concept1 instanceof NamedClass) {
125 if(concept2 instanceof Nothing)
126 return 1;
127 else if(concept2 instanceof NamedClass)
128 return ((NamedClass)concept1).getName().compareTo(((NamedClass)concept2).getName());
129 else
130 return -1;
131 } else if(concept1 instanceof BooleanValueRestriction) {
132 if(concept2 instanceof Nothing || concept2 instanceof NamedClass) {
133 return 1;
134 } else if(concept2 instanceof BooleanValueRestriction) {
135 // first criterion: name of the properties
136 int cmp = rc.compare(((BooleanValueRestriction)concept1).getRestrictedPropertyExpression(), ((BooleanValueRestriction)concept2).getRestrictedPropertyExpression());
137
138 // second criterion: value of the properties (it should rarely happen that
139 // both boolean values are present since this is a contradiction or superfluous)
140 if(cmp == 0) {
141 boolean val1 = ((BooleanValueRestriction)concept1).getBooleanValue();
142 boolean val2 = ((BooleanValueRestriction)concept2).getBooleanValue();
143 if(val1) {
144 if(val2)
145 return 0;
146 else
147 return 1;
148 } else {
149 if(val2)
150 return -1;
151 else
152 return 0;
153 }
154 } else
155 return cmp;
156 } else
157 return -1;
158 } else if(concept1 instanceof DatatypeSomeRestriction) {
159 if(concept2 instanceof Nothing || concept2 instanceof NamedClass || concept2 instanceof BooleanValueRestriction) {
160 return 1;
161 } else if(concept2 instanceof DatatypeSomeRestriction) {
162 DatatypeSomeRestriction dsr = (DatatypeSomeRestriction) concept1;
163 DatatypeProperty dp = (DatatypeProperty) dsr.getRestrictedPropertyExpression();
164 DatatypeSomeRestriction dsr2 = (DatatypeSomeRestriction) concept2;
165 DatatypeProperty dp2 = (DatatypeProperty) dsr2.getRestrictedPropertyExpression();
166
167 // first criterion: name of the properties
168 int cmp = rc.compare(dp, dp2);
169
170 if(cmp == 0) {
171 SimpleDoubleDataRange dr = (SimpleDoubleDataRange) dsr.getDataRange();
172 SimpleDoubleDataRange dr2 = (SimpleDoubleDataRange) dsr2.getDataRange();
173
174 // equal classes
175 if((dr instanceof DoubleMaxValue && dr2 instanceof DoubleMaxValue)
176 || (dr instanceof DoubleMinValue && dr2 instanceof DoubleMinValue)) {
177 double val1 = dr.getValue();
178 double val2 = dr2.getValue();
179 if(val1 > val2)
180 return 1;
181 else if(val1 == val2)
182 return 0;
183 else
184 return -1;
185
186 } else if(dr instanceof DoubleMaxValue)
187 return 1;
188 else
189 return -1;
190 } else
191 return cmp;
192 } else
193 return -1;
194 } else if(concept1 instanceof ObjectValueRestriction) {
195 if(concept2 instanceof Nothing || concept2 instanceof NamedClass || concept2 instanceof BooleanValueRestriction || concept2 instanceof DatatypeSomeRestriction) {
196 return 1;
197 } else if(concept2 instanceof ObjectValueRestriction) {
198 int roleCompare = rc.compare(((ObjectValueRestriction)concept1).getRestrictedPropertyExpression(), ((ObjectValueRestriction)concept2).getRestrictedPropertyExpression());
199
200 if(roleCompare == 0) {
201 Individual value1 = ((ObjectValueRestriction)concept1).getIndividual();
202 Individual value2 = ((ObjectValueRestriction)concept2).getIndividual();
203 return value1.compareTo(value2);
204 } else {
205 return roleCompare;
206 }
207 } else
208 return -1;
209 } else if(concept1 instanceof DatatypeValueRestriction) {
210 if(concept2 instanceof Nothing || concept2 instanceof NamedClass || concept2 instanceof BooleanValueRestriction || concept2 instanceof DatatypeSomeRestriction || concept2 instanceof ObjectValueRestriction) {
211 return 1;
212 } else if(concept2 instanceof DatatypeValueRestriction) {
213 int roleCompare = rc.compare(((DatatypeValueRestriction)concept1).getRestrictedPropertyExpression(), ((DatatypeValueRestriction)concept2).getRestrictedPropertyExpression());
214
215 if(roleCompare == 0) {
216 Constant value1 = ((DatatypeValueRestriction)concept1).getValue();
217 Constant value2 = ((DatatypeValueRestriction)concept2).getValue();
218 return value1.compareTo(value2);
219 } else {
220 return roleCompare;
221 }
222 } else
223 return -1;
224 } else if(concept1 instanceof Thing) {
225 if(concept2 instanceof Nothing || concept2 instanceof NamedClass || concept2 instanceof BooleanValueRestriction || concept2 instanceof DatatypeSomeRestriction || concept2 instanceof ObjectValueRestriction || concept2 instanceof DatatypeValueRestriction)
226 return 1;
227 else if(concept2 instanceof Thing)
228 return 0;
229 else
230 return -1;
231 } else if(concept1 instanceof Negation) {
232 if(concept2.getChildren().size()<1)
233 return 1;
234 else if(concept2 instanceof Negation)
235 return compare(concept1.getChild(0), concept2.getChild(0));
236 else
237 return -1;
238 } else if(concept1 instanceof ObjectSomeRestriction) {
239 if(concept2.getChildren().size()<1 || concept2 instanceof Negation)
240 return 1;
241 else if(concept2 instanceof ObjectSomeRestriction) {
242 int roleCompare = rc.compare(((ObjectQuantorRestriction)concept1).getRole(), ((ObjectQuantorRestriction)concept2).getRole());
243 if(roleCompare == 0)
244 return compare(concept1.getChild(0), concept2.getChild(0));
245 else
246 return roleCompare;
247 }
248 else
249 return -1;
250 } else if(concept1 instanceof ObjectAllRestriction) {
251 if(concept2.getChildren().size()<1 || concept2 instanceof Negation || concept2 instanceof ObjectSomeRestriction)
252 return 1;
253 else if(concept2 instanceof ObjectAllRestriction) {
254 int roleCompare = rc.compare(((ObjectQuantorRestriction)concept1).getRole(), ((ObjectQuantorRestriction)concept2).getRole());
255 if(roleCompare == 0)
256 return compare(concept1.getChild(0), concept2.getChild(0));
257 else
258 return roleCompare;
259 } else
260 return -1;
261 } else if(concept1 instanceof ObjectMinCardinalityRestriction) {
262 if(concept2.getChildren().size()<1 || concept2 instanceof Negation || concept2 instanceof ObjectQuantorRestriction)
263 return 1;
264 // first criterion: object property
265 // second criterion: number
266 // third criterion: children
267 else if(concept2 instanceof ObjectMinCardinalityRestriction) {
268 int roleCompare = rc.compare(((ObjectCardinalityRestriction)concept1).getRole(), ((ObjectCardinalityRestriction)concept2).getRole());
269 if(roleCompare == 0) {
270 Integer number1 = ((ObjectCardinalityRestriction)concept1).getNumber();
271 Integer number2 = ((ObjectCardinalityRestriction)concept2).getNumber();
272 int numberCompare = number1.compareTo(number2);
273 if(numberCompare == 0)
274 return compare(concept1.getChild(0), concept2.getChild(0));
275 else
276 return numberCompare;
277 } else
278 return roleCompare;
279 } else
280 return -1;
281 } else if(concept1 instanceof ObjectMaxCardinalityRestriction) {
282 if(concept2.getChildren().size()<1 || concept2 instanceof Negation || concept2 instanceof ObjectQuantorRestriction || concept2 instanceof ObjectMinCardinalityRestriction)
283 return 1;
284 // first criterion: object property
285 // second criterion: number
286 // third criterion: children
287 else if(concept2 instanceof ObjectMaxCardinalityRestriction) {
288 int roleCompare = rc.compare(((ObjectCardinalityRestriction)concept1).getRole(), ((ObjectCardinalityRestriction)concept2).getRole());
289 if(roleCompare == 0) {
290 Integer number1 = ((ObjectCardinalityRestriction)concept1).getNumber();
291 Integer number2 = ((ObjectCardinalityRestriction)concept2).getNumber();
292 int numberCompare = number1.compareTo(number2);
293 if(numberCompare == 0)
294 return compare(concept1.getChild(0), concept2.getChild(0));
295 else
296 return numberCompare;
297 } else
298 return roleCompare;
299 } else
300 return -1;
301 } else if(concept1 instanceof Intersection) {
302 if(concept2.getChildren().size()<2)
303 return 1;
304 else if(concept2 instanceof Intersection) {
305 int nrOfChildrenConcept1 = concept1.getChildren().size();
306 int nrOfChildrenConcept2 = concept2.getChildren().size();
307
308 if(nrOfChildrenConcept1>nrOfChildrenConcept2)
309 return 1;
310 else if(nrOfChildrenConcept1==nrOfChildrenConcept2) {
311 for(int i=0; i<nrOfChildrenConcept1; i++) {
312 int compareValue = compare(concept1.getChild(i),concept2.getChild(i));
313 if(compareValue>0)
314 return 1;
315 else if(compareValue<0)
316 return -1;
317 }
318 return 0;
319 } else
320 return -1;
321 } else
322 return -1;
323 } else if(concept1 instanceof Union) {
324 if(concept2.getChildren().size()<2 || concept2 instanceof Intersection)
325 return 1;
326 else if(concept2 instanceof Union) {
327 int nrOfChildrenConcept1 = concept1.getChildren().size();
328 int nrOfChildrenConcept2 = concept2.getChildren().size();
329
330 if(nrOfChildrenConcept1>nrOfChildrenConcept2)
331 return 1;
332 else if(nrOfChildrenConcept1==nrOfChildrenConcept2) {
333 for(int i=0; i<nrOfChildrenConcept1; i++) {
334 int compareValue = compare(concept1.getChild(i),concept2.getChild(i));
335 if(compareValue>0)
336 return 1;
337 else if(compareValue<0)
338 return -1;
339 }
340 return 0;
341 } else
342 return -1;
343 } else
344 return -1;
345 } else
346 throw new RuntimeException(concept1.toString());
347 }
348
349 // TODO: Vergleich zwischen ConceptComparators: immer identisch
350 // (testen, ob das bessere Performance bringt)
351 @Override
352 public boolean equals(Object o) {
353 return (o instanceof ConceptComparator);
354 }
355
356 }