Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner: [648] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2008-02-27 11:27:56
|
Revision: 648
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=648&view=rev
Author: jenslehmann
Date: 2008-02-27 03:27:52 -0800 (Wed, 27 Feb 2008)
Log Message:
-----------
moved refinement operators to own package
Added Paths:
-----------
trunk/src/dl-learner/org/dllearner/operators/
trunk/src/dl-learner/org/dllearner/operators/PsiDown.java
trunk/src/dl-learner/org/dllearner/operators/PsiUp.java
trunk/src/dl-learner/org/dllearner/operators/RhoDRDown.java
trunk/src/dl-learner/org/dllearner/operators/RhoDown.java
Copied: trunk/src/dl-learner/org/dllearner/operators/PsiDown.java (from rev 639, trunk/src/dl-learner/org/dllearner/algorithms/hybridgp/PsiDown.java)
===================================================================
--- trunk/src/dl-learner/org/dllearner/operators/PsiDown.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/operators/PsiDown.java 2008-02-27 11:27:52 UTC (rev 648)
@@ -0,0 +1,245 @@
+package org.dllearner.refinementoperators;
+
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
+
+import org.dllearner.algorithms.refinement.RefinementOperator;
+import org.dllearner.core.ReasoningService;
+import org.dllearner.core.owl.ObjectAllRestriction;
+import org.dllearner.core.owl.NamedClass;
+import org.dllearner.core.owl.Nothing;
+import org.dllearner.core.owl.Description;
+import org.dllearner.core.owl.ObjectSomeRestriction;
+import org.dllearner.core.owl.Intersection;
+import org.dllearner.core.owl.Union;
+import org.dllearner.core.owl.Negation;
+import org.dllearner.core.owl.ObjectProperty;
+import org.dllearner.core.owl.ObjectQuantorRestriction;
+import org.dllearner.core.owl.Thing;
+import org.dllearner.learningproblems.PosNegLP;
+import org.dllearner.utilities.ConceptComparator;
+
+/**
+ * Operatoren Psi-Down und Psi-Up müssen noch so umgeschrieben werden, dass sie
+ * nur konsistente Konzepte (mit korrekten parent-Links) enthalten. Dazu müssen
+ * alle verwendeten atomaren Konzepte geklont werden.
+ *
+ * Außerdem erscheint es ratsam weitere konzeptverkürzende Maßnahmen einzuführen,
+ * z.B. EXISTS r.A => BOTTOM für down bzw. TOP für up
+ * => Konzepte erreichen etwa eine Länge von 20
+ *
+ * @author jl
+ *
+ */
+public class PsiDown implements RefinementOperator {
+
+ ConceptComparator conceptComparator = new ConceptComparator();
+
+ PosNegLP learningProblem;
+ ReasoningService reasoningService;
+
+ private TreeSet<Description> topSet;
+
+ public PsiDown(PosNegLP learningProblem) {
+ this.learningProblem = learningProblem;
+ reasoningService = learningProblem.getReasoningService();
+
+ // Top-Menge erstellen
+ createTopSet();
+ }
+
+ private void createTopSet() {
+ topSet = new TreeSet<Description>(conceptComparator);
+
+ // TOP OR TOP => Was soll mit Refinements passieren, die immer improper sind?
+ Union md = new Union();
+ md.addChild(new Thing());
+ md.addChild(new Thing());
+ topSet.add(md);
+
+ // allgemeinste Konzepte
+ topSet.addAll(reasoningService.getMoreSpecialConcepts(new Thing()));
+
+ // negierte speziellste Konzepte
+ Set<Description> tmp = learningProblem.getReasoningService().getMoreGeneralConcepts(new Nothing());
+ for(Description c : tmp)
+ topSet.add(new Negation(c));
+
+ // EXISTS r.TOP und ALL r.TOP für alle r
+ for(ObjectProperty r : reasoningService.getAtomicRoles()) {
+ topSet.add(new ObjectAllRestriction(r, new Thing()));
+ topSet.add(new ObjectSomeRestriction(r, new Thing()));
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public Set<Description> refine(Description concept) {
+
+ Set<Description> refinements = new HashSet<Description>();
+ Set<Description> tmp = new HashSet<Description>();
+
+ if (concept instanceof Thing) {
+ return (Set<Description>) topSet.clone();
+ } else if (concept instanceof Nothing) {
+ // return new TreeSet<Concept>(conceptComparator);
+ return new HashSet<Description>();
+ } else if (concept instanceof NamedClass) {
+ // beachte: die Funktion gibt bereits nur nicht-äquivalente Konzepte zurück
+ // beachte weiter: die zurückgegebenen Instanzen dürfen nicht verändert werden,
+ // da beim Caching der Subsumptionhierarchie (momentan) keine Kopien gemacht werden
+ // Bottom wird hier ggf. automatisch mit zurückgegeben
+ refinements.addAll(reasoningService.getMoreSpecialConcepts(concept));
+ // negiertes atomares Konzept
+ } else if (concept instanceof Negation && concept.getChild(0) instanceof NamedClass) {
+ tmp.addAll(reasoningService.getMoreGeneralConcepts(concept.getChild(0)));
+
+ // Top rausschmeissen
+ boolean containsTop = false;
+ Iterator<Description> it = tmp.iterator();
+ while(it.hasNext()) {
+ Description c = it.next();
+ if(c instanceof Thing) {
+ it.remove();
+ containsTop = true;
+ }
+ }
+ if(containsTop)
+ refinements.add(new Nothing());
+
+ for(Description c : tmp) {
+ refinements.add(new Negation(c));
+ }
+ } else if (concept instanceof Intersection) {
+ // eines der Elemente kann verfeinert werden
+ for(Description child : concept.getChildren()) {
+
+ // Refinement für das Kind ausführen
+ tmp = refine(child);
+
+ // neue MultiConjunction konstruieren
+ for(Description c : tmp) {
+ // TODO: müssen auch alle Konzepte geklont werden??
+ // hier wird nur eine neue Liste erstellt
+ // => eigentlich muss nicht geklont werden (d.h. deep copy) da
+ // die Konzepte nicht verändert werden während des Algorithmus
+ List<Description> newChildren = new LinkedList<Description>(concept.getChildren());
+ // es muss genau die vorherige Reihenfolge erhalten bleiben
+ // (zumindest bis die Normalform definiert ist)
+ int index = newChildren.indexOf(child);
+ newChildren.add(index, c);
+ newChildren.remove(child);
+ Intersection mc = new Intersection(newChildren);
+ refinements.add(mc);
+ }
+ }
+ } else if (concept instanceof Union) {
+ // eines der Elemente kann verfeinert werden
+ for(Description child : concept.getChildren()) {
+
+ // Refinement für das Kind ausführen
+ // tmp = refine(child);
+ tmp = refine(child);
+ // neue MultiConjunction konstruieren
+ for(Description c : tmp) {
+ List<Description> newChildren = new LinkedList<Description>(concept.getChildren());
+ // es muss genau die vorherige Reihenfolge erhalten bleiben
+ // (zumindest bis die Normalform definiert ist)
+ int index = newChildren.indexOf(child);
+ newChildren.add(index, c);
+ newChildren.remove(child);
+ Union md = new Union(newChildren);
+ refinements.add(md);
+ }
+ }
+
+ // ein Element der Disjunktion kann weggelassen werden
+ for(Description child : concept.getChildren()) {
+ List<Description> newChildren = new LinkedList<Description>(concept.getChildren());
+ newChildren.remove(child);
+ // wenn nur ein Kind da ist, dann wird Disjunktion gleich weggelassen
+ if(newChildren.size()==1)
+ refinements.add(newChildren.get(0));
+ else {
+ Union md = new Union(newChildren);
+ refinements.add(md);
+ }
+ }
+
+ } else if (concept instanceof ObjectSomeRestriction) {
+ tmp = refine(concept.getChild(0));
+ for(Description c : tmp) {
+ refinements.add(new ObjectSomeRestriction(((ObjectQuantorRestriction)concept).getRole(),c));
+ }
+
+ // falls Kind Bottom ist, dann kann exists weggelassen werden
+ if(concept.getChild(0) instanceof Nothing)
+ refinements.add(new Nothing());
+
+ } else if (concept instanceof ObjectAllRestriction) {
+ tmp = refine(concept.getChild(0));
+ for(Description c : tmp) {
+ refinements.add(new ObjectAllRestriction(((ObjectQuantorRestriction)concept).getRole(),c));
+ }
+
+ if(concept.getChild(0) instanceof Nothing)
+ refinements.add(new Nothing());
+
+ // falls es keine spezielleren atomaren Konzepte gibt, dann wird
+ // bottom angehangen => nur wenn es ein atomares Konzept (insbesondere != bottom)
+ // ist
+ // if(tmp.size()==0) {
+ // if(concept.getChild(0) instanceof AtomicConcept && tmp.size()==0) {
+ // refinements.add(new All(((Quantification)concept).getRole(),new Bottom()));
+ //}
+ } else
+ throw new RuntimeException(concept.toString());
+
+ // falls Konzept ungleich Bottom oder Top, dann kann ein Refinement von Top
+ // angehangen werden
+ if(concept instanceof Union || concept instanceof NamedClass ||
+ concept instanceof Negation || concept instanceof ObjectSomeRestriction || concept instanceof ObjectAllRestriction) {
+
+ // es wird AND TOP angehangen
+ Intersection mc = new Intersection();
+ mc.addChild(concept);
+ mc.addChild(new Thing());
+ refinements.add(mc);
+ }
+
+ // Refinements werden jetzt noch bereinigt, d.h. Verschachtelungen von Konjunktionen
+ // werden entfernt; es wird eine neue Menge erzeugt, da die Transformationen die
+ // Ordnung des Konzepts ändern könnten
+ // TODO: eventuell geht das noch effizienter, da die meisten Refinement-Regeln Refinements
+ // von Child-Konzepten sind, die bereits geordnet sind, d.h. man könnte dort eventuell
+ // gleich absichern, dass alle neu hinzugefügten Refinements in geordneter Negationsnormalform
+ // sind
+ // SortedSet<Concept> returnSet = new TreeSet<Concept>(conceptComparator);
+ /*
+
+ Set<Concept> returnSet = new HashSet<Concept>();
+ for(Concept c : refinements) {
+ ConceptTransformation.cleanConcept(c);
+ // ConceptTransformation.transformToOrderedNegationNormalForm(c, conceptComparator);
+ returnSet.add(c);
+ }
+
+ return returnSet;
+ */
+
+ // Zwischenschritt wird weggelassen - man muss nicht alle Konzepte cleanen,
+ // um dann nur eins davon auszuwählen
+
+ return refinements;
+
+ }
+
+ public Set<Description> refine(Description concept, int maxLength,
+ List<Description> knownRefinements) {
+ throw new RuntimeException();
+ }
+
+}
Copied: trunk/src/dl-learner/org/dllearner/operators/PsiUp.java (from rev 639, trunk/src/dl-learner/org/dllearner/algorithms/hybridgp/PsiUp.java)
===================================================================
--- trunk/src/dl-learner/org/dllearner/operators/PsiUp.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/operators/PsiUp.java 2008-02-27 11:27:52 UTC (rev 648)
@@ -0,0 +1,221 @@
+package org.dllearner.refinementoperators;
+
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
+
+import org.dllearner.algorithms.refinement.RefinementOperator;
+import org.dllearner.core.ReasoningService;
+import org.dllearner.core.owl.ObjectAllRestriction;
+import org.dllearner.core.owl.NamedClass;
+import org.dllearner.core.owl.Nothing;
+import org.dllearner.core.owl.Description;
+import org.dllearner.core.owl.ObjectSomeRestriction;
+import org.dllearner.core.owl.Intersection;
+import org.dllearner.core.owl.Union;
+import org.dllearner.core.owl.Negation;
+import org.dllearner.core.owl.ObjectProperty;
+import org.dllearner.core.owl.ObjectQuantorRestriction;
+import org.dllearner.core.owl.Thing;
+import org.dllearner.learningproblems.PosNegLP;
+import org.dllearner.utilities.ConceptComparator;
+
+public class PsiUp implements RefinementOperator {
+
+ ConceptComparator conceptComparator = new ConceptComparator();
+
+ PosNegLP learningProblem;
+ ReasoningService reasoningService;
+
+ private TreeSet<Description> bottomSet;
+
+ public PsiUp(PosNegLP learningProblem) {
+ this.learningProblem = learningProblem;
+ reasoningService = learningProblem.getReasoningService();
+
+ // Top-Menge erstellen
+ createBottomSet();
+ }
+
+ private void createBottomSet() {
+ bottomSet = new TreeSet<Description>(conceptComparator);
+
+ // BOTTOM AND BOTTOM
+ Intersection mc = new Intersection();
+ mc.addChild(new Nothing());
+ mc.addChild(new Nothing());
+ bottomSet.add(mc);
+
+ // speziellste Konzepte
+ bottomSet.addAll(reasoningService.getMoreGeneralConcepts(new Nothing()));
+
+ // negierte allgemeinste Konzepte
+ Set<Description> tmp = reasoningService.getMoreSpecialConcepts(new Thing());
+ for(Description c : tmp)
+ bottomSet.add(new Negation(c));
+
+ // EXISTS r.BOTTOM und ALL r.BOTTOM für alle r
+ for(ObjectProperty r : reasoningService.getAtomicRoles()) {
+ bottomSet.add(new ObjectAllRestriction(r, new Nothing()));
+ bottomSet.add(new ObjectSomeRestriction(r, new Nothing()));
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public Set<Description> refine(Description concept) {
+
+ Set<Description> refinements = new HashSet<Description>();
+ Set<Description> tmp = new HashSet<Description>();
+
+ if (concept instanceof Thing) {
+ return new TreeSet<Description>(conceptComparator);
+ } else if (concept instanceof Nothing) {
+ return (Set<Description>) bottomSet.clone();
+ } else if (concept instanceof NamedClass) {
+ // Top darf hier mit dabei sein
+ refinements.addAll(reasoningService.getMoreGeneralConcepts(concept));
+
+ // negiertes atomares Konzept
+ } else if (concept instanceof Negation && concept.getChild(0) instanceof NamedClass) {
+ tmp.addAll(reasoningService.getMoreSpecialConcepts(concept.getChild(0)));
+
+ // Bottom rausschmeissen
+ boolean containsBottom = false;
+ Iterator<Description> it = tmp.iterator();
+ while(it.hasNext()) {
+ Description c = it.next();
+ if(c instanceof Nothing) {
+ it.remove();
+ containsBottom = true;
+ }
+ }
+ // es soll z.B. NOT male auch zu NOT BOTTOM d.h. zu TOP verfeinert
+ // werden können
+ if(containsBottom)
+ refinements.add(new Thing());
+
+ for(Description c : tmp) {
+ refinements.add(new Negation(c));
+ }
+ } else if (concept instanceof Intersection) {
+ // eines der Elemente kann verfeinert werden
+ for(Description child : concept.getChildren()) {
+
+ // Refinement für das Kind ausführen
+ tmp = refine(child);
+
+ // neue MultiConjunction konstruieren
+ for(Description c : tmp) {
+ // TODO: müssen auch alle Konzepte geklont werden??
+ // hier wird nur eine neue Liste erstellt
+ // => eigentlich muss nicht geklont werden (d.h. deep copy) da
+ // die Konzepte nicht verändert werden während des Algorithmus
+ List<Description> newChildren = new LinkedList<Description>(concept.getChildren());
+ // es muss genau die vorherige Reihenfolge erhalten bleiben
+ // (zumindest bis die Normalform definiert ist)
+ int index = newChildren.indexOf(child);
+ newChildren.add(index, c);
+ newChildren.remove(child);
+ Intersection mc = new Intersection(newChildren);
+ refinements.add(mc);
+ }
+ }
+
+ // ein Element der Konjunktion kann weggelassen werden
+ for(Description child : concept.getChildren()) {
+ List<Description> newChildren = new LinkedList<Description>(concept.getChildren());
+ newChildren.remove(child);
+ if(newChildren.size()==1)
+ refinements.add(newChildren.get(0));
+ else {
+ Intersection md = new Intersection(newChildren);
+ refinements.add(md);
+ }
+ }
+ } else if (concept instanceof Union) {
+ // eines der Elemente kann verfeinert werden
+ for(Description child : concept.getChildren()) {
+
+ // Refinement für das Kind ausführen
+ // tmp = refine(child);
+ tmp = refine(child);
+ // neue MultiConjunction konstruieren
+ for(Description c : tmp) {
+ List<Description> newChildren = new LinkedList<Description>(concept.getChildren());
+ // es muss genau die vorherige Reihenfolge erhalten bleiben
+ // (zumindest bis die Normalform definiert ist)
+ int index = newChildren.indexOf(child);
+ newChildren.add(index, c);
+ newChildren.remove(child);
+ Union md = new Union(newChildren);
+ refinements.add(md);
+ }
+ }
+ } else if (concept instanceof ObjectSomeRestriction) {
+ tmp = refine(concept.getChild(0));
+ for(Description c : tmp) {
+ refinements.add(new ObjectSomeRestriction(((ObjectQuantorRestriction)concept).getRole(),c));
+ }
+
+ if(concept.getChild(0) instanceof Thing)
+ refinements.add(new Thing());
+
+ } else if (concept instanceof ObjectAllRestriction) {
+ tmp = refine(concept.getChild(0));
+ for(Description c : tmp) {
+ refinements.add(new ObjectAllRestriction(((ObjectQuantorRestriction)concept).getRole(),c));
+ }
+
+ if(concept.getChild(0) instanceof Thing)
+ refinements.add(new Thing());
+
+ // falls es keine spezielleren atomaren Konzepte gibt, dann wird
+ // bottom angehangen => nur wenn es ein atomares Konzept (insbesondere != bottom)
+ // ist
+ // if(tmp.size()==0) {
+ // if(concept.getChild(0) instanceof AtomicConcept && tmp.size()==0) {
+ // refinements.add(new All(((Quantification)concept).getRole(),new Bottom()));
+ //}
+ } else
+ throw new RuntimeException(concept.toString());
+
+ if(concept instanceof Union || concept instanceof NamedClass ||
+ concept instanceof Negation || concept instanceof ObjectSomeRestriction || concept instanceof ObjectAllRestriction) {
+
+ // es wird OR BOTTOM angehangen
+ Union md = new Union();
+ md.addChild(concept);
+ md.addChild(new Nothing());
+ refinements.add(md);
+ }
+
+ // Refinements werden jetzt noch bereinigt, d.h. Verschachtelungen von Konjunktionen
+ // werden entfernt; es wird eine neue Menge erzeugt, da die Transformationen die
+ // Ordnung des Konzepts ändern könnten
+ // TODO: eventuell geht das noch effizienter, da die meisten Refinement-Regeln Refinements
+ // von Child-Konzepten sind, die bereits geordnet sind, d.h. man könnte dort eventuell
+ // gleich absichern, dass alle neu hinzugefügten Refinements in geordneter Negationsnormalform
+ // sind
+ // SortedSet<Concept> returnSet = new TreeSet<Concept>(conceptComparator);
+ /*
+ Set<Concept> returnSet = new HashSet<Concept>();
+ for(Concept c : refinements) {
+ ConceptTransformation.cleanConcept(c);
+ // ConceptTransformation.transformToOrderedNegationNormalForm(c, conceptComparator);
+ returnSet.add(c);
+ }
+
+ return returnSet;
+ */
+ return refinements;
+ }
+
+ public Set<Description> refine(Description concept, int maxLength,
+ List<Description> knownRefinements) {
+ throw new RuntimeException();
+ }
+
+}
Added: trunk/src/dl-learner/org/dllearner/operators/RhoDRDown.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/operators/RhoDRDown.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/operators/RhoDRDown.java 2008-02-27 11:27:52 UTC (rev 648)
@@ -0,0 +1,57 @@
+/**
+ * Copyright (C) 2007-2008, Jens Lehmann
+ *
+ * This file is part of DL-Learner.
+ *
+ * DL-Learner is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * DL-Learner is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+package org.dllearner.refinementoperators;
+
+import java.util.List;
+import java.util.Set;
+
+import org.dllearner.algorithms.refinement.RefinementOperator;
+import org.dllearner.core.owl.Description;
+
+/**
+ * A downward refinement operator, which makes use of domains
+ * and ranges of properties. The operator is currently under
+ * development. Its aim is to span a much "cleaner" and smaller search
+ * tree compared to RhoDown by omitting many class descriptions,
+ * which are obviously too weak, because they violate
+ * domain/range restrictions.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class RhoDRDown implements RefinementOperator {
+
+ /* (non-Javadoc)
+ * @see org.dllearner.algorithms.refinement.RefinementOperator#refine(org.dllearner.core.owl.Description)
+ */
+ public Set<Description> refine(Description concept) {
+ throw new RuntimeException();
+ }
+
+ /* (non-Javadoc)
+ * @see org.dllearner.algorithms.refinement.RefinementOperator#refine(org.dllearner.core.owl.Description, int, java.util.List)
+ */
+ public Set<Description> refine(Description concept, int maxLength,
+ List<Description> knownRefinements) {
+
+ return null;
+ }
+
+}
Copied: trunk/src/dl-learner/org/dllearner/operators/RhoDown.java (from rev 644, trunk/src/dl-learner/org/dllearner/algorithms/refinement/RhoDown.java)
===================================================================
--- trunk/src/dl-learner/org/dllearner/operators/RhoDown.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/operators/RhoDown.java 2008-02-27 11:27:52 UTC (rev 648)
@@ -0,0 +1,766 @@
+/**
+ * Copyright (C) 2007, Jens Lehmann
+ *
+ * This file is part of DL-Learner.
+ *
+ * DL-Learner is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * DL-Learner is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+package org.dllearner.refinementoperators;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import org.dllearner.algorithms.refinement.RefinementOperator;
+import org.dllearner.core.ReasoningService;
+import org.dllearner.core.owl.BooleanValueRestriction;
+import org.dllearner.core.owl.DatatypeProperty;
+import org.dllearner.core.owl.ObjectAllRestriction;
+import org.dllearner.core.owl.NamedClass;
+import org.dllearner.core.owl.Nothing;
+import org.dllearner.core.owl.Description;
+import org.dllearner.core.owl.ObjectSomeRestriction;
+import org.dllearner.core.owl.Intersection;
+import org.dllearner.core.owl.Union;
+import org.dllearner.core.owl.Negation;
+import org.dllearner.core.owl.ObjectProperty;
+import org.dllearner.core.owl.ObjectPropertyExpression;
+import org.dllearner.core.owl.ObjectQuantorRestriction;
+import org.dllearner.core.owl.Thing;
+import org.dllearner.core.owl.ValueRestriction;
+import org.dllearner.utilities.ConceptComparator;
+import org.dllearner.utilities.ConceptTransformation;
+
+/**
+ * Implementation of the downward refinement operator in the DL-Learner refinement
+ * based algorithm.
+ *
+ * See <a href="http://jens-lehmann.org/files/2007_alc_learning_algorithm.pdf"
+ * >http://jens-lehmann.org/files/2007_alc_learning_algorithm.pdf</a> for
+ * details.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class RhoDown implements RefinementOperator {
+
+// private PosNegLP learningProblem;
+ private ReasoningService rs;
+
+ // gibt die Gr��e an bis zu der die Refinements des Top-Konzepts
+ // bereits berechnet worden => entspricht der max. L�nge der Menge M
+ private int topRefinementsLength = 0;
+
+ // die Menge M im Refinement-Operator indiziert nach ihrer L�nge
+ Map<Integer,Set<Description>> m = new HashMap<Integer,Set<Description>>();
+
+ // Zerlegungen der Zahl n in Mengen
+ // Map<Integer,Set<IntegerCombo>> combos = new HashMap<Integer,Set<IntegerCombo>>();
+ Map<Integer, List<List<Integer>>> combos = new HashMap<Integer, List<List<Integer>>>();
+ // abspeichern von Kombinationen während diese rekursiv berechnet werden
+ // private List<List<Integer>> combosTmp;
+
+ // Refinements des Top-Konzept indiziert nach Länge
+ Map<Integer, TreeSet<Description>> topRefinements = new HashMap<Integer, TreeSet<Description>>();
+ Map<Integer, TreeSet<Description>> topRefinementsCumulative = new HashMap<Integer, TreeSet<Description>>();
+
+ // comparator für Konzepte
+ private ConceptComparator conceptComparator = new ConceptComparator();
+
+ // Statistik
+ public long mComputationTimeNs = 0;
+ public long topComputationTimeNs = 0;
+
+ private boolean applyAllFilter = true;
+ private boolean applyExistsFilter = true;
+ private boolean useAllConstructor = true;
+ private boolean useExistsConstructor = true;
+ private boolean useNegation = true;
+ private boolean useBooleanDatatypes = true;
+
+ // braucht man wirklich das learningProblem oder reicht der Reasoning-Service?
+ // TODO: conceptComparator könnte auch noch Parameter sein
+ public RhoDown(ReasoningService reasoningService, boolean applyAllFilter, boolean applyExistsFilter, boolean useAllConstructor,
+ boolean useExistsConstructor, boolean useNegation, boolean useBooleanDatatypes) {
+ this.rs = reasoningService;
+ this.applyAllFilter = applyAllFilter;
+ this.applyExistsFilter = applyExistsFilter;
+ this.useAllConstructor = useAllConstructor;
+ this.useExistsConstructor = useExistsConstructor;
+ this.useNegation = useNegation;
+ this.useBooleanDatatypes = useBooleanDatatypes;
+
+// this.learningProblem = learningProblem;
+// rs = learningProblem.getReasoningService();
+ }
+
+ public Set<Description> refine(Description concept) {
+ throw new RuntimeException();
+ // TODO Auto-generated method stub
+ // return null;
+ }
+
+ // TODO: Methode muss effizienter werden
+ // Hauptproblem ist nicht die Berechnung von M und Top (siehe Benchmarks)
+ // => zuerst muss Objekterzeugung minimiert werden
+ // => als zweites wäre bei nicht ausreichendem Performancegewinn die Implementierung
+ // von Minimallänge eine Möglichkeit (alle Refinements, auch improper, müssten
+ // dann im Algorithmus gespeichert werden)
+ @SuppressWarnings("unchecked")
+ public SortedSet<Description> refine(Description concept, int maxLength,
+ List<Description> knownRefinements) {
+
+
+
+ // Set<Concept> refinements = new HashSet<Concept>();
+ SortedSet<Description> refinements = new TreeSet<Description>(conceptComparator);
+ Set<Description> tmp = new HashSet<Description>();
+ // SortedSet<Concept> tmp = new TreeSet<Concept>(conceptComparator);
+
+ if (concept instanceof Thing) {
+
+ // ggf. Refinements von Top erweitern
+ if(maxLength>topRefinementsLength)
+ computeTopRefinements(maxLength);
+ // System.out.println(topRefinements);
+ refinements = (TreeSet<Description>) topRefinementsCumulative.get(maxLength).clone();
+ // refinements = copyTopRefinements(maxLength);
+ // refinements = topRefinementsCumulative.get(maxLength);
+
+ } else if (concept instanceof Nothing) {
+ // return new HashSet<Concept>();
+ } else if (concept instanceof ValueRestriction) {
+ // value restrictions cannot be further refined
+ } else if (concept instanceof NamedClass) {
+ // Erkenntnisse aus Benchmarks: dieser Teil wird sehr häufig aufgerufen,
+ // allerdings lässt er sich kaum weiter verbessern (selbst ohne klonen
+ // der Konzepte im DIG-Reasoner, was durch das entfernen von Bottom notwendig
+ // ist und außerdem sicherer vor zukünftigen Bugs, wird es nicht wesentlich
+ // schneller)
+
+ // beachte: die Funktion gibt bereits nur nicht-äquivalente Konzepte zurück
+ // TODO: der Cast auf SortedSet ist nur ein Hack und muss später geeignet
+ // behandelt werden
+ refinements = rs.getMoreSpecialConcepts(concept);
+ // refinements.addAll(learningProblem.getReasoningService().getMoreSpecialConcepts(concept));
+
+ // Bottom rausschmeißen (nicht im Operator vorgesehen)
+ // Iterator<Concept> it = refinements.iterator();
+ // while(it.hasNext()) {
+ // Concept c = it.next();
+ // if(c instanceof Bottom)
+ // it.remove();
+ // }
+ // geht jetzt auch schneller durch conceptComparator
+ refinements.remove(new Nothing());
+
+ // negiertes atomares Konzept
+ } else if (concept instanceof Negation && concept.getChild(0) instanceof NamedClass) {
+
+ tmp = rs.getMoreGeneralConcepts(concept.getChild(0));
+
+ //Iterator<Concept> it = tmp.iterator();
+ //while(it.hasNext()) {
+ // Concept c = it.next();
+ // if(c instanceof Top)
+ // it.remove();
+ //}
+
+ // tmp.remove(new Top());
+
+ for(Description c : tmp) {
+ if(!(c instanceof Thing))
+ refinements.add(new Negation(c));
+ }
+
+ } else if (concept instanceof Intersection) {
+
+ // eines der Elemente kann verfeinert werden
+ for(Description child : concept.getChildren()) {
+
+ // Refinement für das Kind ausführen
+ // System.out.println("child: " + child);
+ // wenn man von maximaler Länge die Länge des Konzepts außer dem aktuell
+ // betrachteten Element abzieht, dann bekommt man neue maxLength
+ tmp = refine(child, maxLength - concept.getLength()+child.getLength(),null);
+
+ // neue MultiConjunction konstruieren
+ for(Description c : tmp) {
+ // TODO: müssen auch alle Konzepte geklont werden??
+ // hier wird nur eine neue Liste erstellt
+ // => eigentlich muss nicht geklont werden (d.h. deep copy) da
+ // die Konzepte nicht verändert werden während des Algorithmus
+ // => es muss geklont werden, da die top refinements nicht verändert
+ // werden dürfen
+ // List<Concept> newChildren = new LinkedList<Concept>(concept.getChildren());
+ // TODO: Class Cast ist nur ein Hack
+ List<Description> newChildren = (List<Description>)((LinkedList)concept.getChildren()).clone();
+ // es muss genau die vorherige Reihenfolge erhalten bleiben
+ // (zumindest bis die Normalform definiert ist)
+ // int index = newChildren.indexOf(child);
+ // newChildren.add(index, c);
+ // newChildren.remove(child);
+ // MultiConjunction mc = new MultiConjunction(newChildren);
+
+ // Index muss jetzt nich mehr erhalten bleiben, da ohnehin
+ // neu sortiert wird
+ newChildren.add(c);
+ newChildren.remove(child);
+ Intersection mc = new Intersection(newChildren);
+
+ // sicherstellten, dass Konzept in negation normal form ist
+ ConceptTransformation.cleanConceptNonRecursive(mc);
+ ConceptTransformation.transformToOrderedNegationNormalFormNonRecursive(mc, conceptComparator);
+
+ refinements.add(mc);
+ }
+
+ }
+
+ } else if (concept instanceof Union) {
+ // eines der Elemente kann verfeinert werden
+ for(Description child : concept.getChildren()) {
+
+ // Refinement für das Kind ausführen
+ // tmp = refine(child);
+ tmp = refine(child, maxLength - concept.getLength()+child.getLength(),null);
+
+
+
+ // neue MultiConjunction konstruieren
+ for(Description c : tmp) {
+ List<Description> newChildren = new LinkedList<Description>(concept.getChildren());
+ // es muss genau die vorherige Reihenfolge erhalten bleiben
+ // (zumindest bis die Normalform definiert ist)
+ // int index = newChildren.indexOf(child);
+ // newChildren.add(index, c);
+ newChildren.remove(child);
+ newChildren.add(c);
+ Union md = new Union(newChildren);
+
+ // sicherstellten, dass Konzept in negation normal form ist
+ // ConceptTransformation.cleanConcept(md); // nicht notwendig, da kein Element einer
+ // Disjunktion auf eine Disjunktion abgebildet wird (nur Top und das ist nie
+ // in einer Disjunktion)
+ ConceptTransformation.transformToOrderedNegationNormalFormNonRecursive(md, conceptComparator);
+
+
+ refinements.add(md);
+ }
+
+
+ }
+
+ } else if (concept instanceof ObjectSomeRestriction) {
+ ObjectPropertyExpression role = ((ObjectQuantorRestriction)concept).getRole();
+
+ // rule 1: EXISTS r.D => EXISTS r.E
+ tmp = refine(concept.getChild(0), maxLength-2, null);
+
+ for(Description c : tmp) {
+ refinements.add(new ObjectSomeRestriction(((ObjectQuantorRestriction)concept).getRole(),c));
+ }
+
+ // rule 2: EXISTS r.D => EXISTS s.D or EXISTS r^-1.D => EXISTS s^-1.D
+ // currently inverse roles are not supported
+ ObjectProperty ar = (ObjectProperty) role;
+ Set<ObjectProperty> moreSpecialRoles = rs.getMoreSpecialRoles(ar);
+ for(ObjectProperty moreSpecialRole : moreSpecialRoles) {
+ refinements.add(new ObjectSomeRestriction(moreSpecialRole, concept.getChild(0)));
+ }
+
+ } else if (concept instanceof ObjectAllRestriction) {
+ ObjectPropertyExpression role = ((ObjectQuantorRestriction)concept).getRole();
+
+ // rule 1: ALL r.D => ALL r.E
+ tmp = refine(concept.getChild(0), maxLength-2, null);
+
+ for(Description c : tmp) {
+ refinements.add(new ObjectAllRestriction(((ObjectQuantorRestriction)concept).getRole(),c));
+ }
+
+ // rule 2: ALL r.D => ALL r.BOTTOM if D is a most specific atomic concept
+ // falls es keine spezielleren atomaren Konzepte gibt, dann wird
+ // bottom angehangen => nur wenn es ein atomares Konzept (insbesondere != bottom)
+ // ist
+ // if(tmp.size()==0) {
+ if(concept.getChild(0) instanceof NamedClass && tmp.size()==0) {
+ refinements.add(new ObjectAllRestriction(((ObjectQuantorRestriction)concept).getRole(),new Nothing()));
+ }
+
+ // rule 3: ALL r.D => ALL s.D or ALL r^-1.D => ALL s^-1.D
+ // currently inverse roles are not supported
+ ObjectProperty ar = (ObjectProperty) role;
+ Set<ObjectProperty> moreSpecialRoles = rs.getMoreSpecialRoles(ar);
+ for(ObjectProperty moreSpecialRole : moreSpecialRoles) {
+ refinements.add(new ObjectAllRestriction(moreSpecialRole, concept.getChild(0)));
+ }
+
+ }
+
+ // falls Konzept ungleich Bottom oder Top, dann kann ein Refinement von Top
+ // angehangen werden
+ if(concept instanceof Union || concept instanceof NamedClass ||
+ concept instanceof Negation || concept instanceof ObjectQuantorRestriction
+ || concept instanceof ValueRestriction) {
+ // long someTimeNsStart = System.nanoTime();
+ // someCount++;
+ // Refinement von Top anhängen
+ int topRefLength = maxLength - concept.getLength() - 1; //-1 wegen zusätzlichem UND
+ // es könnte passieren, das wir hier neue Refinements von Top berechnen müssen
+ if(topRefLength > topRefinementsLength)
+ computeTopRefinements(topRefLength);
+ if(topRefLength>0) {
+ // Set<Concept> topRefs = copyTopRefinements(topRefLength);
+ Set<Description> topRefs = topRefinementsCumulative.get(topRefLength);
+ for(Description c : topRefs) {
+ boolean skip = false;
+
+ // falls Refinement von der Form ALL r ist, dann prüfen, ob
+ // ALL r nicht bereits vorkommt
+ if(applyAllFilter) {
+ if(c instanceof ObjectAllRestriction) {
+ for(Description child : concept.getChildren()) {
+ if(child instanceof ObjectAllRestriction) {
+ ObjectPropertyExpression r1 = ((ObjectAllRestriction)c).getRole();
+ ObjectPropertyExpression r2 = ((ObjectAllRestriction)child).getRole();
+ if(r1.toString().equals(r2.toString()))
+ skip = true;
+ }
+ }
+ }
+ }
+
+ if(!skip) {
+ // MultiConjunction md = new MultiConjunction(concept.getChildren());
+ Intersection mc = new Intersection();
+ mc.addChild(concept);
+ mc.addChild(c);
+
+ // Negationsnormalform herstellen
+ ConceptTransformation.cleanConceptNonRecursive(mc);
+ ConceptTransformation.transformToOrderedNegationNormalFormNonRecursive(mc, conceptComparator);
+
+ refinements.add(mc);
+ }
+ }
+ }
+ // someTimeNs += System.nanoTime() - someTimeNsStart;
+ }
+
+
+
+ // Refinements werden jetzt noch bereinigt, d.h. Verschachtelungen von Konjunktionen
+ // werden entfernt; es wird eine neue Menge erzeugt, da die Transformationen die
+ // Ordnung des Konzepts ändern könnten
+ // TODO: eventuell geht das noch effizienter, da die meisten Refinement-Regeln Refinements
+ // von Child-Konzepten sind, die bereits geordnet sind, d.h. man könnte dort eventuell
+ // gleich absichern, dass alle neu hinzugefügten Refinements in geordneter Negationsnormalform
+ // sind
+ /*
+ SortedSet<Concept> returnSet = new TreeSet<Concept>(conceptComparator);
+ for(Concept c : refinements) {
+ ConceptTransformation.cleanConcept(c);
+ ConceptTransformation.transformToOrderedNegationNormalForm(c, conceptComparator);
+ returnSet.add(c);
+ }
+
+ return returnSet;
+ */
+ // TODO: obiger Code kann noch nicht gelöscht werden (anderes Ergebnis); warum?
+ // => erstmal so implementieren, dass obiger Code nicht mehr gebraucht wird und
+ // im zweiten Schritt dann auf die nicht-rekursiven Methoden umsteigen
+ return refinements;
+ }
+
+
+ // TODO: Methode kann später entfernt werden, es muss nur
+ // sichergestellt werden, dass die refine-Methode an den
+ // kumulativen Top-Refinements nichts ändert
+ @SuppressWarnings("unused")
+ private SortedSet<Description> copyTopRefinements(int maxLength) {
+ // return topRefinementsCumulative.get(maxLength);
+ SortedSet<Description> ret = new TreeSet<Description>(conceptComparator);
+ for(Description c : topRefinementsCumulative.get(maxLength))
+ ret.add(c);
+ return ret;
+ }
+
+
+ // TODO: später private
+ public void computeTopRefinements(int maxLength) {
+ long topComputationTimeStartNs = System.nanoTime();
+
+ // M erweiteren
+ computeM(maxLength);
+
+ // berechnen aller möglichen Kombinationen für Disjunktion,
+ for(int i = topRefinementsLength+1; i <= maxLength; i++) {
+ combos.put(i,getCombos(i));
+ topRefinements.put(i, new TreeSet<Description>(conceptComparator));
+ // topRefinements.put(i, new HashSet<Concept>());
+
+ for(List<Integer> combo : combos.get(i)) {
+ /*
+ // für eine Kombo alle Konzeptkombinationen berechnen
+ Set<Set<Concept>> baseSet = new HashSet<Set<Concept>>();
+ // boolean firstNonEmptyNumber = true;
+ for(Integer j : combo.getNumbers()) {
+ // initialisiert wird mit der passenden Menge m
+ //if(firstNonEmptyNumber || )
+ // baseSet.add(m.get(j));
+ // else {
+ baseSet = incCrossProduct(baseSet,m.get(j));
+ //}
+ }
+
+ // Disjunktionen erzeugen und hinzufügen
+ for(Set<Concept> children : baseSet) {
+ if(children.size() == 1) {
+ Iterator<Concept> it = children.iterator();
+ Concept c = it.next();
+ topRefinements.get(i).add(c);
+ } else {
+ topRefinements.get(i).add(new MultiDisjunction(children));
+ }
+ }
+ */
+
+ /* neue Implementierung */
+
+ // Kombination besteht aus nur einer Zahl => einfach M benutzen
+ // if(combo.getNumbers().size()==1) {
+ if(combo.size()==1) {
+ topRefinements.get(i).addAll(m.get(i));
+ // Kombination besteht aus mehreren Zahlen => Disjunktion erzeugen
+ } else {
+ Set<Union> baseSet = new HashSet<Union>();
+ for(Integer j : combo) { // combo.getNumbers()) {
+ baseSet = incCrossProduct2(baseSet, m.get(j));
+ }
+
+ // Umwandlung aller Konzepte in Negationsnormalform
+ for(Description concept : baseSet) {
+ ConceptTransformation.transformToOrderedNegationNormalForm(concept, conceptComparator);
+ }
+
+ if(applyExistsFilter) {
+ Iterator<Union> it = baseSet.iterator();
+ while(it.hasNext()) {
+ Union md = it.next();
+ boolean remove = false;
+ // falls Exists r für gleiche Rolle zweimal vorkommt,
+ // dann rausschmeißen
+ // Map<AtomicRole,Boolean> roleOccured = new HashMap<AtomicRole,Boolean>();
+ Set<String> roles = new TreeSet<String>();
+ for(Description c : md.getChildren()) {
+ if(c instanceof ObjectSomeRestriction) {
+ String role = ((ObjectSomeRestriction)c).getRole().getName();
+ boolean roleExists = !roles.add(role);
+ // falls Rolle schon vorkommt, dann kann ganzes
+ // Refinement ignoriert werden (man könnte dann auch
+ // gleich abbrechen, aber das hat nur minimalste
+ // Auswirkungen auf Effizienz)
+ if(roleExists)
+ remove = true;
+ }
+ }
+ if(remove)
+ it.remove();
+
+ }
+ }
+
+ topRefinements.get(i).addAll(baseSet);
+ }
+ }
+
+ // neu berechnete Refinements kumulieren, damit sie schneller abgefragt werden können
+ // computeCumulativeTopRefinements(i);
+ TreeSet<Description> cumulativeRefinements = new TreeSet<Description>(conceptComparator);
+ // Set<Concept> cumulativeRefinements = new HashSet<Concept>();
+ for(int j=1; j<=i; j++) {
+ cumulativeRefinements.addAll(topRefinements.get(j));
+ }
+ topRefinementsCumulative.put(i, cumulativeRefinements);
+ }
+
+ // neue Maximallänge eintragen
+ topRefinementsLength = maxLength;
+
+ topComputationTimeNs += System.nanoTime() - topComputationTimeStartNs;
+ }
+
+ // computation of the set M
+ private void computeM(int maxLength) {
+ long mComputationTimeStartNs = System.nanoTime();
+ // System.out.println("compute M from " + (topRefinementsLength+1) + " up to " + maxLength);
+
+ // initialise all not yet initialised lengths
+ // (avoids null pointers in some cases)
+ for(int i=topRefinementsLength+1; i<=maxLength; i++) {
+ m.put(i, new TreeSet<Description>(conceptComparator));
+ }
+
+ // Berechnung der Basiskonzepte in M
+ // TODO: Spezialfälle, dass zwischen Top und Bottom nichts liegt behandeln
+ if(topRefinementsLength==0 && maxLength>0) {
+ // Konzepte der Länge 1 = alle Konzepte, die in der Subsumptionhierarchie unter Top liegen
+ Set<Description> m1 = rs.getMoreSpecialConcepts(new Thing());
+ m.put(1,m1);
+ }
+
+ if(topRefinementsLength<2 && maxLength>1) {
+ // Konzepte der Länge 2 = Negation aller Konzepte, die über Bottom liegen
+ if(useNegation) {
+ Set<Description> m2tmp = rs.getMoreGeneralConcepts(new Nothing());
+ Set<Description> m2 = new TreeSet<Description>(conceptComparator);
+ for(Description c : m2tmp) {
+ m2.add(new Negation(c));
+ }
+ m.put(2,m2);
+ }
+ }
+
+ if(topRefinementsLength<3 && maxLength>2) {
+ // Konzepte der Länge 3: EXISTS r.TOP
+ Set<Description> m3 = new TreeSet<Description>(conceptComparator);
+ if(useExistsConstructor) {
+ // previous operator: uses all roles
+ // for(AtomicRole r : Config.Refinement.allowedRoles) {
+ // m3.add(new Exists(r, new Top()));
+ //}
+ // new operator: only uses most general roles
+ for(ObjectProperty r : rs.getMostGeneralRoles()) {
+ m3.add(new ObjectSomeRestriction(r, new Thing()));
+ }
+
+ }
+
+ // boolean datatypes, e.g. testPositive = true
+ if(useBooleanDatatypes) {
+ Set<DatatypeProperty> booleanDPs = rs.getBooleanDatatypeProperties();
+ for(DatatypeProperty dp : booleanDPs) {
+ m3.add(new BooleanValueRestriction(dp,true));
+ m3.add(new BooleanValueRestriction(dp,false));
+ }
+ }
+
+ m.put(3,m3);
+ }
+
+ if(maxLength>2) {
+ if(useAllConstructor) {
+ // Konzepte, die mit ALL r starten
+ // alle existierenden Konzepte durchgehen, die maximal 2 k�rzer als
+ // die maximale L�nge sind
+ // topRefinementsLength - 1, damit Konzepte der Länge mindestens
+ // topRefinementsLength + 1 erzeugt werden (ALL r)
+ for(int i=topRefinementsLength-1; i<=maxLength-2; i++) {
+ // i muss natürlich mindestens 1 sein
+ if(i>=1) {
+
+ // alle Konzepte durchgehen
+ for(Description c : m.get(i)) {
+ // Fall wird jetzt weiter oben schon abgehandelt
+ // if(!m.containsKey(i+2))
+ // m.put(i+2, new TreeSet<Concept>(conceptComparator));
+
+ // previous operator: uses all roles
+ // for(AtomicRole r : Config.Refinement.allowedRoles) {
+ // Mehrfacheinf�gen ist bei einer Menge kein Problem
+ // m.get(i+2).add(new All(r,c));
+ // }
+
+ for(ObjectProperty r : rs.getMostGeneralRoles()) {
+ m.get(i+2).add(new ObjectAllRestriction(r,c));
+ }
+ }
+ }
+ }
+ }
+ }
+
+ mComputationTimeNs += System.nanoTime() - mComputationTimeStartNs;
+ }
+
+
+ public static void summen(int zahl, int max, String bisher, int recDepth)
+ {
+ for(int j=0; j<recDepth; j++)
+ System.out.print(" ");
+ System.out.println("f("+zahl+","+max+",\""+bisher+"\")");
+
+ for (int i = Math.min(zahl, max); i >= 1; i--)
+ {
+
+ String jetzt = bisher + i;
+
+ if (zahl - i > 1)
+ {
+ jetzt += " + ";
+ // i wird hinzugefügt, d.h.
+ // - es muss nur noch zahl - i zerlegt werden
+ // - es darf keine größere Zahl als i mehr vorkommen
+ // (dadurch gehen keine Kombinationen verloren)
+ summen(zahl - i -1 , i, jetzt, recDepth+1);
+ }
+ // Fall zahl == i, d.h. es muss nicht weiter zerlegt werden
+ else if(zahl - i == 0){
+ for(int j=0; j<recDepth; j++)
+ System.out.print(" ");
+ System.out.println(jetzt);
+ }
+ // durch die -1 Abzug für jedes Zwischenzeichen gibt es auch Fälle, in denen
+ // keine Lösung entsteht (zahl-i==1)
+
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ private LinkedList<Integer> cloneList(LinkedList<Integer> list) {
+ return (LinkedList<Integer>) list.clone();
+ }
+
+ /**
+ *
+ * Dadurch das max das Maximum der vorkommenden Zahl regelt, kommen
+ * keine doppelten Kombinationen vor.
+ *
+ * TODO: Implementierung mit Speicherung in Datenstruktur statt
+ * direkter Ausgabe; IntegerCombo wird hier gar nicht benötigt, da
+ * alle Elemente bereits in richtiger Reihenfolge vorliegen und
+ * es keine doppelten Nennungen gibt
+ *
+ * @param zahl Zu zerlegende Zahl.
+ * @param max Maximal in Summenzerlegung vorkommende Zahl.
+ * @param bisher
+ */
+ private void zerlege(int zahl, int max, LinkedList<Integer> bisher, List<List<Integer>> combosTmp) {
+
+ for (int i = Math.min(zahl, max); i >= 1; i--)
+ {
+
+ LinkedList<Integer> newBisher = null;
+ // für i==0 wird aus Effizienzgründen die bisherige Liste genommen
+ if(i==0) {
+ newBisher = bisher;
+ newBisher.add(i);
+ // für zahl - i == 1 muss gar keine Liste erstellt werden, da dann keine
+ // Zerlegung mehr möglich ist
+ } else if(zahl - i != 1) {
+ newBisher = cloneList(bisher);
+ newBisher.add(i);
+ }
+
+
+ if (zahl - i > 1)
+ {
+ // i wird hinzugefügt, d.h.
+ // - es muss nur noch zahl - i - 1 zerlegt werden (-1 wegen OR-Symbol)
+ // - es darf keine größere Zahl als i mehr vorkommen
+ // (dadurch gehen keine Kombinationen verloren)
+ zerlege(zahl - i - 1, i, newBisher,combosTmp);
+ }
+ // Fall zahl == i, d.h. es muss nicht weiter zerlegt werden
+ else if(zahl - i == 0){
+ combosTmp.add(newBisher);
+ }
+
+
+ }
+
+ // numbers.add(bisher);
+ }
+
+ // auf Notebook: Länge 70 in 17 Sekunden, Länge 50 in 800ms, Länge 30 in 15ms
+ // http://88.198.173.90/tud/forum/messages?topic=304392
+ public List<List<Integer>> getCombos(int length) {
+ LinkedList<List<Integer>> combosTmp = new LinkedList<List<Integer>>();
+ zerlege(length, length, new LinkedList<Integer>(), combosTmp);
+ return combosTmp;
+ }
+
+ // neue Implementierung, die nicht mehr zur incompleteness führen soll,
+ // da die Konzepte in einer MultiDisjunction als Liste gespeichert werden
+ private Set<Union> incCrossProduct2(Set<Union> baseSet, Set<Description> newSet) {
+ Set<Union> retSet = new HashSet<Union>();
+
+ if(baseSet.isEmpty()) {
+ for(Description c : newSet) {
+ Union md = new Union();
+ md.addChild(c);
+ retSet.add(md);
+ }
+ return retSet;
+ }
+
+ for(Union md : baseSet) {
+ for(Description c : newSet) {
+ Union mdNew = new Union(md.getChildren());
+ mdNew.addChild(c);
+ retSet.add(mdNew);
+ }
+ }
+
+ return retSet;
+ }
+
+ // incremental cross product
+ // es müssen Listen statt Sets verwendet werden
+ @SuppressWarnings({"unused"})
+ private Set<Set<Description>> incCrossProduct(Set<Set<Description>> baseSet, Set<Description> newSet) {
+ Set<Set<Description>> retSet = new HashSet<Set<Description>>();
+
+ // falls erste Menge leer ist, dann wird Menge mit jeweils Singletons aus der
+ // zweiten Menge zurückgegeben => das müsste dem Fall entsprechen, dass das
+ // baseSet nur die leere Menge enthält
+ if(baseSet.isEmpty()) {
+ for(Description c : newSet) {
+ Set<Description> singleton = new HashSet<Description>();
+ singleton.add(c);
+ retSet.add(singleton);
+ }
+ // retSet.add(newSet);
+ return retSet;
+ }
+
+ for(Set<Description> set : baseSet) {
+ for(Description c : newSet) {
+ // neues Konzept zu alter Konzeptmenge hinzufügen, indem altes
+ // Konzept kopiert und ergänzt wird
+ // beachte: dadurch, dass die Konzepte nach ihrem Hash eingefügt werden,
+ // ist schon eine Ordnung vorgegeben und es entfallen viele Mengen
+ // z.B. ist {male,female} = {female,male}
+ // TODO: das ist allerdings auch gefährlich, denn es gilt auch
+ // {male,male,female} = {male,female} d.h. es entfallen auch gewünschte
+ // Lösungen! (Es könnte z.B. sein, dass die Lösung eine Disjunktion von
+ // 3 atomaren Konzepten ist, die nur über male erreichbar sind.) D.h. diese
+ // Implementierung führt zur incompleteness des Operators.
+ Set<Description> newConcept = new HashSet<Description>(set);
+ newConcept.add(c);
+ retSet.add(newConcept);
+ }
+ }
+ return retSet;
+ }
+
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
