Source code

001package conexp.fx.core.algorithm.nextclosures;
002
003/*-
004 * #%L
005 * Concept Explorer FX
006 * %%
007 * Copyright (C) 2010 - 2023 Francesco Kriegel
008 * %%
009 * This program is free software: you can redistribute it and/or modify
010 * it under the terms of the GNU General Public License as
011 * published by the Free Software Foundation, either version 3 of the
012 * License, or (at your option) any later version.
013 * 
014 * This program is distributed in the hope that it will be useful,
015 * but WITHOUT ANY WARRANTY; without even the implied warranty of
016 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
017 * GNU General Public License for more details.
018 * 
019 * You should have received a copy of the GNU General Public
020 * License along with this program.  If not, see
021 * <http://www.gnu.org/licenses/gpl-3.0.html>.
022 * #L%
023 */
024
025import java.util.Collections;
026import java.util.HashSet;
027import java.util.Map;
028import java.util.Map.Entry;
029import java.util.Set;
030import java.util.concurrent.ConcurrentHashMap;
031import java.util.concurrent.ExecutionException;
032import java.util.concurrent.ExecutorService;
033import java.util.concurrent.Executors;
034import java.util.concurrent.Future;
035import java.util.function.Consumer;
036import java.util.function.Supplier;
037import java.util.stream.Collectors;
038import java.util.stream.Stream;
039
040import conexp.fx.core.collections.BitSetFX;
041import conexp.fx.core.collections.Collections3;
042import conexp.fx.core.collections.Pair;
043import conexp.fx.core.context.Concept;
044import conexp.fx.core.context.Context;
045import conexp.fx.core.context.Implication;
046import conexp.fx.core.context.MatrixContext;
047import conexp.fx.core.math.SetClosureOperator;
048import conexp.fx.core.math.Math3;
049import conexp.fx.core.util.Meter;
050import conexp.fx.gui.ConExpFX;
051import conexp.fx.gui.dataset.FCADataset;
052import conexp.fx.gui.task.TimeTask;
053import conexp.fx.gui.util.Platform2;
054
055public class NextClosures2Bit {
056
057  public static final <G, M> Pair<Set<Concept<G, M>>, Set<Implication<G, M>>> bitCompute(
058      final Context<G, M> cxt,
059      final ExecutorService executor,
060      final Consumer<Concept<G, M>> conceptConsumer,
061      final Consumer<Implication<G, M>> implicationConsumer,
062      final Consumer<String> updateStatus,
063      final Consumer<Double> updateProgress,
064      final Supplier<Boolean> isCancelled) {
065    final MatrixContext<G, M> mcxt = cxt instanceof MatrixContext ? (MatrixContext<G, M>) cxt : cxt.clone();
066    final int max = mcxt.colHeads().size();
067    final NextClosuresState<Integer, Integer, BitSetFX> state = NextClosuresState.withBitSets(max);
068//    final Function<BitSetFX, BitSetFX> cl = bitClosure(b.implications);
069    for (; state.cardinality <= max; state.cardinality++) {
070      if (isCancelled.get())
071        break;
072      final double q = ((double) state.cardinality) / ((double) max);
073      final int p = (int) (100d * q);
074      updateStatus.accept("current cardinality: " + state.cardinality + "/" + max + " (" + p + "%)");
075      updateProgress.accept(q);
076      final Set<Future<?>> fs = Collections3.newConcurrentHashSet();
077      final Set<BitSetFX> cc = state.getActualCandidates();
078      cc.forEach(c -> fs.add(executor.submit(() -> {
079        final BitSetFX d = SetClosureOperator
080            .implicativeClosure(state.implications, state.getFirstPremiseSize(c), true, true, true, BitSetFX::new, c);
081        if (c.geq(d)) {
082//        if (c.containsAll(d)) {
083          final BitSetFX c1 = mcxt._colAnd(c);
084          final BitSetFX c2 = mcxt._rowAnd(c1);
085          if (state.isNewIntent(c2)) {
086            state.concepts.add(new Concept<Integer, Integer>(c1, new BitSetFX(c2)));
087            state.addNewCandidates(c2);
088          }
089          if (!c.geq(c2)) {
090//          if (!c.containsAll(c2)) {
091            c2.removeAll(c);
092            state.implications.add(new Implication<Integer, Integer>(c, c2));
093          }
094        } else
095          state.addCandidate(d);
096//        state.candidates.remove(c);
097      })));
098      for (Future<?> f : fs)
099        try {
100          f.get();
101        } catch (InterruptedException | ExecutionException __) {}
102      state.candidates.keySet().removeAll(cc);
103    }
104    updateStatus.accept(state.concepts.size() + " concepts, and " + state.implications.size() + " implications found");
105    final NextClosuresState<G, M, Set<M>> r = NextClosuresState.withHashSets(cxt.colHeads());
106    state.concepts
107        .parallelStream()
108        .map(
109            c -> new Concept<G, M>(
110                mcxt.rowHeads().getAll(c.getExtent(), true),
111                mcxt.colHeads().getAll(c.getIntent(), true)))
112        .forEach(conceptConsumer.andThen(r.concepts::add));
113    state.implications
114        .parallelStream()
115        .map(
116            i -> new Implication<G, M>(
117                mcxt.colHeads().getAll(i.getPremise(), true),
118                mcxt.colHeads().getAll(i.getConclusion(), true)))
119        .forEach(implicationConsumer.andThen(r.implications::add));
120    return r.getResultAndDispose();
121  }
122
123  public static final <G, M> Pair<Set<Concept<G, M>>, Set<Implication<G, M>>> bitCompute(final Context<G, M> cxt) {
124    return bitCompute(cxt, Executors.newWorkStealingPool(), __ -> {}, __ -> {}, __ -> {}, __ -> {}, () -> false);
125  }
126
127  public static final <G, M> Pair<Set<Concept<G, M>>, Set<Implication<G, M>>> bitCleanedCompute(
128      final Context<G, M> cxt,
129      final ExecutorService executor,
130      final Consumer<Concept<G, M>> conceptConsumer,
131      final Consumer<Implication<G, M>> implicationConsumer,
132      final Consumer<String> updateStatus,
133      final Consumer<Double> updateProgress,
134      final Supplier<Boolean> isCancelled) {
135    final MatrixContext<G, M> mcxt = cxt.toMatrixContext();
136    System.out.println("starting context cleaning...");
137    final Meter<Long> nsw = Meter.newNanoStopWatch();
138    mcxt.clean();
139    System.out.println("context cleaning took " + Math3.formatNanos(nsw.measure()));
140    System.out.println("cloning cleaned context...");
141    final Meter<Long> nsw2 = Meter.newNanoStopWatch();
142    final MatrixContext<Set<G>, Set<M>> ccxt = mcxt.cleaned.clone();
143    System.out.println("context cloning took " + Math3.formatNanos(nsw2.measure()));
144
145    final Meter<Long> nsw3 = Meter.newNanoStopWatch();
146    final Pair<Set<Concept<Set<G>, Set<M>>>, Set<Implication<Set<G>, Set<M>>>> r =
147        bitCompute(ccxt, executor, __ -> {}, __ -> {}, updateStatus, updateProgress, isCancelled);
148    System.out.println("bitcleaned: " + nsw3.measureAndFormat());
149    final Meter<Long> nsw4 = Meter.newNanoStopWatch();
150    final NextClosuresState<G, M, Set<M>> x = NextClosuresState.withHashSets(cxt.colHeads());
151    r
152        .first()
153        .parallelStream()
154        .map(
155            c -> new Concept<G, M>(
156                c.extent().parallelStream().flatMap(Set::parallelStream).collect(Collectors.toSet()),
157                c.intent().parallelStream().flatMap(Set::parallelStream).collect(Collectors.toSet())))
158        .forEach(conceptConsumer.andThen(x.concepts::add));
159    final Map<Set<M>, M> f = new ConcurrentHashMap<>();
160    ccxt.colHeads().parallelStream().map(c -> new HashSet<M>(c)).forEach(c -> f.put(c, c.iterator().next()));
161    r
162        .second()
163        .parallelStream()
164        .map(
165            i -> new Implication<G, M>(
166                i.getPremise().parallelStream().map(f::get).collect(Collectors.toSet()),
167                i.getConclusion().parallelStream().map(f::get).collect(Collectors.toSet())))
168        .forEach(implicationConsumer.andThen(x.implications::add));
169    f
170        .keySet()
171        .parallelStream()
172        .flatMap(
173            c -> c.size() > 1 ? c.parallelStream().map(m -> new Implication<G, M>(Collections.singleton(m), c))
174                : Stream.empty())
175        .forEach(implicationConsumer.andThen(x.implications::add));
176    System.out.println("transform: " + nsw3.measureAndFormat());
177    return x.getResultAndDispose();
178  }
179
180  public static final <G, M> Pair<Set<Concept<G, M>>, Set<Implication<G, M>>> bitReducedCompute(
181      final Context<G, M> cxt,
182      final ExecutorService executor,
183      final Consumer<Concept<G, M>> conceptConsumer,
184      final Consumer<Implication<G, M>> implicationConsumer,
185      final Consumer<String> updateStatus,
186      final Consumer<Double> updateProgress,
187      final Supplier<Boolean> isCancelled) {
188    final MatrixContext<G, M> mcxt = cxt.toMatrixContext();
189//    final long s = System.nanoTime();
190//    System.out.print(".");
191    mcxt.reduce();
192//    System.out.print(".");
193    final MatrixContext<Set<G>, Set<M>> rcxt = mcxt.reduced.clone();
194    final MatrixContext<Set<G>, Set<M>> ccxt = mcxt.cleaned.clone();
195//    System.out.println("reducing took " + Math3.formatNanos(System.nanoTime() - s));
196    final Pair<Set<Concept<Set<G>, Set<M>>>, Set<Implication<Set<G>, Set<M>>>> r =
197        bitCompute(rcxt, executor, __ -> {}, __ -> {}, updateStatus, updateProgress, isCancelled);
198    final NextClosuresState<G, M, Set<M>> x = NextClosuresState.withHashSets(cxt.colHeads());
199    final Map<Set<M>, Set<Set<M>>> irr = new ConcurrentHashMap<>();
200    ccxt
201        .colHeads()
202        .parallelStream()
203        .filter(atts -> !rcxt.colHeads().contains(atts))
204        .forEach(atts -> irr.put(atts, new HashSet<Set<M>>(ccxt.attributeQuasiOrder().col(atts))));
205    final Map<Set<G>, Set<Set<G>>> jrr = new ConcurrentHashMap<>();
206    ccxt
207        .rowHeads()
208        .parallelStream()
209        .filter(objs -> !rcxt.rowHeads().contains(objs))
210        .forEach(objs -> jrr.put(objs, new HashSet<Set<G>>(ccxt.objectQuasiOrder().col(objs))));
211    final Map<Set<M>, M> f = new ConcurrentHashMap<>();
212    ccxt.colHeads().parallelStream().map(c -> new HashSet<M>(c)).forEach(c -> f.put(c, c.iterator().next()));
213    r
214        .first()
215        .parallelStream()
216        .map(
217            c -> new Concept<G, M>(
218                c.extent().parallelStream().flatMap(Set::parallelStream).collect(Collectors.toSet()),
219                c.intent().parallelStream().flatMap(Set::parallelStream).collect(Collectors.toSet())))
220        .forEach(conceptConsumer.andThen(x.concepts::add));
221    for (Concept<G, M> c : x.concepts) {
222      for (Entry<Set<M>, Set<Set<M>>> e : irr.entrySet())
223        if (c.intent().containsAll(e.getValue().parallelStream().map(f::get).collect(Collectors.toSet())))
224          c.intent().addAll(e.getKey());
225      for (Entry<Set<G>, Set<Set<G>>> e : jrr.entrySet())
226        if (c.extent().containsAll(e.getValue().parallelStream().map(f::get).collect(Collectors.toSet())))
227          c.extent().addAll(e.getKey());
228    }
229    r
230        .second()
231        .parallelStream()
232        .map(
233            i -> new Implication<G, M>(
234                i.getPremise().parallelStream().map(f::get).collect(Collectors.toSet()),
235                i.getConclusion().parallelStream().map(f::get).collect(Collectors.toSet())))
236        .forEach(implicationConsumer.andThen(x.implications::add));
237    f
238        .keySet()
239        .parallelStream()
240        .flatMap(
241            c -> c.size() > 1 ? c.parallelStream().map(m -> new Implication<G, M>(Collections.singleton(m), c))
242                : Stream.empty())
243        .forEach(implicationConsumer.andThen(x.implications::add));
244    irr
245        .keySet()
246        .parallelStream()
247        .flatMap(
248            ir -> Stream
249                .<Implication<G, M>> of(
250                    new Implication<G, M>(
251                        Collections.singleton(f.get(ir)),
252                        irr.get(ir).parallelStream().map(f::get).collect(Collectors.toSet())),
253                    new Implication<G, M>(
254                        irr.get(ir).parallelStream().map(f::get).collect(Collectors.toSet()),
255                        Collections.singleton(f.get(ir)))))
256        .forEach(implicationConsumer.andThen(x.implications::add));
257    return x.getResultAndDispose();
258  }
259
260  public static final <G, M> TimeTask<?> createTask(FCADataset<G, M> dataset) {
261    return new TimeTask<Void>(dataset, "NextClosures") {
262
263      @Override
264      protected Void call() throws Exception {
265        updateProgress(0d, 1d);
266        if (isCancelled())
267          return null;
268        bitCompute(
269            dataset.context.getSelection(),
270            ConExpFX.instance.executor.tpe,
271            concept -> Platform2.runOnFXThread(() -> dataset.concepts.add(concept)),
272            implication -> Platform2.runOnFXThread(() -> dataset.implications.add(implication)),
273            // dataset.concepts::add,
274            // dataset.implications::add,
275            status -> updateMessage(status),
276            progress -> updateProgress(progress, 1d),
277            () -> isCancelled());
278        updateProgress(1d, 1d);
279        return null;
280      }
281    };
282  }
283
284}