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