001/**
002 * Copyright (C) 2007 - 2016, 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 */
019package org.dllearner.utilities.owl;
020
021import com.google.common.collect.HashMultimap;
022import com.google.common.collect.Multimap;
023import org.dllearner.core.AbstractReasonerComponent;
024import org.semanticweb.owlapi.model.*;
025import org.semanticweb.owlapi.util.OWLObjectDuplicator;
026
027import java.util.*;
028import java.util.Map.Entry;
029
030/**
031 * @author Lorenz Buehmann
032 *
033 */
034public class OWLClassExpressionMinimizer implements OWLClassExpressionVisitorEx<OWLClassExpression>{
035        
036        private OWLDataFactory df;
037        private AbstractReasonerComponent reasoner;
038        private OWLObjectDuplicator objectDuplicator;
039        
040        private boolean beautify = true;
041        
042        private Map<OWLClassExpression,Map<OWLClassExpression,Boolean>> cachedSubclassOf = new TreeMap<>();
043
044        public OWLClassExpressionMinimizer(OWLDataFactory dataFactory, AbstractReasonerComponent reasoner) {
045                this.df = dataFactory;
046                this.reasoner = reasoner;
047                
048                objectDuplicator = new OWLObjectDuplicator(dataFactory);
049        }
050        
051        public OWLClassExpression minimize(OWLClassExpression ce){
052                return ce.accept(this);
053        }
054        
055        public OWLClassExpression minimizeClone(OWLClassExpression ce){
056                OWLObjectDuplicator objectDuplicator = new OWLObjectDuplicator(df);
057                OWLClassExpression clone = objectDuplicator.duplicateObject(ce);
058                return clone.accept(this);
059        }
060
061        /* (non-Javadoc)
062         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLClass)
063         */
064        @Override
065        public OWLClassExpression visit(OWLClass ce) {
066                return ce;
067        }
068
069        /* (non-Javadoc)
070         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectIntersectionOf)
071         */
072        @Override
073        public OWLClassExpression visit(OWLObjectIntersectionOf ce) {
074                List<OWLClassExpression> operands = ce.getOperandsAsList();
075                //replace operands by the short form
076                for (int i = 0; i < operands.size(); i++) {
077                        operands.set(i, operands.get(i).accept(this));
078                }
079                
080                List<OWLClassExpression> oldOperands = new ArrayList<>(new TreeSet<>(operands));
081                List<OWLClassExpression> newOperands = new ArrayList<>(operands);
082                
083                if(newOperands.size() == 1){
084                        return newOperands.iterator().next().accept(this);
085                }
086                
087                for (int i = 0; i < oldOperands.size(); i++) {
088                        OWLClassExpression op1 = oldOperands.get(i);
089                        for (int j = i + 1; j < oldOperands.size(); j++) {
090                                OWLClassExpression op2 = oldOperands.get(j);
091                                
092                                //remove operand if it is a super class
093                                if(isSubClassOf(op1, op2)){
094                                        newOperands.remove(op2);
095                                } else if(isSubClassOf(op2, op1)){
096                                        newOperands.remove(op1);
097                                }
098                        }
099                }
100                
101                // combine facet restrictions with same p
102                Multimap<OWLDataPropertyExpression, OWLDataSomeValuesFrom> map = HashMultimap.create();
103                for (OWLClassExpression operand : newOperands) {
104                        if(operand instanceof OWLDataSomeValuesFrom) {
105                                map.put(((OWLDataSomeValuesFrom) operand).getProperty(), (OWLDataSomeValuesFrom) operand);
106                        }
107                }
108                for (Entry<OWLDataPropertyExpression, Collection<OWLDataSomeValuesFrom>> entry : map.asMap().entrySet()) {
109                        OWLDataPropertyExpression dp = entry.getKey();
110                        Collection<OWLDataSomeValuesFrom> datapropertyRestrictions = entry.getValue();
111                        
112                        if(datapropertyRestrictions.size() > 1) {
113                                Set<OWLFacetRestriction> facetRestrictions = new TreeSet<>();
114                                for (OWLDataSomeValuesFrom restriction : datapropertyRestrictions) {
115                                        OWLDataRange dataRange = restriction.getFiller();
116                                        if(dataRange instanceof OWLDatatypeRestriction) {
117                                                facetRestrictions.addAll(((OWLDatatypeRestriction) dataRange).getFacetRestrictions());
118                                        }
119                                }
120                                if(facetRestrictions.size() > 1) {
121                                        OWLDatatype datatype = ((OWLDatatypeRestriction)datapropertyRestrictions.iterator().next().getFiller()).getDatatype();
122                                        OWLDataRange newDataRange = df.getOWLDatatypeRestriction(datatype, facetRestrictions);
123                                        OWLClassExpression newRestriction = df.getOWLDataSomeValuesFrom(dp, newDataRange);
124                                        newOperands.removeAll(datapropertyRestrictions);
125                                        newOperands.add(newRestriction);
126                                }
127                        }
128                }
129                
130                if(newOperands.size() == 1){
131                        return newOperands.iterator().next().accept(this);
132                }
133                
134                return df.getOWLObjectIntersectionOf(new HashSet<>(newOperands));
135        }
136
137        private boolean isSubClassOf(OWLClassExpression subClass, OWLClassExpression superClass) {
138                return superClass.isOWLThing() || reasoner.isSuperClassOf(superClass, subClass);
139        }
140
141        /* (non-Javadoc)
142         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectUnionOf)
143         */
144        @Override
145        public OWLClassExpression visit(OWLObjectUnionOf ce) {
146                List<OWLClassExpression> operands = ce.getOperandsAsList();
147                //replace operands by the short form
148                for (int i = 0; i < operands.size(); i++) {
149                        operands.set(i, operands.get(i).accept(this));
150                }
151                List<OWLClassExpression> oldOperands = new ArrayList<>(new TreeSet<>(operands));
152                List<OWLClassExpression> newOperands = new ArrayList<>(operands);
153                
154                if(newOperands.size() == 1){
155                        return newOperands.iterator().next().accept(this);
156                }
157                
158                for (int i = 0; i < oldOperands.size(); i++) {
159                        OWLClassExpression op1 = oldOperands.get(i);
160                        for (int j = i + 1; j < oldOperands.size(); j++) {
161                                OWLClassExpression op2 = oldOperands.get(j);
162                                
163                                //remove operand if it is a subclass
164                                if(isSubClassOf(op2, op1)){
165                                        newOperands.remove(op2);
166                                } else if(isSubClassOf(op1, op2)){
167                                        newOperands.remove(op1);
168                                } else if(isSubClassOf(op1, df.getOWLObjectComplementOf(op2)) || isSubClassOf(op2, df.getOWLObjectComplementOf(op1))) {
169                                        // check for C or not C
170                                        return df.getOWLThing();
171                                }
172                        }
173                }
174                
175                if(newOperands.size() == 1){
176                        return newOperands.iterator().next().accept(this);
177                }
178                
179                return df.getOWLObjectUnionOf(new HashSet<>(newOperands));
180        }
181
182        /* (non-Javadoc)
183         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectComplementOf)
184         */
185        @Override
186        public OWLClassExpression visit(OWLObjectComplementOf ce) {
187                OWLClassExpression operand = ce.getOperand();
188                OWLClassExpression shortenedOperand = operand.accept(this);
189                if(shortenedOperand.isOWLThing()){// \neg \top \equiv \bot
190                        return df.getOWLNothing();
191                } else if(shortenedOperand.isOWLNothing()){// \neg \bot \equiv \top
192                        return df.getOWLThing();
193                } else if(operand != shortenedOperand){
194                        return df.getOWLObjectComplementOf(shortenedOperand);
195                }
196                return ce;
197        }
198
199        /* (non-Javadoc)
200         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectSomeValuesFrom)
201         */
202        @Override
203        public OWLClassExpression visit(OWLObjectSomeValuesFrom ce) {
204                OWLClassExpression filler = ce.getFiller();
205                OWLClassExpression shortendedFiller = filler.accept(this);
206                if(shortendedFiller.isOWLNothing()){
207                        return df.getOWLNothing();
208                } else if(filler != shortendedFiller){
209                        return df.getOWLObjectSomeValuesFrom(ce.getProperty(), shortendedFiller);
210                }
211                return ce;
212        }
213
214        /* (non-Javadoc)
215         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectAllValuesFrom)
216         */
217        @Override
218        public OWLClassExpression visit(OWLObjectAllValuesFrom ce) {
219                OWLClassExpression filler = ce.getFiller();
220                OWLClassExpression shortendedFiller = filler.accept(this);
221                if(shortendedFiller.isOWLThing()){// \forall r.\top \equiv \top
222                        return df.getOWLThing();
223                } else if(beautify && shortendedFiller.isOWLNothing()) {// \forall r.\bot to \neg \exists r.\top
224                        return df.getOWLObjectComplementOf(df.getOWLObjectSomeValuesFrom(ce.getProperty(), df.getOWLThing()));
225                } else if(filler != shortendedFiller){
226                        return df.getOWLObjectAllValuesFrom(ce.getProperty(), shortendedFiller);
227                }
228                return ce;
229        }
230
231        /* (non-Javadoc)
232         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectHasValue)
233         */
234        @Override
235        public OWLClassExpression visit(OWLObjectHasValue ce) {
236                return ce;
237        }
238
239        /* (non-Javadoc)
240         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectMinCardinality)
241         */
242        @Override
243        public OWLClassExpression visit(OWLObjectMinCardinality ce) {
244                // >= 0 r.C \equiv \top
245                int cardinality = ce.getCardinality();
246                if (cardinality == 0) {
247                        return df.getOWLThing();
248                }
249                OWLClassExpression filler = ce.getFiller();
250                OWLClassExpression shortendedFiller = filler.accept(this);
251                if(shortendedFiller.isOWLNothing()){// >= n r.\bot \equiv \bot if n != 0
252                        return df.getOWLNothing();
253                } else if(filler != shortendedFiller){
254                        return df.getOWLObjectMinCardinality(ce.getCardinality(), ce.getProperty(), shortendedFiller);
255                }
256                return ce;
257        }
258
259        /* (non-Javadoc)
260         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectExactCardinality)
261         */
262        @Override
263        public OWLClassExpression visit(OWLObjectExactCardinality ce) {
264                OWLClassExpression filler = ce.getFiller();
265                OWLClassExpression shortendedFiller = filler.accept(this);
266                if(filler != shortendedFiller){
267                        return df.getOWLObjectExactCardinality(ce.getCardinality(), ce.getProperty(), shortendedFiller);
268                }
269                return ce;
270        }
271
272        /* (non-Javadoc)
273         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectMaxCardinality)
274         */
275        @Override
276        public OWLClassExpression visit(OWLObjectMaxCardinality ce) {
277                OWLClassExpression filler = ce.getFiller();
278                OWLClassExpression shortendedFiller = filler.accept(this);
279                if(shortendedFiller.isOWLNothing()){// <= n r.\bot \equiv \top
280                        return df.getOWLThing();
281                } else if(beautify && ce.getCardinality() == 0) {// we rewrite <= 0 r C to \neg \exists r C - easier to read for humans
282                        return df.getOWLObjectComplementOf(df.getOWLObjectSomeValuesFrom(ce.getProperty(), shortendedFiller));
283                } else if(filler != shortendedFiller){
284                        return df.getOWLObjectMaxCardinality(ce.getCardinality(), ce.getProperty(), shortendedFiller);
285                }
286                return ce;
287        }
288
289        /* (non-Javadoc)
290         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectHasSelf)
291         */
292        @Override
293        public OWLClassExpression visit(OWLObjectHasSelf ce) {
294                return ce;
295        }
296
297        /* (non-Javadoc)
298         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLObjectOneOf)
299         */
300        @Override
301        public OWLClassExpression visit(OWLObjectOneOf ce) {
302                return ce;
303        }
304
305        /* (non-Javadoc)
306         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLDataSomeValuesFrom)
307         */
308        @Override
309        public OWLClassExpression visit(OWLDataSomeValuesFrom ce) {
310                return ce;
311        }
312
313        /* (non-Javadoc)
314         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLDataAllValuesFrom)
315         */
316        @Override
317        public OWLClassExpression visit(OWLDataAllValuesFrom ce) {
318                return ce;
319        }
320
321        /* (non-Javadoc)
322         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLDataHasValue)
323         */
324        @Override
325        public OWLClassExpression visit(OWLDataHasValue ce) {
326                return ce;
327        }
328
329        /* (non-Javadoc)
330         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLDataMinCardinality)
331         */
332        @Override
333        public OWLClassExpression visit(OWLDataMinCardinality ce) {
334                return ce;
335        }
336
337        /* (non-Javadoc)
338         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLDataExactCardinality)
339         */
340        @Override
341        public OWLClassExpression visit(OWLDataExactCardinality ce) {
342                return ce;
343        }
344
345        /* (non-Javadoc)
346         * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitorEx#visit(org.semanticweb.owlapi.model.OWLDataMaxCardinality)
347         */
348        @Override
349        public OWLClassExpression visit(OWLDataMaxCardinality ce) {
350                return ce;
351        }
352}