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.Collection;
026import java.util.ConcurrentModificationException;
027import java.util.HashSet;
028import java.util.Map;
029import java.util.Map.Entry;
030import java.util.Set;
031import java.util.concurrent.ConcurrentHashMap;
032import java.util.concurrent.ExecutionException;
033import java.util.concurrent.Future;
034import java.util.concurrent.LinkedBlockingQueue;
035import java.util.concurrent.ThreadPoolExecutor;
036import java.util.concurrent.TimeUnit;
037import java.util.stream.Collectors;
038
039import com.google.common.collect.Sets;
040
041import conexp.fx.core.collections.Collections3;
042import conexp.fx.core.context.Concept;
043import conexp.fx.core.context.Context;
044import conexp.fx.core.context.Implication;
045import conexp.fx.core.math.SetClosureOperator;
046
047public final class NextClosures1C {
048
049  public static final class ResultC<G, M> {
050
051    public final Set<Concept<G, M>>  concepts     = Collections3.newConcurrentHashSet();
052    public final Map<Set<M>, Set<M>> implications = new ConcurrentHashMap<Set<M>, Set<M>>();
053    final Map<Set<M>, Integer>       candidates   = new ConcurrentHashMap<Set<M>, Integer>();
054    private final Set<Set<M>>        processed    = Collections3.newConcurrentHashSet();
055    int                              cardinality  = 0;
056    private final SetClosureOperator<M> clop;
057
058    public ResultC(SetClosureOperator<M> clop) {
059      this.clop = clop;
060      candidates.put(new HashSet<M>(), 0);
061    }
062
063    private final boolean isClosed(final Set<M> candidate) {
064//      if (!clop.isClosed(candidate))
065//        return false;
066      for (Entry<Set<M>, Set<M>> implication : implications.entrySet())
067        if (candidate.size() > implication.getKey().size() && candidate.containsAll(implication.getKey())
068            && !candidate.containsAll(implication.getValue()))
069          return false;
070      return true;
071    }
072
073    final Set<M> fastClosure(final Set<M> candidate, final int c) {
074      final Set<M> closure = new HashSet<M>(candidate);
075      boolean changed = false;
076      for (Entry<Set<M>, Set<M>> implication : implications.entrySet())
077        if (implication.getKey().size() >= c && closure.size() > implication.getKey().size()
078            && closure.containsAll(implication.getKey()) && !closure.containsAll(implication.getValue())) {
079          closure.addAll(implication.getValue());
080          changed = true;
081        }
082//      changed |= !clop.close(closure);
083      while (changed) {
084        changed = false;
085        for (Entry<Set<M>, Set<M>> implication : implications.entrySet())
086          if (closure.size() > implication.getKey().size() && closure.containsAll(implication.getKey())
087              && !closure.containsAll(implication.getValue())) {
088            closure.addAll(implication.getValue());
089            changed = true;
090          }
091//        changed |= !clop.close(closure);
092      }
093      return closure;
094    }
095
096    private final Set<M> closure(final Set<M> candidate) {
097      final Set<M> closure = new HashSet<M>(candidate);
098      boolean changed = true;
099      while (changed) {
100        changed = false;
101        for (Entry<Set<M>, Set<M>> implication : implications.entrySet())
102          if (closure.size() > implication.getKey().size() && closure.containsAll(implication.getKey())
103              && !closure.containsAll(implication.getValue())) {
104            closure.addAll(implication.getValue());
105            changed = true;
106          }
107//        changed |= !clop.close(closure);
108      }
109      return closure;
110    }
111
112    final boolean addToProcessed(final Set<M> s) {
113      try {
114        return processed.add(s);
115      } catch (ConcurrentModificationException e) {
116        return addToProcessed(s);
117      }
118    }
119
120  }
121
122  public static final <G, M> ResultC<G, M> compute(
123      final Context<G, M> cxt,
124      final SetClosureOperator<M> clop,
125      final boolean verbose,
126      final ThreadPoolExecutor tpe) {
127    if (verbose)
128      System.out
129          .println("NextClosures running on " + tpe.getCorePoolSize() + " - " + tpe.getMaximumPoolSize() + " cores...");
130    final ResultC<G, M> result = new ResultC<G, M>(clop);
131    final SetClosureOperator<M> sup = SetClosureOperator.supremum(SetClosureOperator.fromContext(cxt), clop);
132    final int maxCardinality = cxt.colHeads().size();
133    for (; result.cardinality <= maxCardinality; result.cardinality++) {
134      if (verbose) {
135        final int p = (int) ((100f * (float) result.cardinality) / ((float) maxCardinality));
136        System.out.println("current cardinality: " + result.cardinality + "/" + maxCardinality + " (" + p + "%)");
137      }
138//      final Collection<Set<M>> candidatesN =
139//          new HashSet<Set<M>>(Collections2.filter(result.candidates.keySet(), new Predicate<Set<M>>() {
140//
141//            @Override
142//            public final boolean apply(final Set<M> candidate) {
143//              return candidate.size() == result.cardinality;
144//            }
145//          }));
146//      if (verbose)
147//        System.out.println("     " + candidatesN.size() + " candidates will be processed...");
148      final Set<Future<?>> futures = Collections3.newConcurrentHashSet();
149//      for (final Set<M> candidate : candidatesN) {
150      result.candidates.keySet().parallelStream().filter(c -> c.size() == result.cardinality).forEach(candidate -> {
151        futures.add(tpe.submit(() -> {
152          final Set<M> closure = SetClosureOperator
153              .fromImplications(
154                  result.implications
155                      .entrySet()
156                      .stream()
157                      .map(e -> new Implication<G, M>(e.getKey(), e.getValue()))
158                      .collect(Collectors.toSet()),
159                  true,
160                  true)
161              .closure(candidate);
162//                result.fastClosure(candidate, result.candidates.get(candidate));
163          if (closure.size() == candidate.size()) {
164            final Set<M> candidateII = sup.closure(candidate);
165            if (result.addToProcessed(candidateII)) {
166              for (M m : Sets.difference(cxt.colHeads(), candidateII)) {
167                final Set<M> candidateM = new HashSet<M>(candidateII);
168                candidateM.add(m);
169                result.candidates.put(candidateM, 0);
170              }
171            }
172            result.concepts.add(new Concept<G, M>(cxt.colAnd(candidateII), Sets.newHashSet(candidateII)));
173            if (candidateII.size() != candidate.size()) {
174//                result.concepts.add(new Concept<G, M>(cxt.colAnd(candidate), candidate));
175//              } else {
176              candidateII.removeAll(candidate);
177              result.implications.put(candidate, candidateII);
178            }
179          } else {
180            result.candidates.put(closure, result.cardinality);
181          }
182          result.candidates.remove(candidate);
183        }));
184      });
185      for (Future<?> future : futures)
186        try {
187          future.get();
188        } catch (InterruptedException | ExecutionException e) {
189          e.printStackTrace();
190        }
191//      result.candidates.keySet().removeAll(candidatesN);
192    }
193    if (verbose) {
194      System.out.println(result.concepts.size() + " concepts found");
195      System.out.println(result.implications.size() + " implications found");
196    }
197    return result;
198  }
199
200  public static final <G, M> ResultC<G, M>
201      compute(final Context<G, M> cxt, final SetClosureOperator<M> clop, final boolean verbose, final int cores) {
202    if (cores > Runtime.getRuntime().availableProcessors())
203      throw new IllegalArgumentException(
204          "Requested pool size is too large. VM has only " + Runtime.getRuntime().availableProcessors()
205              + " available cpus, thus a thread pool with " + cores + " cores cannot be used here.");
206    final ThreadPoolExecutor tpe =
207        new ThreadPoolExecutor(cores, cores, 1000, TimeUnit.MILLISECONDS, new LinkedBlockingQueue<Runnable>());
208    tpe.prestartAllCoreThreads();
209    final ResultC<G, M> result = compute(cxt, clop, verbose, tpe);
210    tpe.purge();
211    tpe.shutdown();
212    return result;
213  }
214
215  public static final <G, M> ResultC<G, M>
216      compute(final Context<G, M> cxt, final SetClosureOperator<M> clop, final boolean verbose) {
217    final int maxc = Runtime.getRuntime().availableProcessors();
218    final int cores = maxc < 9 ? maxc : (maxc * 3) / 4;
219    return compute(cxt, clop, verbose, cores);
220  }
221
222  public static final <G, M> ResultC<G, M> computeWithBackgroundImplications(
223      final Context<G, M> cxt,
224      final Set<Implication<G, M>> backgroundImplications,
225      final boolean verbose) {
226    return compute(cxt, SetClosureOperator.fromImplications(backgroundImplications, false, true), verbose);
227  }
228
229  public static final <G, M> ResultC<G, M>
230      computeIceberg(final Context<G, M> cxt, final int minSupp, final boolean verbose) {
231    return compute(cxt, SetClosureOperator.byMinimalSupport(minSupp, cxt), verbose);
232  }
233
234  public static final <G, M> ResultC<G, M>
235      computeByMaxCard(final Context<G, M> cxt, final int maxCard, final boolean verbose) {
236    return compute(cxt, SetClosureOperator.byMaximalCardinality(maxCard, cxt.colHeads()), verbose);
237  }
238
239  public static final <G, M> ResultC<G, M>
240      computeBelow(final Context<G, M> cxt, final Collection<M> elements, final boolean verbose) {
241    return compute(cxt, SetClosureOperator.isSubsetOf(elements, cxt.colHeads()), verbose);
242  }
243
244  public static final <G, M> ResultC<G, M>
245      computeAbove(final Context<G, M> cxt, final Collection<M> elements, final boolean verbose) {
246    return compute(cxt, SetClosureOperator.containsAllFrom(elements, cxt.colHeads()), verbose);
247  }
248
249}