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;
037
038import com.google.common.collect.Collections2;
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;
044
045public final class NextClosures1 {
046
047  public static final class Result<G, M> {
048
049    public final Set<Concept<G, M>>      concepts     = Collections3.newConcurrentHashSet();
050    public final Map<Set<M>, Set<M>>     implications = new ConcurrentHashMap<Set<M>, Set<M>>();
051    public final Map<Set<M>, Set<G>>     supports     = new ConcurrentHashMap<Set<M>, Set<G>>();
052    protected final Map<Set<M>, Integer> candidates   = new ConcurrentHashMap<Set<M>, Integer>();
053    private final Set<Set<M>>            processed    = Collections3.newConcurrentHashSet();
054    protected int                        cardinality  = 0;
055
056    public Result() {
057      candidates.put(new HashSet<M>(), 0);
058    }
059
060    private final boolean isClosed(final Set<M> candidate) {
061      for (Entry<Set<M>, Set<M>> implication : implications.entrySet())
062        if (candidate.size() > implication.getKey().size() && candidate.containsAll(implication.getKey())
063            && !candidate.containsAll(implication.getValue()))
064          return false;
065      return true;
066    }
067
068    final Set<M> fastClosure(final Set<M> candidate, final int c) {
069      final Set<M> closure = new HashSet<M>(candidate);
070      boolean changed = false;
071      for (Entry<Set<M>, Set<M>> implication : implications.entrySet())
072        if (implication.getKey().size() >= c && closure.size() > implication.getKey().size()
073            && closure.containsAll(implication.getKey()) && !closure.containsAll(implication.getValue())) {
074          closure.addAll(implication.getValue());
075          changed = true;
076        }
077      while (changed) {
078        changed = false;
079        for (Entry<Set<M>, Set<M>> implication : implications.entrySet())
080          if (closure.size() > implication.getKey().size() && closure.containsAll(implication.getKey())
081              && !closure.containsAll(implication.getValue())) {
082            closure.addAll(implication.getValue());
083            changed = true;
084          }
085      }
086      return closure;
087    }
088
089    private final Set<M> closure(final Set<M> candidate) {
090      final Set<M> closure = new HashSet<M>(candidate);
091      boolean changed = true;
092      while (changed) {
093        changed = false;
094        for (Entry<Set<M>, Set<M>> implication : implications.entrySet())
095          if (closure.size() > implication.getKey().size() && closure.containsAll(implication.getKey())
096              && !closure.containsAll(implication.getValue())) {
097            closure.addAll(implication.getValue());
098            changed = true;
099          }
100      }
101      return closure;
102    }
103
104    final boolean addToProcessed(final Set<M> s) {
105      try {
106        return processed.add(s);
107      } catch (ConcurrentModificationException e) {
108        return addToProcessed(s);
109      }
110    }
111
112  }
113
114  public static final <G, M> Result<G, M>
115      compute(final Context<G, M> cxt, final boolean verbose, final ThreadPoolExecutor tpe) {
116    if (verbose)
117      System.out
118          .println("NextClosures running on " + tpe.getCorePoolSize() + " - " + tpe.getMaximumPoolSize() + " cores...");
119    final Result<G, M> result = new Result<G, M>();
120    final int maxCardinality = cxt.colHeads().size();
121    for (; result.cardinality <= maxCardinality; result.cardinality++) {
122      if (verbose) {
123        final int p = (int) ((100f * (float) result.cardinality) / ((float) maxCardinality));
124        System.out.print("current cardinality: " + result.cardinality + "/" + maxCardinality + " (" + p + "%)");
125      }
126      final Collection<Set<M>> candidatesN = new HashSet<Set<M>>(
127          Collections2.filter(result.candidates.keySet(), candidate -> candidate.size() == result.cardinality));
128      if (verbose)
129        System.out.println("     " + candidatesN.size() + " candidates will be processed...");
130      final Set<Future<?>> futures = new HashSet<Future<?>>();
131      for (final Set<M> candidate : candidatesN) {
132        futures.add(tpe.submit(new Runnable() {
133
134          @Override
135          public final void run() {
136            final Set<M> closure = result.fastClosure(candidate, result.candidates.get(candidate));
137            if (closure.equals(candidate)) {
138              final Set<G> candidateI = cxt.colAnd(candidate);
139              final Set<M> candidateII = cxt.rowAnd(candidateI);
140              if (result.addToProcessed(candidateII)) {
141                for (M m : Sets.difference(cxt.colHeads(), candidateII)) {
142                  final Set<M> candidateM = new HashSet<M>(candidateII);
143                  candidateM.add(m);
144                  result.candidates.put(candidateM, 0);
145                }
146              }
147              if (candidateII.size() == candidate.size()) {
148                result.concepts.add(new Concept<G, M>(candidateI, candidate));
149              } else {
150                result.concepts.add(new Concept<G, M>(candidateI, candidateII));
151                candidateII.removeAll(candidate);
152                result.implications.put(candidate, candidateII);
153                result.supports.put(candidate, candidateI);
154              }
155            } else {
156              result.candidates.put(closure, result.cardinality);
157            }
158          }
159        }));
160      }
161      for (Future<?> future : futures)
162        try {
163          future.get();
164        } catch (InterruptedException | ExecutionException e) {
165          e.printStackTrace();
166        }
167      result.candidates.keySet().removeAll(candidatesN);
168    }
169    if (verbose) {
170      System.out.println(result.concepts.size() + " concepts found");
171      System.out.println(result.implications.size() + " implications found");
172    }
173    return result;
174  }
175
176  public static final <G, M> Result<G, M> compute(final Context<G, M> cxt, final boolean verbose, final int cores) {
177    if (cores > Runtime.getRuntime().availableProcessors())
178      throw new IllegalArgumentException(
179          "Requested pool size is too large. VM has only " + Runtime.getRuntime().availableProcessors()
180              + " available cpus, thus a thread pool with " + cores + " cores cannot be used here.");
181    final ThreadPoolExecutor tpe =
182        new ThreadPoolExecutor(cores, cores, 1000, TimeUnit.MILLISECONDS, new LinkedBlockingQueue<Runnable>());
183    tpe.prestartAllCoreThreads();
184    final Result<G, M> result = compute(cxt, verbose, tpe);
185    tpe.purge();
186    tpe.shutdown();
187    return result;
188  }
189
190  public static final <G, M> Result<G, M> compute(final Context<G, M> cxt, final boolean verbose) {
191    final int maxc = Runtime.getRuntime().availableProcessors();
192    final int cores = maxc < 9 ? maxc : (maxc * 3) / 4;
193    return compute(cxt, verbose, cores);
194  }
195
196}