Source code

001package conexp.fx.core.layout;
002
003import java.util.HashMap;
004
005/*
006 * #%L
007 * Concept Explorer FX
008 * %%
009 * Copyright (C) 2010 - 2023 Francesco Kriegel
010 * %%
011 * This program is free software: you can redistribute it and/or modify
012 * it under the terms of the GNU General Public License as
013 * published by the Free Software Foundation, either version 3 of the
014 * License, or (at your option) any later version.
015 * 
016 * This program is distributed in the hope that it will be useful,
017 * but WITHOUT ANY WARRANTY; without even the implied warranty of
018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
019 * GNU General Public License for more details.
020 * 
021 * You should have received a copy of the GNU General Public
022 * License along with this program.  If not, see
023 * <http://www.gnu.org/licenses/gpl-3.0.html>.
024 * #L%
025 */
026
027import java.util.HashSet;
028import java.util.Map;
029import java.util.Random;
030import java.util.Set;
031import java.util.concurrent.ExecutionException;
032import java.util.concurrent.Future;
033
034import org.ujmp.core.util.RandomSimple;
035
036import com.google.common.collect.Collections2;
037import com.google.common.collect.Iterables;
038
039import conexp.fx.core.collections.BitSetFX;
040import conexp.fx.core.collections.Collections3;
041import conexp.fx.core.context.Concept;
042import conexp.fx.core.context.MatrixContext;
043import conexp.fx.core.layout.AdditiveConceptLayout.Type;
044import conexp.fx.gui.ConExpFX;
045import conexp.fx.gui.dataset.FCADataset;
046import conexp.fx.gui.task.TimeTask;
047import javafx.beans.property.DoubleProperty;
048import javafx.beans.property.SimpleDoubleProperty;
049import javafx.geometry.Point3D;
050
051public final class GeneticLayouter<G, M> {
052
053  public static final <G, M> TimeTask<Void> initialSeeds(final FCADataset<G, M> dataset) {
054    return new TimeTask<Void>(dataset, "Initial Seeds and Labels") {
055
056      protected final Void call() {
057        updateProgress(0d, 1d);
058        if (isCancelled())
059          return null;
060        final Random rng = new RandomSimple();
061        updateMessage("Computing Infimum Irreducibles...");
062        final Set<G> supremumIrreducibles = dataset.layout.lattice.context.selection.supremumIrreducibles();
063        final Set<M> infimumIrreducibles = dataset.layout.lattice.context.selection.infimumIrreducibles();
064        updateProgress(0.2d, 1d);
065        updateProgress(0.3d, 1d);
066        updateMessage("Generating Layered Random Seeds...");
067        final Map<G, Point3D> randomSeedsG = new HashMap<G, Point3D>();
068        final Map<M, Point3D> randomSeedsM = new HashMap<M, Point3D>();
069        for (G g : supremumIrreducibles)
070          randomSeedsG.put(g, new Point3D(2d * rng.nextDouble() - 1d, 1, 0));
071        for (M m : infimumIrreducibles)
072          randomSeedsM.put(m, new Point3D(2d * rng.nextDouble() - 1d, 1, 0));
073        updateProgress(0.4d, 1d);
074        dataset.layout.updateSeeds(randomSeedsG, randomSeedsM);
075        updateProgress(0.5d, 1d);
076        updateMessage("Computing Attribute Labels...");
077        for (Concept<G, M> c : dataset.layout.lattice.rowHeads()) {
078          final Set<M> attributeLabels =
079              new HashSet<M>(dataset.layout.lattice.context.selection.attributeLabels(c.extent(), c.intent()));
080          synchronized (dataset.layout.lattice.attributeConcepts) {
081            for (M m : attributeLabels)
082              dataset.layout.lattice.attributeConcepts.put(m, c);
083          }
084        }
085        updateProgress(0.75d, 1d);
086        updateMessage("Computing Object Labels...");
087        for (Concept<G, M> c : dataset.layout.lattice.rowHeads()) {
088          final Set<G> objectLabels =
089              new HashSet<G>(dataset.layout.lattice.context.selection.objectLabels(c.extent(), c.intent()));
090          synchronized (dataset.layout.lattice.objectConcepts) {
091            for (G g : objectLabels)
092              dataset.layout.lattice.objectConcepts.put(g, c);
093          }
094        }
095        updateProgress(1d, 1d);
096        return null;
097      }
098    };
099  }
100
101  public static final <G, M> TimeTask<Void> seeds(
102      final FCADataset<G, M> dataset,
103      final boolean includingLayout,
104      final int generationCount,
105      final int populationSize) {
106    return new TimeTask<Void>(dataset, "Genetic Layouter") {
107
108      private final DoubleProperty                   evolutionaryProgressProperty = new SimpleDoubleProperty(0d);
109      private final Set<AdditiveConceptLayout<G, M>> layouts                      =
110          new HashSet<AdditiveConceptLayout<G, M>>(populationSize);
111      private double                                 currentQuality               = -1d;
112      private AdditiveConceptLayout<G, M>            currentBest;
113      private ChainDecomposer<Set<Integer>>          chainDecomposerG;
114      private ChainDecomposer<Set<Integer>>          chainDecomposerM;
115      private Random                                 rng                          = new RandomSimple();
116
117      @Override
118      protected final void updateProgress(double workDone, double max) {
119        super.updateProgress(workDone, max);
120        evolutionaryProgressProperty.set(workDone / max);
121      };
122
123      @Override
124      protected final Void call() {
125        updateProgress(0d, 1d);
126        if (isCancelled())
127          return null;
128        updateProgress(0.1d, 1d);
129        updateMessage("Decomposing Concept Lattice...");
130        final MatrixContext<Set<Integer>, Set<Integer>> cxt = dataset.layout.lattice.context.selection._reduced.clone();
131        chainDecomposerG = new ChainDecomposer<Set<Integer>>(cxt.objectQuasiOrder().neighborhood());
132        chainDecomposerM = new ChainDecomposer<Set<Integer>>(cxt.attributeQuasiOrder().neighborhood());
133        if (includingLayout) {
134          layouts.add(dataset.layout.clone());
135          currentBest = dataset.layout;
136        }
137        updateProgress(0.2d, 1d);
138        updateMessage("Setting up Evolution Engine...");
139        initPopulation();
140        updateProgress(0.3d, 1d);
141        updateMessage("Evolving Layout...");
142        evolvePopulation();
143        updateProgress(1d, 1d);
144        return null;
145      }
146
147      private final void initPopulation() {
148        final Set<Future<?>> futures = new HashSet<Future<?>>();
149        for (int i = includingLayout ? 1 : 0; i < populationSize; i++)
150          futures.add(ConExpFX.instance.executor.tpe.submit(generate()));
151        for (Future<?> f : futures)
152          try {
153            f.get();
154          } catch (InterruptedException | ExecutionException e) {
155            e.printStackTrace();
156          }
157      }
158
159      private final Runnable generate() {
160        return new Runnable() {
161
162          @Override
163          public void run() {
164            if (dataset.conceptGraph.polar()) {} else {
165              final AdditiveConceptLayout<G, M> candidate =
166                  new AdditiveConceptLayout<G, M>(dataset.layout.lattice, null, null, Type.HYBRID);
167              final Set<Set<Set<Integer>>> chainsG = chainDecomposerG.randomChainDecomposition();
168              final Set<Set<Set<Integer>>> chainsM = chainDecomposerM.randomChainDecomposition();
169              final int v = chainsG.size();
170              if (v == 1) {
171                final Point3D seed = new Point3D(0d, 1d, 0d);
172                for (G g : Collections2
173                    .transform(Iterables.getOnlyElement(chainsG), candidate.lattice.context.selection._firstObject))
174                  candidate.seedsG.put(g, seed);
175              } else {
176                final int vv = v * v;
177                final BitSetFX usedX = new BitSetFX();
178                for (Set<Set<Integer>> chain : chainsG) {
179                  int _x;
180                  for (_x = rng.nextInt(vv + 1); usedX.contains(_x) || usedX.contains(_x + 1)
181                      || (_x != 0 && usedX.contains(_x - 1)); _x = rng.nextInt(vv + 1));
182                  usedX.add(_x);
183                  final int __x = _x - vv / 2;
184                  final Point3D seed = new Point3D(
185                      (double) __x,
186                      (double) (rng.nextInt(Math.abs(__x + 1) + 1) + 1),
187                      dataset.conceptGraph.threeDimensions() ? (double) (rng.nextInt(Math.abs(__x + 1) + 1) - __x / 2)
188                          : 0d);
189                  for (G g : Collections2.transform(chain, candidate.lattice.context.selection._firstObject))
190                    candidate.seedsG.put(g, seed);
191                }
192              }
193              final int w = chainsM.size();
194              if (w == 1) {
195                final Point3D seed = new Point3D(0d, 1d, 0d);
196                for (M m : Collections2
197                    .transform(Iterables.getOnlyElement(chainsM), candidate.lattice.context.selection._firstAttribute))
198                  candidate.seedsM.put(m, seed);
199              } else {
200                final int ww = w * w;
201                final BitSetFX usedX = new BitSetFX();
202                for (Set<Set<Integer>> chain : chainsM) {
203                  int _x;
204                  for (_x = rng.nextInt(ww + 1); usedX.contains(_x) || usedX.contains(_x + 1)
205                      || (_x != 0 && usedX.contains(_x - 1)); _x = rng.nextInt(ww + 1));
206                  usedX.add(_x);
207                  final int __x = _x - ww / 2;
208                  final Point3D seed = new Point3D(
209                      (double) __x,
210                      (double) (rng.nextInt(Math.abs(__x + 1) + 1) + 1),
211                      dataset.conceptGraph.threeDimensions() ? (double) (rng.nextInt(Math.abs(__x + 1) + 1) - __x / 2)
212                          : 0d);
213                  for (M m : Collections2.transform(chain, candidate.lattice.context.selection._firstAttribute))
214                    candidate.seedsM.put(m, seed);
215                }
216              }
217              synchronized (layouts) {
218                layouts.add(candidate);
219              }
220              final double result = dataset.conflictDistance.apply(candidate).second();
221              if (result > currentQuality || currentBest == null) {
222                currentQuality = result;
223                currentBest = candidate;
224              }
225            }
226          }
227        };
228      }
229
230      private final AdditiveConceptLayout<G, M>
231          crossover(final AdditiveConceptLayout<G, M> l1, final AdditiveConceptLayout<G, M> l2) {
232        final AdditiveConceptLayout<G, M> l = l1.clone();
233        return null;
234      }
235
236      private final void evolvePopulation() {
237        if (dataset.conceptGraph.polar()) {} else {
238          for (int i = 0; i < generationCount; i++) {
239//            if (currentBest != dataset.layout)
240            dataset.layout.updateSeeds(currentBest.seedsG, currentBest.seedsM);
241            updateProgress(0.3d + 0.7d * ((double) i) / (double) generationCount, 1d);
242            updateMessage("Evolving Seeds: " + i + " of " + generationCount + " Generations...");
243            evolveGeneration();
244          }
245//          try {
246//            if (currentBest != dataset.layout)
247          dataset.layout.updateSeeds(currentBest.seedsG, currentBest.seedsM);
248//          } catch (Exception e) {
249//            System.err.println(currentBest);
250//            System.err.println(dataset.layout);
251//            e.printStackTrace();
252//          }
253        }
254      }
255
256      private final void evolveGeneration() {
257        if (dataset.conceptGraph.polar()) {} else {
258          currentQuality = -1d;
259          for (AdditiveConceptLayout<G, M> candidate : layouts) {
260            LayoutEvolution<G, M>.Value v = new LayoutEvolution<G, M>(
261                candidate,
262                dataset.conflictDistance.apply(candidate).first(),
263                ConceptMovement.INTENT_CHAIN_SEEDS,
264                4d,
265                4d,
266                2,
267                2,
268                1,
269                dataset.conflictDistance,
270                ConExpFX.instance.executor.tpe).calculate();
271            if (!candidate.updateSeeds(v.seedsG, v.seedsM)) {
272//              if (rng.nextBoolean()) {
273//                final Concept<G, M> c = candidate.seedsM
274//                    .keySet()
275//                    .parallelStream()
276//                    .map(candidate.lattice.attributeConcepts::get)
277//                    .filter(cn -> cn != null)
278//                    .findAny()
279//                    .get();
280////                    candidate.lattice.attributeConcepts.get(Collections3.random(candidate.seeds.keySet(), rng));
281//                v = new LayoutEvolution<G, M>(
282//                    candidate,
283//                    c,
284//                    // TODO
285//                    //                    ConceptMovement.LABEL_CHAIN_SEEDS,
286//                    ConceptMovement.INTENT_CHAIN_SEEDS,
287//                    4d,
288//                    4d,
289//                    2,
290//                    2,
291//                    1,
292//                    dataset.conflictDistance,
293//                    ConExpFX.instance.executor.tpe).calculate();
294//              } else
295              v = new LayoutEvolution<G, M>(
296                  candidate,
297                  Collections3.random(candidate.lattice.rowHeads(), rng),
298                  ConceptMovement.INTENT_CHAIN_SEEDS,
299                  4d,
300                  4d,
301                  2,
302                  2,
303                  1,
304                  dataset.conflictDistance,
305                  ConExpFX.instance.executor.tpe).calculate();
306              candidate.updateSeeds(v.seedsG, v.seedsM);
307            }
308            if (v.result > currentQuality) {
309              currentQuality = v.result;
310              currentBest = candidate;
311            }
312          }
313        }
314      }
315    };
316  }
317}