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.refinementoperators;
020
021import java.util.Collections;
022import java.util.HashSet;
023import java.util.LinkedList;
024import java.util.List;
025import java.util.Set;
026import java.util.SortedSet;
027import java.util.TreeSet;
028
029import org.dllearner.core.owl.OWLObjectUnionOfImplExt;
030import org.semanticweb.owlapi.model.OWLClassExpression;
031import org.semanticweb.owlapi.model.OWLDataFactory;
032import org.semanticweb.owlapi.model.OWLObjectPropertyExpression;
033import org.semanticweb.owlapi.model.OWLObjectSomeValuesFrom;
034import org.semanticweb.owlapi.model.OWLObjectUnionOf;
035
036import uk.ac.manchester.cs.owl.owlapi.OWLDataFactoryImpl;
037
038/**
039 * Math operations related to refinement operators.
040 * 
041 * @author Jens Lehmann
042 *
043 */
044public class MathOperations {
045        
046        private static final OWLDataFactory df = new OWLDataFactoryImpl();
047
048        /**
049         * This function implements the getCombos method. Through the
050         * use of the upper limit, it is guaranteed that it
051         * will never return doublettes, so no special handling for
052         * them is necessary.
053         * 
054         * @see #getCombos(int)
055         * @param number Number to decompose.
056         * @param upperLimit Maximum number allowed in sum.
057         * @param bisher Numbers created so far.
058         * @param combosTmp Temporary list of combinations (filled during run).
059         */
060        private static void decompose(int number, int upperLimit, LinkedList<Integer> bisher, List<List<Integer>> combosTmp) {
061                
062            for (int i = Math.min(number, upperLimit); i >= 1; i--)
063            {
064                
065                LinkedList<Integer> newBisher = null;
066                // für i==0 wird aus Effizienzgründen die bisherige Liste genommen
067                if(i==0) {
068                        newBisher = bisher;
069                        newBisher.add(i);
070                // für zahl - i == 1 muss gar keine Liste erstellt werden, da dann keine
071                // Zerlegung mehr möglich ist
072                } else if(number - i != 1) {
073                        newBisher = cloneList(bisher);
074                        newBisher.add(i);
075                }
076                
077                
078                if (number - i > 1)
079                {
080                    // i wird hinzugefügt, d.h.
081                    // - es muss nur noch zahl - i - 1 zerlegt werden (-1 wegen OR-Symbol)
082                    // - es darf keine größere Zahl als i mehr vorkommen
083                    // (dadurch gehen keine Kombinationen verloren)
084                    decompose(number - i - 1, i, newBisher,combosTmp);
085                }
086                // Fall zahl == i, d.h. es muss nicht weiter zerlegt werden
087                else if(number - i == 0){
088                        combosTmp.add(newBisher);
089                }
090                
091
092            }   
093            
094            // numbers.add(bisher);
095        }
096        
097        /**
098         * Given <code>number</code>, the functions returns all 
099         * combinations of natural numbers plus the number count 
100         * (which can be thought of as the number of interconnecting
101         * symbols between those numbers) adds up to <code>number</code>.
102         * 
103         * It uses an efficient algorithm to achieve this, which can 
104         * handle number=50 in less than a second and number=30 in 
105         * about 10 milliseconds on an average PC.
106         * 
107         * For illustrating the function, the return values of the first numbers
108         * are given:
109         * number = 1: [[1]]
110         * number = 2: [[2]]
111         * number = 3: [[3], [1, 1]]
112         * number = 4: [[4], [2, 1]]
113         * number = 5: [[5], [3, 1], [2, 2], [1, 1, 1]]
114         * number = 6: [[6], [4, 1], [3, 2], [2, 1, 1]]
115         * number = 7: [[7], [5, 1], [4, 2], [3, 3], [3, 1, 1], [2, 2, 1], [1, 1, 1, 1]]
116         * 
117         * @param number A natural number.
118         * @return A two dimensional list constructed as described above.
119         */
120        public static List<List<Integer>> getCombos(int number) {
121                // on Notebook: length 70 in 17 seconds, length 50 in 800ms, length 30 in 15ms          
122                List<List<Integer>> combosTmp = new LinkedList<>();
123                decompose(number, number, new LinkedList<>(), combosTmp);
124                return combosTmp;
125        }
126        
127        /**
128         * Methods for computing combinations with the additional restriction
129         * that <code>maxValue</code> is the highest natural number, which can
130         * occur.
131         * @see #getCombos(int)
132         * @param length Length of construct.
133         * @param maxValue Maximum value which can occur in sum.
134         * @return A two dimensional list constructed in {@link #getCombos(int)}.
135         */
136        public static List<List<Integer>> getCombos(int length, int maxValue) {         
137                List<List<Integer>> combosTmp = new LinkedList<>();
138                decompose(length, maxValue, new LinkedList<>(), combosTmp);
139                return combosTmp;
140        }       
141        
142        @SuppressWarnings("unchecked")
143        private static LinkedList<Integer> cloneList(LinkedList<Integer> list) {
144                return (LinkedList<Integer>) list.clone();
145        }
146        
147        /**
148         * Implements a cross product in the sense that each union in the
149         * base set is extended by each class expression in the new set. 
150         * 
151         * Example:
152         * baseSet = {A1 OR A2, A1 or A3}
153         * newSet = {A1, EXISTS r.A3}
154         * 
155         * Returns:
156         * {A1 OR A2 OR A1, A1 OR A2 OR EXISTS r.A3, A1 OR A3 OR A1, A1 OR A3 OR EXISTS r.A3}
157         * 
158         * If the base set is empty, then the return value are union class descriptions
159         * for each value in newSet (a union with only one concept).
160         * 
161         * @param baseSet A set of union class descriptions.
162         * @param newSet The descriptions to add to each union class descriptions.
163         * @return The "cross product" of baseSet and newSet.
164         */
165        public static SortedSet<OWLObjectUnionOf> incCrossProduct(Set<OWLObjectUnionOf> baseSet, Set<OWLClassExpression> newSet) {
166                SortedSet<OWLObjectUnionOf> retSet = new TreeSet<>();
167        
168                if(baseSet.isEmpty()) {
169                        for(OWLClassExpression c : newSet) {
170                                OWLObjectUnionOf md = df.getOWLObjectUnionOf(c);
171                                retSet.add(md);
172                        }
173                        return retSet;
174                }
175                
176                List<OWLClassExpression> operands;
177                for(OWLObjectUnionOf md : baseSet) {
178                        for(OWLClassExpression c : newSet) {
179                                operands = md.getOperandsAsList();
180                                operands.add(c);
181                                Collections.sort(operands);
182                                OWLObjectUnionOf mdNew = new OWLObjectUnionOfImplExt(operands);
183                                retSet.add(mdNew);
184                        }
185                }
186                
187                return retSet;
188        }       
189        
190        /**
191         * Returns true if the same property is used twice in an object some
192         * restriction, e.g. (EXISTS r.A1 AND A2 AND EXISTS r.A3) returns true,
193         * while (A1 OR A2) and (EXISTS r.A1 AND A2 AND EXISTS s.A3) return false.
194         * Note that the method does not work recursively, e.g. it return false 
195         * for EXISTS r.(EXISTS r.A1 AND A2 AND EXISTS r.A3).
196         * 
197         * @param d OWLClassExpression to test.
198         * @return See description.
199         */
200        public static boolean containsDoubleObjectSomeRestriction(OWLClassExpression d) {
201                Set<OWLObjectPropertyExpression> roles = new HashSet<>();
202                for(OWLClassExpression c : d.getNestedClassExpressions()) {
203                        if(c instanceof OWLObjectSomeValuesFrom) {
204                                OWLObjectPropertyExpression role = ((OWLObjectSomeValuesFrom)c).getProperty();                                                          
205                                boolean roleExists = !roles.add(role);
206                                if(roleExists)
207                                        return true;
208                        }
209                }
210                return false;
211        }
212}