001package conexp.fx.core.layout;
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.Random;
028import java.util.Set;
029
030import org.ujmp.core.util.RandomSimple;
031
032import com.google.common.base.Predicate;
033
034import conexp.fx.core.collections.BitSetFX;
035import conexp.fx.core.collections.Collections3;
036import conexp.fx.core.collections.relation.MatrixRelation;
037
038public final class ChainDecomposer<E> {
039
040  private final MatrixRelation<E, E> neighborhood;
041  private final int                  num;
042  private final Random               rng = new RandomSimple();
043
044  public ChainDecomposer(final MatrixRelation<E, E> neighborhood) {
045    this.neighborhood = neighborhood;
046    this.num = neighborhood.rowHeads().size();
047  }
048
049  public final Set<Set<E>> randomChainDecomposition() {
050    final BitSetFX available = new BitSetFX();
051    available.set(0, num);
052    final Set<Set<E>> chains = new HashSet<Set<E>>();
053    while (!available.isEmpty())
054      chains.add(nextChain(available));
055    return chains;
056  }
057
058  private final Set<E> nextChain(final BitSetFX available) {
059    final Set<E> chain = new HashSet<E>();
060    for (int i = nextMinimalElement(available); i != -1; i = nextChainElement(i, available))
061      chain.add(neighborhood.rowHeads().get(i));
062    return chain;
063  }
064
065  private final int nextMinimalElement(final BitSetFX available) {
066    final int i = Collections3.random(available, new Predicate<Integer>() {
067
068      public final boolean apply(final Integer i) {
069        return neighborhood._col(i, available).isEmpty();
070      }
071    }, rng);
072    available.remove(i);
073    return i;
074  }
075
076  private final int nextChainElement(final int i, final BitSetFX available) {
077    final Collection<Integer> upper = neighborhood._row(i, available);
078    if (upper.isEmpty())
079      return -1;
080    else {
081      final int j = Collections3.random(upper, rng);
082      available.remove(j);
083      return j;
084    }
085  }
086}