Source code

001/*
002 * @author Francesco.Kriegel@gmx.de
003 */
004package conexp.fx.core.math;
005
006/*
007 * #%L
008 * Concept Explorer FX
009 * %%
010 * Copyright (C) 2010 - 2019 Francesco Kriegel
011 * %%
012 * This program is free software: you can redistribute it and/or modify
013 * it under the terms of the GNU General Public License as
014 * published by the Free Software Foundation, either version 3 of the
015 * License, or (at your option) any later version.
016 * 
017 * This program is distributed in the hope that it will be useful,
018 * but WITHOUT ANY WARRANTY; without even the implied warranty of
019 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
020 * GNU General Public License for more details.
021 * 
022 * You should have received a copy of the GNU General Public
023 * License along with this program.  If not, see
024 * <http://www.gnu.org/licenses/gpl-3.0.html>.
025 * #L%
026 */
027
028import java.util.Arrays;
029import java.util.Collection;
030import java.util.Iterator;
031
032import org.ujmp.core.booleanmatrix.BooleanMatrix;
033import org.ujmp.core.booleanmatrix.BooleanMatrix2D;
034import org.ujmp.core.calculation.Calculation.Ret;
035
036public final class BooleanMatrices {
037
038  public static final BooleanMatrix clone(final BooleanMatrix m) {
039    return m.clone().toBooleanMatrix();
040  }
041
042  public static final BooleanMatrix empty(final long size) {
043    return empty(size, size);
044  }
045
046  public static final BooleanMatrix empty(final long rows, final long columns) {
047    return BooleanMatrix2D.Factory.zeros(rows, columns);
048  }
049
050  public static final BooleanMatrix full(final long size) {
051    return full(size, size);
052  }
053
054  public static final BooleanMatrix full(final long rows, final long columns) {
055    return complement(empty(rows, columns));
056  }
057
058  public static final BooleanMatrix identity(final long size) {
059    final BooleanMatrix m = empty(size);
060    for (int i = 0; i < size; i++)
061      m.setBoolean(true, i, i);
062    return m;
063  }
064
065  public static final BooleanMatrix negativeIdentity(final long size) {
066    return complement(identity(size));
067  }
068
069  public static final BooleanMatrix lowerDiagonal(final long size) {
070    return dual(upperDiagonal(size));
071  }
072
073  public static final BooleanMatrix upperDiagonal(final long size) {
074    final BooleanMatrix m = empty(size);
075    for (int i = 0; i < size; i++)
076      for (int j = i; j < size; j++)
077        m.setBoolean(true, i, j);
078    return m;
079  }
080
081  public static final BooleanMatrix strictLowerDiagonal(final long size) {
082    return complement(upperDiagonal(size));
083  }
084
085  public static final BooleanMatrix strictUpperDiagonal(final long size) {
086    return complement(lowerDiagonal(size));
087  }
088
089  public static final BooleanMatrix apposition(final BooleanMatrix... ms) {
090    if (ms.length == 0)
091      return null;
092    BooleanMatrix m = ms[0];
093    for (int i = 1; i < ms.length; i++)
094      m = apposition(m, ms[i]);
095    return m;
096  }
097
098  public static final BooleanMatrix apposition(final BooleanMatrix left, final BooleanMatrix right) {
099    if (left == null)
100      return (BooleanMatrix) right.clone();
101    if (right == null)
102      return (BooleanMatrix) left.clone();
103    return (BooleanMatrix) left.appendHorizontally(Ret.NEW, right);
104  }
105
106  public static final BooleanMatrix subposition(final BooleanMatrix... ms) {
107    if (ms.length == 0)
108      return null;
109    BooleanMatrix m = ms[0];
110    for (int i = 1; i < ms.length; i++)
111      m = subposition(m, ms[i]);
112    return m;
113  }
114
115  public static final BooleanMatrix subposition(final BooleanMatrix upper, final BooleanMatrix lower) {
116    if (upper == null)
117      return (BooleanMatrix) lower.clone();
118    if (lower == null)
119      return (BooleanMatrix) upper.clone();
120    return (BooleanMatrix) upper.appendVertically(Ret.NEW, lower);
121  }
122
123  public static final BooleanMatrix quadPosition(
124      final BooleanMatrix leftUpper,
125      final BooleanMatrix rightUpper,
126      final BooleanMatrix leftLower,
127      final BooleanMatrix rightLower) {
128    return subposition(apposition(leftUpper, rightUpper), apposition(leftLower, rightLower));
129  }
130
131  public static final BooleanMatrix complement(final BooleanMatrix m) {
132    return (BooleanMatrix) m.not(Ret.NEW);
133  }
134
135  public static final BooleanMatrix dual(final BooleanMatrix m) {
136    return (BooleanMatrix) m.transpose(Ret.NEW);
137  }
138
139  public static final BooleanMatrix booleann(final long size) {
140    if (size < 0)
141      return null;
142    else if (size == 0)
143      return identity(1);
144    final BooleanMatrix m = booleann(size - 1);
145    return subposition(apposition(m, m), apposition(empty((long) Math.pow(2, size - 1)), m));
146  }
147
148  public static final BooleanMatrix directSum(final BooleanMatrix leftUpper, final BooleanMatrix rightLower) {
149    return subposition(
150        apposition(leftUpper, full(leftUpper.getRowCount(), rightLower.getColumnCount())),
151        apposition(full(rightLower.getRowCount(), leftUpper.getColumnCount()), rightLower));
152  }
153
154  public static final BooleanMatrix horizontalSum(final BooleanMatrix leftUpper, final BooleanMatrix rightLower) {
155    return subposition(
156        apposition(leftUpper, empty(leftUpper.getRowCount(), rightLower.getColumnCount())),
157        apposition(empty(rightLower.getRowCount(), leftUpper.getColumnCount()), rightLower));
158  }
159
160  public static final BooleanMatrix verticalSum(final BooleanMatrix leftUpper, final BooleanMatrix rightLower) {
161    return subposition(
162        apposition(leftUpper, full(leftUpper.getRowCount(), rightLower.getColumnCount())),
163        apposition(empty(rightLower.getRowCount(), leftUpper.getColumnCount()), rightLower));
164  }
165
166  public static final BooleanMatrix substitutionSum(
167      final BooleanMatrix outer,
168      final BooleanMatrix inner,
169      final long row,
170      final long column,
171      final Collection<Integer> gI,
172      final Collection<Integer> mI) {
173    final BooleanMatrix lu, ru, ll, rl;
174    // ( G\{g}, M\{m}, I )
175    lu = outer;
176    System.out.println(lu);
177    // ( H, N, J )
178    rl = inner;
179    System.out.println(rl);
180    // ( G\{g}, N, (m'\{g}) x N )
181    ru = empty(lu.getRowCount(), rl.getColumnCount());
182    ru.selectRows(Ret.LINK, mI).not(Ret.ORIG);
183    System.out.println(ru);
184    // ( H, M\{m}, H x (g'\{m}) )
185    ll = empty(rl.getRowCount(), lu.getColumnCount());
186    ll.selectColumns(Ret.LINK, gI).not(Ret.ORIG);
187    System.out.println(ll);
188    return quadPosition(lu, ru, ll, rl).deleteRows(Ret.NEW, row).deleteColumns(Ret.NEW, column).toBooleanMatrix();
189  }
190
191  public static final BooleanMatrix directProduct(final BooleanMatrix m1, final BooleanMatrix m2) {
192    return (BooleanMatrix) scale(m1, m2.getRowCount(), m2.getColumnCount())
193        .or(Ret.NEW, duplicate(m2, m1.getRowCount(), m1.getColumnCount()));
194  }
195
196  public static final BooleanMatrix biProduct(final BooleanMatrix m1, final BooleanMatrix m2) {
197    return (BooleanMatrix) scale(m1, m2.getRowCount(), m2.getColumnCount())
198        .and(Ret.NEW, duplicate(m2, m1.getRowCount(), m1.getColumnCount()));
199  }
200
201  public static final BooleanMatrix semiProduct(final BooleanMatrix m1, final BooleanMatrix m2) {
202    return apposition(scaleV(m1, m2.getRowCount()), duplicateV(m2, m1.getRowCount()));
203  }
204
205  private static final BooleanMatrix duplicate(final BooleanMatrix m, final long rowFactor, final long columnFactor) {
206    return duplicateV(duplicateH(m, columnFactor), rowFactor);
207  }
208
209  private static final BooleanMatrix duplicateH(final BooleanMatrix m, final long columnFactor) {
210    BooleanMatrix h = null;
211    for (int i = 0; i < columnFactor; i++)
212      h = apposition(h, m);
213    return h;
214  }
215
216  private static final BooleanMatrix duplicateV(final BooleanMatrix m, final long rowFactor) {
217    BooleanMatrix v = null;
218    for (int i = 0; i < rowFactor; i++)
219      v = subposition(v, m);
220    return v;
221  }
222
223  private static final BooleanMatrix scale(final BooleanMatrix m, final long rowFactor, final long columnFactor) {
224    return scaleV(scaleH(m, columnFactor), rowFactor);
225  }
226
227  private static final BooleanMatrix scaleH(final BooleanMatrix m, final long columnFactor) {
228    BooleanMatrix h = null;
229    for (long j = 0; j < m.getColumnCount(); j++)
230      for (int f = 0; f < columnFactor; f++)
231        h = apposition(h, (BooleanMatrix) m.selectColumns(Ret.NEW, j));
232    return h;
233  }
234
235  private static final BooleanMatrix scaleV(final BooleanMatrix m, final long rowFactor) {
236    BooleanMatrix v = null;
237    for (long i = 0; i < m.getRowCount(); i++)
238      for (int f = 0; f < rowFactor; f++)
239        v = subposition(v, (BooleanMatrix) m.selectRows(Ret.NEW, i));
240    return v;
241  }
242
243  public static final BooleanMatrix andCol(final BooleanMatrix m, final Iterable<Integer> columns) {
244//    return StreamSupport.stream(columns.spliterator(), false).map(column -> m.selectColumns(Ret.NEW, column)).collect(
245//        () -> full(m.getRowCount(), 1),
246//        (x, y) -> x.and(Ret.ORIG, y),
247//        (x, y) -> x.and(Ret.ORIG, y));
248    final Iterator<Integer> it = columns.iterator();
249    if (it.hasNext()) {
250      final BooleanMatrix andCol = (BooleanMatrix) m.selectColumns(Ret.NEW, it.next());
251      while (it.hasNext())
252        andCol.and(Ret.ORIG, m.selectColumns(Ret.LINK, it.next()));
253      return andCol;
254    }
255    return full(m.getRowCount(), 1);
256  }
257
258  public static final BooleanMatrix andRow(final BooleanMatrix m, final Iterable<Integer> rows) {
259//    return StreamSupport.stream(rows.spliterator(), false).map(row -> m.selectRows(Ret.NEW, row)).collect(
260//        () -> full(1, m.getColumnCount()),
261//        (x, y) -> x.and(Ret.ORIG, y),
262//        (x, y) -> x.and(Ret.ORIG, y));
263    final Iterator<Integer> it = rows.iterator();
264    if (it.hasNext()) {
265      final BooleanMatrix andRow = (BooleanMatrix) m.selectRows(Ret.NEW, it.next());
266      while (it.hasNext())
267        andRow.and(Ret.ORIG, m.selectRows(Ret.LINK, it.next()));
268      return andRow;
269    }
270    return full(1, m.getColumnCount());
271  }
272
273  public static final BooleanMatrix andCol(final BooleanMatrix m, final Integer... columns) {
274    return andCol(m, Arrays.<Integer> asList(columns));
275  }
276
277  public static final BooleanMatrix andRow(final BooleanMatrix m, final Integer... rows) {
278    return andRow(m, Arrays.<Integer> asList(rows));
279  }
280
281  private static final boolean isSquare(final BooleanMatrix m) {
282    return m.getRowCount() == m.getColumnCount();
283  }
284
285  public static final BooleanMatrix product(final BooleanMatrix m1, final BooleanMatrix m2) {
286    return m1.mtimes(Ret.NEW, false, m2).toBooleanMatrix();
287  }
288
289  public static final BooleanMatrix power(final BooleanMatrix m, final int n) {
290    if (!isSquare(m))
291      throw new IllegalArgumentException();
292    if (n < 0)
293      throw new IllegalArgumentException();
294    if (n == 0)
295      return identity(m.getRowCount());
296    if (n == 1)
297      return clone(m);
298    if (n == 2)
299      return product(m, m);
300    return product(power(m, n - 1), m);
301  }
302
303  public static final BooleanMatrix reflexiveClosure(final BooleanMatrix m) {
304    if (!isSquare(m))
305      return null;
306    return m.or(Ret.NEW, identity(m.getRowCount())).toBooleanMatrix();
307  }
308
309  public static final BooleanMatrix reflexiveReduction(final BooleanMatrix m) {
310    if (!isSquare(m))
311      return null;
312    return m.and(Ret.NEW, negativeIdentity(m.getRowCount())).toBooleanMatrix();
313  }
314
315  public static final BooleanMatrix transitiveClosure(final BooleanMatrix m) {
316    if (!isSquare(m))
317      return null;
318    BooleanMatrix t = clone(m);
319    BooleanMatrix power = clone(m);
320    BooleanMatrix last = null;
321    do {
322      power = product(power, m);
323      last = clone(t);
324      t = t.or(Ret.NEW, power).toBooleanMatrix();
325    } while (!t.equals(last));
326    return t;
327  }
328
329  public static final BooleanMatrix transitiveReduction(final BooleanMatrix m) {
330    if (!isSquare(m))
331      return null;
332    return m.and(Ret.NEW, m.mtimes(Ret.NEW, false, transitiveClosure(m)).not(Ret.NEW)).toBooleanMatrix();
333  }
334}