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}