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.Collection;
026import java.util.HashSet;
027import java.util.Map;
028import java.util.Map.Entry;
029import java.util.Optional;
030import java.util.Set;
031import java.util.concurrent.ConcurrentHashMap;
032import java.util.concurrent.ExecutionException;
033import java.util.concurrent.ExecutorService;
034import java.util.concurrent.Executors;
035import java.util.concurrent.Future;
036import java.util.concurrent.atomic.AtomicInteger;
037import java.util.function.Consumer;
038import java.util.function.Function;
039import java.util.function.Predicate;
040import java.util.function.Supplier;
041import java.util.stream.Collectors;
042
043import com.google.common.collect.Collections2;
044import com.google.common.collect.Sets;
045
046import conexp.fx.core.collections.Collections3;
047import conexp.fx.core.collections.Pair;
048import conexp.fx.core.context.Concept;
049import conexp.fx.core.context.Context;
050import conexp.fx.core.context.Implication;
051import conexp.fx.core.math.SetClosureOperator;
052import conexp.fx.gui.ConExpFX;
053import conexp.fx.gui.dataset.FCADataset;
054import conexp.fx.gui.task.TimeTask;
055import conexp.fx.gui.util.Platform2;
056
057public final class NextClosures2 {
058
059  public static final <G, M> Pair<Set<Concept<G, M>>, Set<Implication<G, M>>> compute(
060      final Set<M> baseSet,
061      final SetClosureOperator<M> clop,
062      final Function<Set<M>, Set<G>> extension,
063      final Predicate<Set<M>> monotoneBreakPredicate,
064      final ExecutorService executor,
065      final Consumer<Concept<G, M>> conceptConsumer,
066      final Consumer<Implication<G, M>> implicationConsumer,
067      final Consumer<String> updateStatus,
068      final Consumer<Double> updateProgress,
069      final Supplier<Boolean> isCancelled,
070      final Set<Implication<G, M>> backgroundKnowledge) {
071    final int max = baseSet.size();
072    final NextClosuresState<G, M, Set<M>> state = NextClosuresState.withHashSets(baseSet);
073//    final Function<BitSetFX, BitSetFX> cl = bitClosure(b.implications);
074    for (; state.cardinality <= max; state.cardinality++) {
075      if (isCancelled.get())
076        break;
077      final double q = ((double) state.cardinality) / ((double) max);
078      final int p = (int) (100d * q);
079      updateStatus.accept("current cardinality: " + state.cardinality + "/" + max + " (" + p + "%)");
080      updateProgress.accept(q);
081      final Set<Future<?>> fs = Collections3.newConcurrentHashSet();
082      final Set<Set<M>> cc = state.getActualCandidates();
083      cc.forEach(c -> fs.add(executor.submit(() -> {
084        if (monotoneBreakPredicate.test(c))
085          return;
086//        final Set<M> d = SetClosureOperator
087//            .implicativeClosure(state.implications, state.getFirstPremiseSize(c), true, true, true, HashSet::new, c);
088        final SetClosureOperator<M> _clop = backgroundKnowledge.isEmpty()
089            ? SetClosureOperator
090                .fromImplications(state.implications, state.getFirstPremiseSize(c), true, true, true, HashSet::new)
091            : SetClosureOperator
092                .supremum(
093                    SetClosureOperator
094                        .fromImplications(
095                            state.implications,
096                            state.getFirstPremiseSize(c),
097                            true,
098                            true,
099                            true,
100                            HashSet::new),
101                    SetClosureOperator.fromImplications(backgroundKnowledge, false, true));
102        final Set<M> d = _clop.closure(c);
103        if (c.containsAll(d)) {
104//        if (c.containsAll(d)) {
105//          final BitSetFX c1 = mcxt._colAnd(c);
106//          final BitSetFX c2 = mcxt._rowAnd(c1);
107          final Set<M> c2 = clop.closure(c);
108          if (state.isNewIntent(c2)) {
109            state.concepts.add(new Concept<G, M>(extension.apply(c2), c2));
110            state.addNewCandidates(c2);
111          }
112          if (!c.containsAll(c2)) {
113//          if (!c.containsAll(c2)) {
114            c2.removeAll(c);
115            final Implication<G, M> impl = new Implication<G, M>(c, c2);
116            implicationConsumer.accept(impl);
117            state.implications.add(impl);
118          }
119        } else
120          state.addCandidate(d);
121//        state.candidates.remove(c);
122      })));
123      for (Future<?> f : fs)
124        try {
125          f.get();
126        } catch (InterruptedException | ExecutionException __) {}
127      state.candidates.keySet().removeAll(cc);
128    }
129    updateStatus.accept(state.concepts.size() + " concepts, and " + state.implications.size() + " implications found");
130//    final NextClosuresState<G, M, Set<M>> r = NextClosuresState.withHashSets(cxt.colHeads());
131//    state.concepts
132//        .parallelStream()
133//        .map(
134//            c -> new Concept<G, M>(
135//                mcxt.rowHeads().getAll(c.getExtent(), true),
136//                mcxt.colHeads().getAll(c.getIntent(), true)))
137//        .forEach(conceptConsumer.andThen(r.concepts::add));
138//    state.implications
139//        .parallelStream()
140//        .map(
141//            i -> new Implication<G, M>(
142//                mcxt.colHeads().getAll(i.getPremise(), true),
143//                mcxt.colHeads().getAll(i.getConclusion(), true)))
144//        .forEach(implicationConsumer.andThen(r.implications::add));
145//    return r.getResultAndDispose();
146    return state.getResultAndDispose();
147  }
148
149  public static final <G, M> Pair<Set<Concept<G, M>>, Set<Implication<G, M>>> compute(
150      final Set<M> baseSet,
151      final SetClosureOperator<M> clop,
152      final Function<Set<M>, Set<G>> extension,
153      final Set<Implication<G, M>> backgroundKnowledge) {
154    return compute(
155        baseSet,
156        clop,
157        extension,
158        __ -> false,
159        Executors.newWorkStealingPool(),
160        __ -> {},
161        __ -> {},
162        __ -> {},
163        __ -> {},
164        () -> false,
165        backgroundKnowledge);
166  }
167
168  public static <G, M> Set<Implication<G, M>> transformToJoiningImplications(
169      final Context<G, M> cxt,
170      final Set<M> premises,
171      final Set<M> conclusions,
172      final Set<Implication<G, M>> implications) {
173    final Set<Implication<G, M>> joiningImplications = new HashSet<>();
174    for (Implication<G, M> implication : implications) {
175      final Set<M> premise = new HashSet<>(implication.getPremise());
176      premise.retainAll(premises);
177      final Set<M> conclusion = cxt.rowAnd(cxt.colAnd(premise));
178      conclusion.retainAll(conclusions);
179      joiningImplications.add(new Implication<G, M>(premise, conclusion));
180    }
181    return joiningImplications;
182  }
183
184  public static final <T> Set<Set<T>> compute(
185      final Set<T> baseSet,
186      final SetClosureOperator<T> clop,
187      final boolean verbose,
188      final ExecutorService tpe) {
189    final Map<Set<T>, Set<T>> closures = new ConcurrentHashMap<>();
190    final Set<Set<T>> candidates = Collections3.newConcurrentHashSet();
191    candidates.add(new HashSet<T>());
192    for (final AtomicInteger cardinality = new AtomicInteger(0); cardinality.get() < baseSet.size(); cardinality
193        .incrementAndGet()) {
194      System.out.println("current cardinality: " + cardinality.get());
195//      final long total = candidates.parallelStream().filter(c -> c.size() == cardinality.get()).count();
196//      final AtomicInteger current = new AtomicInteger(0);
197      while (!Collections2.filter(candidates, c -> c.size() == cardinality.get()).isEmpty()) {
198        final Set<Future<?>> futures = Collections3.newConcurrentHashSet();
199        final long count = candidates.parallelStream().filter(c -> c.size() == cardinality.get()).count();
200        System.out.println("processing " + count + " candidates");
201        for (Set<T> candidate : candidates)
202          if (candidate.size() == cardinality.get()) {
203            // candidates.parallelStream().filter(c -> c.size() == cardinality.get()).forEach(candidate -> {
204            futures.add(tpe.submit(() -> {
205              final Optional<Entry<Set<T>, Set<T>>> optional = closures
206                  .entrySet()
207                  .parallelStream()
208                  .filter(e -> candidate.containsAll(e.getKey()) && e.getValue().containsAll(candidate))
209                  .findAny();
210              final Set<T> closure;
211              if (optional.isPresent())
212                closure = optional.get().getValue();
213              else {
214                closure = clop.closure(candidate);
215//              System.out.println(cardinality.get() + " : " + current.incrementAndGet() + "/" + total + " : " + closure);
216                closures.put(candidate, closure);
217                Sets.difference(baseSet, closure).parallelStream().forEach(individual -> {
218                  final Set<T> nextCandidate = Sets.newHashSet(closure);
219                  nextCandidate.add(individual);
220                  candidates.add(nextCandidate);
221                });
222              }
223            }));
224          }
225        // });
226        candidates.removeIf(c -> c.size() == cardinality.get());
227        futures.forEach(f -> {
228          try {
229            f.get();
230          } catch (Exception e) {}
231        });
232      }
233    }
234    return closures.values().parallelStream().collect(Collectors.toSet());
235  }
236
237  @SafeVarargs
238  public static final <G, M> Pair<Set<Concept<G, M>>, Set<Implication<G, M>>> compute(
239      final Context<G, M> cxt,
240      final ExecutorService executor,
241      final Consumer<Concept<G, M>> conceptConsumer,
242      final Consumer<Implication<G, M>> implicationConsumer,
243      final Consumer<String> updateStatus,
244      final Consumer<Double> updateProgress,
245      final Supplier<Boolean> isCancelled,
246      final Collection<Implication<G, M>>... backgroundKnowledge) {
247//    System.out.println("invalid background implications:");
248//    Collections3.union(backgroundKnowledge).stream().filter(i -> !cxt.models(i)).forEach(System.out::println);;
249//    System.out.println();
250    if (!cxt.models(Collections3.union(backgroundKnowledge)))
251      throw new RuntimeException("The background implications are not valid in the formal context.");
252    final NextClosuresState<G, M, Set<M>> result = NextClosuresState.withHashSets(cxt.colHeads());
253    final Function<Integer, SetClosureOperator<M>> clop;
254    if (backgroundKnowledge.length == 0)
255      clop = i -> SetClosureOperator.fromImplications(result.implications, i, true, true);
256    else
257      clop = i -> SetClosureOperator
258          .supremum(
259              SetClosureOperator.fromImplications(result.implications, i, true, true),
260              SetClosureOperator.fromImplications(Collections3.union(backgroundKnowledge), false, true));
261//    final ClosureOperator<M> clop = ClosureOperator.fromImplications(result.implications, true, true);
262    final int maxCardinality = cxt.colHeads().size();
263    for (; result.cardinality <= maxCardinality; result.cardinality++) {
264      try {
265        if (isCancelled.get())
266          break;
267      } catch (Exception __) {}
268      final double q = ((double) result.cardinality) / ((double) maxCardinality);
269      final int p = (int) (100d * q);
270      updateStatus.accept("current cardinality: " + result.cardinality + "/" + maxCardinality + " (" + p + "%)");
271      updateProgress.accept(q);
272      final Set<Future<?>> futures = Collections3.newConcurrentHashSet();
273      final Set<Set<M>> cc = result.getActualCandidates();
274      cc.forEach(candidate -> {
275        futures.add(executor.submit(() -> {
276          final Set<M> closure = clop.apply(result.candidates.get(candidate)).closure(candidate);
277//          if (closure.size() == candidate.size()) {
278          if (closure.equals(candidate)) {
279            final Set<G> candidateI = cxt.colAnd(candidate);
280            final Set<M> candidateII = cxt.rowAnd(candidateI);
281            if (result.isNewIntent(candidateII)) {
282              final Concept<G, M> concept = new Concept<G, M>(candidateI, new HashSet<M>(candidateII));
283              result.concepts.add(concept);
284              conceptConsumer.accept(concept);
285              result.addNewCandidates(candidateII);
286            }
287            if (candidateII.size() != candidate.size()) {
288              candidateII.removeAll(candidate);
289              final Implication<G, M> implication = new Implication<G, M>(candidate, candidateII, candidateI);
290              result.implications.add(implication);
291              implicationConsumer.accept(implication);
292            }
293          } else {
294            result.candidates.put(closure, result.cardinality);
295          }
296//          result.candidates.remove(candidate);
297        }));
298      });
299      for (Future<?> future : futures)
300        try {
301          future.get();
302        } catch (InterruptedException | ExecutionException e) {
303          e.printStackTrace();
304        }
305      result.candidates.keySet().removeAll(cc);
306    }
307    updateStatus
308        .accept(result.concepts.size() + " concepts, and " + result.implications.size() + " implications found");
309    return result.getResultAndDispose();
310  }
311
312  @SafeVarargs
313  public static final <G, M> Pair<Set<Concept<G, M>>, Set<Implication<G, M>>> compute(
314      final Context<G, M> cxt,
315      final ExecutorService executor,
316      final Collection<Implication<G, M>>... backgroundKnowledge) {
317    return compute(cxt, executor, __ -> {}, __ -> {}, __ -> {}, __ -> {}, () -> false, backgroundKnowledge);
318  }
319
320  @SafeVarargs
321  public static final <G, M> Pair<Set<Concept<G, M>>, Set<Implication<G, M>>>
322      compute(final Context<G, M> cxt, final int cores, final Collection<Implication<G, M>>... backgroundKnowledge) {
323    if (cores > Runtime.getRuntime().availableProcessors())
324      throw new IllegalArgumentException(
325          "Requested pool size is too large. VM has only " + Runtime.getRuntime().availableProcessors()
326              + " available cpus, thus a thread pool with " + cores + " cores cannot be used here.");
327//    final ThreadPoolExecutor tpe =
328//        new ThreadPoolExecutor(cores, cores, 1000, TimeUnit.MILLISECONDS, new LinkedBlockingQueue<Runnable>());
329//    tpe.prestartAllCoreThreads();
330    final ExecutorService tpe = Executors.newWorkStealingPool(cores);
331    final Pair<Set<Concept<G, M>>, Set<Implication<G, M>>> result = compute(cxt, tpe, backgroundKnowledge);
332//    tpe.purge();
333    tpe.shutdown();
334    return result;
335  }
336
337  @SafeVarargs
338  public static final <G, M> Pair<Set<Concept<G, M>>, Set<Implication<G, M>>>
339      compute(final Context<G, M> cxt, final Collection<Implication<G, M>>... backgroundKnowledge) {
340    return compute(cxt, Runtime.getRuntime().availableProcessors(), backgroundKnowledge);
341  }
342
343  public static final <G, M> TimeTask<?> createTask(FCADataset<G, M> dataset) {
344    return new TimeTask<Void>(dataset, "NextClosures") {
345
346      @Override
347      protected Void call() throws Exception {
348        updateProgress(0d, 1d);
349        if (isCancelled())
350          return null;
351        compute(
352            dataset.context.getSelection(),
353            ConExpFX.instance.executor.tpe,
354            concept -> Platform2.runOnFXThread(() -> dataset.concepts.add(concept)),
355            implication -> Platform2.runOnFXThread(() -> dataset.implications.add(implication)),
356            // dataset.concepts::add,
357            // dataset.implications::add,
358            status -> updateMessage(status),
359            progress -> updateProgress(progress, 1d),
360            () -> isCancelled());
361        updateProgress(1d, 1d);
362        return null;
363      }
364    };
365  }
366
367}