Source code

001package conexp.fx.core.dl;
002
003import java.util.Collections;
004import java.util.HashMap;
005import java.util.HashSet;
006import java.util.Iterator;
007import java.util.Map;
008import java.util.Map.Entry;
009import java.util.Set;
010import java.util.function.BiFunction;
011import java.util.function.BinaryOperator;
012import java.util.function.Predicate;
013import java.util.stream.Collectors;
014
015import org.semanticweb.owlapi.model.IRI;
016
017import com.google.common.base.Predicates;
018import com.google.common.collect.Sets;
019
020import conexp.fx.core.collections.relation.MatrixRelation;
021
022/*-
023 * #%L
024 * Concept Explorer FX
025 * %%
026 * Copyright (C) 2010 - 2019 Francesco Kriegel
027 * %%
028 * This program is free software: you can redistribute it and/or modify
029 * it under the terms of the GNU General Public License as
030 * published by the Free Software Foundation, either version 3 of the
031 * License, or (at your option) any later version.
032 * 
033 * This program is distributed in the hope that it will be useful,
034 * but WITHOUT ANY WARRANTY; without even the implied warranty of
035 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
036 * GNU General Public License for more details.
037 * 
038 * You should have received a copy of the GNU General Public
039 * License along with this program.  If not, see
040 * <http://www.gnu.org/licenses/gpl-3.0.html>.
041 * #L%
042 */
043
044public class ELInterpretation2<I> {
045
046  private final MatrixRelation<I, IRI>         conceptNameExtensionMatrix;
047  private final Map<IRI, MatrixRelation<I, I>> roleNameExtensionMatrix;
048
049  public ELInterpretation2() {
050    super();
051    this.conceptNameExtensionMatrix = new MatrixRelation<>(false);
052    this.roleNameExtensionMatrix = new HashMap<>();
053  }
054
055  public final Signature getSignature(final boolean onlyActiveSignature) {
056    final Signature sigma = new Signature(IRI.generateDocumentIRI());
057    if (!onlyActiveSignature) {
058      sigma.getConceptNames().addAll(conceptNameExtensionMatrix.colHeads());
059      sigma.getRoleNames().addAll(roleNameExtensionMatrix.keySet());
060    } else {
061      for (IRI A : conceptNameExtensionMatrix.colHeads())
062        if (!conceptNameExtensionMatrix.col(A).isEmpty())
063          sigma.getConceptNames().add(A);
064      for (IRI r : roleNameExtensionMatrix.keySet())
065        if (!roleNameExtensionMatrix.get(r).isEmpty())
066          sigma.getRoleNames().add(r);
067    }
068    return sigma;
069  }
070
071  public final MatrixRelation<I, IRI> getConceptNameExtensionMatrix() {
072    return this.conceptNameExtensionMatrix;
073  }
074
075  public final MatrixRelation<I, I> getRoleNameExtensionMatrix(final IRI roleName) {
076    return this.roleNameExtensionMatrix.computeIfAbsent(roleName, __ -> new MatrixRelation<>(true));
077  }
078
079  public final Map<IRI, MatrixRelation<I, I>> getRoleNameExtensionMatrixMap() {
080    return this.roleNameExtensionMatrix;
081  }
082
083  public final Set<I> getDomain() {
084    return roleNameExtensionMatrix
085        .values()
086        .stream()
087        .reduce((Set<I>) conceptNameExtensionMatrix.rowHeads(), (s, m) -> Sets.union(s, m.colHeads()), Sets::union);
088  }
089
090  public final boolean add(final I i, final IRI A) {
091    return conceptNameExtensionMatrix.add(i, A);
092  }
093
094  public final boolean add(final I i, final String A) {
095    return add(i, IRI.create(A));
096  }
097
098  public final boolean add(final I i, final IRI r, final I j) {
099    return getRoleNameExtensionMatrix(r).add(i, j);
100  }
101
102  public final boolean add(final I i, final String r, final I j) {
103    return add(i, IRI.create(r), j);
104  }
105
106  private final Predicate<I> satisfiesAllExistentialRestrictions(final ELConceptDescription conceptDescription) {
107    return i -> conceptDescription
108        .getExistentialRestrictions()
109        .entries()
110        .parallelStream()
111        .allMatch(
112            e -> roleNameExtensionMatrix.containsKey(e.getKey())
113                && roleNameExtensionMatrix.get(e.getKey()).rowHeads().contains(i)
114                    ? roleNameExtensionMatrix
115                        .get(e.getKey())
116                        .row(i)
117                        .parallelStream()
118                        .anyMatch(j -> isInExtensionOf(j, e.getValue()))
119                    : false);
120  }
121
122  public final Set<I> getExtension(final ELConceptDescription conceptDescription) {
123    if (conceptDescription.isBot())
124      return Collections.emptySet();
125    else if (conceptDescription.isTop())
126      return new HashSet<>(this.getDomain());
127    else
128      return this.conceptNameExtensionMatrix
129          .colAnd(conceptDescription.getConceptNames())
130          .parallelStream()
131          .filter(satisfiesAllExistentialRestrictions(conceptDescription))
132          .collect(Collectors.toSet());
133  }
134
135  public final boolean isInExtensionOf(final I i, final ELConceptDescription conceptDescription) {
136    if (conceptDescription.isBot())
137      return false;
138    else if (conceptDescription.isTop())
139      return true;
140    else
141      return this.conceptNameExtensionMatrix.colAnd(conceptDescription.getConceptNames()).contains(i)
142          && satisfiesAllExistentialRestrictions(conceptDescription).test(i);
143  }
144
145  public final boolean models(final ELConceptInclusion conceptInclusion) {
146    return getDomain()
147        .parallelStream()
148        .allMatch(
149            Predicates
150                .<I> not(i -> isInExtensionOf(i, conceptInclusion.getSubsumee()))
151                .or(i -> isInExtensionOf(i, conceptInclusion.getSubsumer())));
152  }
153
154  public final boolean models(final ELTBox tBox) {
155    return tBox.getConceptInclusions().parallelStream().allMatch(this::models);
156  }
157
158  public final ELConceptDescription getMostSpecificConceptDescription(final I object, final int roleDepth) {
159    if (roleDepth < 0)
160      throw new IllegalArgumentException();
161    else {
162      final ELConceptDescription mmsc = new ELConceptDescription();
163      mmsc.getConceptNames().addAll(conceptNameExtensionMatrix.row(object));
164      if (roleDepth > 0) {
165        for (Entry<IRI, MatrixRelation<I, I>> e : roleNameExtensionMatrix.entrySet())
166          if (e.getValue().rowHeads().contains(object))
167            for (I successor : e.getValue().row(object))
168              mmsc
169                  .getExistentialRestrictions()
170                  .put(e.getKey(), getMostSpecificConceptDescription(successor, roleDepth - 1));
171      }
172      return mmsc.reduce();
173    }
174  }
175
176  public final ELConceptDescription getMostSpecificConceptDescription(final Set<I> objects, final int roleDepth) {
177    if (roleDepth < 0)
178      throw new IllegalArgumentException();
179    else if (objects.isEmpty())
180      return ELConceptDescription.bot();
181    else {
182      final Iterator<I> it = objects.iterator();
183      ELConceptDescription mmsc = getMostSpecificConceptDescription(it.next(), roleDepth);
184      while (it.hasNext())
185        mmsc = ELLeastCommonSubsumer.lcs(mmsc, getMostSpecificConceptDescription(it.next(), roleDepth));
186      return mmsc;
187    }
188//      return objects
189//          .parallelStream()
190//          .reduce(
191//              ELConceptDescription.bot(),
192//              (mmsc, object) -> ELLeastCommonSubsumer.lcs(mmsc, getMostSpecificConceptDescription(object, roleDepth)),
193//              ELLeastCommonSubsumer::lcs)
194//          .reduce();
195  }
196
197  public final ELConceptDescription getMostSpecificConceptDescription2(final Set<I> objects, final int roleDepth) {
198    if (roleDepth < 0)
199      throw new IllegalArgumentException();
200    else if (objects.isEmpty())
201      return ELConceptDescription.bot();
202    else {
203      final ELConceptDescription mmsc = new ELConceptDescription();
204      mmsc.getConceptNames().addAll(this.conceptNameExtensionMatrix.rowAnd(objects));
205      if (roleDepth > 0) {
206        for (Entry<IRI, MatrixRelation<I, I>> e : roleNameExtensionMatrix.entrySet()) {
207          final IRI roleName = e.getKey();
208          final Set<Set<I>> hypergraph = objects
209              .parallelStream()
210              .map(o -> e.getValue().rowHeads().contains(o) ? e.getValue().row(o) : Collections.<I> emptySet())
211              .collect(Collectors.toSet());
212          for (Set<I> mhs : getMinimalHittingSets(hypergraph)) {
213            mmsc.getExistentialRestrictions().put(roleName, getMostSpecificConceptDescription(mhs, roleDepth - 1));
214          }
215        }
216      }
217      return mmsc.reduce();
218    }
219  }
220
221  public static final <T> Set<Set<T>> getMinimalHittingSets(final Set<Set<T>> hypergraph) {
222    if (hypergraph.isEmpty())
223      return Collections.<Set<T>> emptySet();
224    else {
225      final Set<Set<T>> identity = Collections.singleton(Collections.emptySet());
226      final BiFunction<Set<Set<T>>, Set<T>, Set<Set<T>>> accumulator = (hittingSets, factor) -> hittingSets
227          .parallelStream()
228          .flatMap(hittingSet -> factor.parallelStream().map(element -> {
229            final Set<T> newHittingSet = new HashSet<>(hittingSet);
230            newHittingSet.add(element);
231            return newHittingSet;
232          }))
233          .collect(Collectors.toSet());
234      final BinaryOperator<Set<Set<T>>> combiner = (hittingSets1, hittingSets2) -> hittingSets1
235          .parallelStream()
236          .flatMap(hittingSet1 -> hittingSets2.parallelStream().map(hittingSet2 -> {
237            final Set<T> newHittingSet = new HashSet<>(hittingSet1);
238            newHittingSet.addAll(hittingSet2);
239            return newHittingSet;
240          }))
241          .collect(Collectors.toSet());
242      final Set<Set<T>> hittingSets = hypergraph.parallelStream().reduce(identity, accumulator, combiner);
243      final Set<Set<T>> nonMinimalHittingSets = Sets.newConcurrentHashSet();
244      hittingSets.parallelStream().forEach(hittingSet1 -> {
245        if (hittingSets
246            .parallelStream()
247            .anyMatch(hittingSet2 -> hittingSet1.containsAll(hittingSet2) && !hittingSet2.containsAll(hittingSet1)))
248          nonMinimalHittingSets.add(hittingSet1);
249      });
250      hittingSets.removeAll(nonMinimalHittingSets);
251      return hittingSets;
252    }
253  }
254
255  @Override
256  public String toString() {
257    return "Interpretation\r\n" + conceptNameExtensionMatrix + "\r\n" + roleNameExtensionMatrix;
258  }
259
260}