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 - 2023 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    final BooleanMatrix copy = BooleanMatrices.empty(m.getRowCount(), m.getColumnCount());
040    copy.or(Ret.ORIG, m);
041    return copy;
042//    The below return statement sometimes yields read-only matrices.
043//    return m.clone().toBooleanMatrix();
044  }
045
046  public static final BooleanMatrix empty(final long size) {
047    return empty(size, size);
048  }
049
050  public static final BooleanMatrix empty(final long rows, final long columns) {
051    return BooleanMatrix2D.Factory.zeros(rows, columns);
052  }
053
054  public static final BooleanMatrix full(final long size) {
055    return full(size, size);
056  }
057
058  public static final BooleanMatrix full(final long rows, final long columns) {
059    return complement(empty(rows, columns));
060  }
061
062  public static final BooleanMatrix identity(final long size) {
063    final BooleanMatrix m = empty(size);
064    for (int i = 0; i < size; i++)
065      m.setBoolean(true, i, i);
066    return m;
067  }
068
069  public static final BooleanMatrix negativeIdentity(final long size) {
070    return complement(identity(size));
071  }
072
073  public static final BooleanMatrix lowerDiagonal(final long size) {
074    return dual(upperDiagonal(size));
075  }
076
077  public static final BooleanMatrix upperDiagonal(final long size) {
078    final BooleanMatrix m = empty(size);
079    for (int i = 0; i < size; i++)
080      for (int j = i; j < size; j++)
081        m.setBoolean(true, i, j);
082    return m;
083  }
084
085  public static final BooleanMatrix strictLowerDiagonal(final long size) {
086    return complement(upperDiagonal(size));
087  }
088
089  public static final BooleanMatrix strictUpperDiagonal(final long size) {
090    return complement(lowerDiagonal(size));
091  }
092
093  public static final BooleanMatrix apposition(final BooleanMatrix... ms) {
094    if (ms.length == 0)
095      return null;
096    BooleanMatrix m = ms[0];
097    for (int i = 1; i < ms.length; i++)
098      m = apposition(m, ms[i]);
099    return m;
100  }
101
102  public static final BooleanMatrix apposition(final BooleanMatrix left, final BooleanMatrix right) {
103    if (left == null)
104      return (BooleanMatrix) right.clone();
105    if (right == null)
106      return (BooleanMatrix) left.clone();
107    return (BooleanMatrix) left.appendHorizontally(Ret.NEW, right);
108  }
109
110  public static final BooleanMatrix subposition(final BooleanMatrix... ms) {
111    if (ms.length == 0)
112      return null;
113    BooleanMatrix m = ms[0];
114    for (int i = 1; i < ms.length; i++)
115      m = subposition(m, ms[i]);
116    return m;
117  }
118
119  public static final BooleanMatrix subposition(final BooleanMatrix upper, final BooleanMatrix lower) {
120    if (upper == null)
121      return (BooleanMatrix) lower.clone();
122    if (lower == null)
123      return (BooleanMatrix) upper.clone();
124    return (BooleanMatrix) upper.appendVertically(Ret.NEW, lower);
125  }
126
127  public static final BooleanMatrix quadPosition(
128      final BooleanMatrix leftUpper,
129      final BooleanMatrix rightUpper,
130      final BooleanMatrix leftLower,
131      final BooleanMatrix rightLower) {
132    return subposition(apposition(leftUpper, rightUpper), apposition(leftLower, rightLower));
133  }
134
135  public static final BooleanMatrix complement(final BooleanMatrix m) {
136    return (BooleanMatrix) m.not(Ret.NEW);
137  }
138
139  public static final BooleanMatrix dual(final BooleanMatrix m) {
140    return (BooleanMatrix) m.transpose(Ret.NEW);
141  }
142
143  public static final BooleanMatrix booleann(final long size) {
144    if (size < 0)
145      return null;
146    else if (size == 0)
147      return identity(1);
148    final BooleanMatrix m = booleann(size - 1);
149    return subposition(apposition(m, m), apposition(empty((long) Math.pow(2, size - 1)), m));
150  }
151
152  public static final BooleanMatrix directSum(final BooleanMatrix leftUpper, final BooleanMatrix rightLower) {
153    return subposition(
154        apposition(leftUpper, full(leftUpper.getRowCount(), rightLower.getColumnCount())),
155        apposition(full(rightLower.getRowCount(), leftUpper.getColumnCount()), rightLower));
156  }
157
158  public static final BooleanMatrix horizontalSum(final BooleanMatrix leftUpper, final BooleanMatrix rightLower) {
159    return subposition(
160        apposition(leftUpper, empty(leftUpper.getRowCount(), rightLower.getColumnCount())),
161        apposition(empty(rightLower.getRowCount(), leftUpper.getColumnCount()), rightLower));
162  }
163
164  public static final BooleanMatrix verticalSum(final BooleanMatrix leftUpper, final BooleanMatrix rightLower) {
165    return subposition(
166        apposition(leftUpper, full(leftUpper.getRowCount(), rightLower.getColumnCount())),
167        apposition(empty(rightLower.getRowCount(), leftUpper.getColumnCount()), rightLower));
168  }
169
170  public static final BooleanMatrix substitutionSum(
171      final BooleanMatrix outer,
172      final BooleanMatrix inner,
173      final long row,
174      final long column,
175      final Collection<Integer> gI,
176      final Collection<Integer> mI) {
177    final BooleanMatrix lu, ru, ll, rl;
178    // ( G\{g}, M\{m}, I )
179    lu = outer;
180    System.out.println(lu);
181    // ( H, N, J )
182    rl = inner;
183    System.out.println(rl);
184    // ( G\{g}, N, (m'\{g}) x N )
185    ru = empty(lu.getRowCount(), rl.getColumnCount());
186    ru.selectRows(Ret.LINK, mI).not(Ret.ORIG);
187    System.out.println(ru);
188    // ( H, M\{m}, H x (g'\{m}) )
189    ll = empty(rl.getRowCount(), lu.getColumnCount());
190    ll.selectColumns(Ret.LINK, gI).not(Ret.ORIG);
191    System.out.println(ll);
192    return quadPosition(lu, ru, ll, rl).deleteRows(Ret.NEW, row).deleteColumns(Ret.NEW, column).toBooleanMatrix();
193  }
194
195  public static final BooleanMatrix directProduct(final BooleanMatrix m1, final BooleanMatrix m2) {
196    return (BooleanMatrix) scale(m1, m2.getRowCount(), m2.getColumnCount())
197        .or(Ret.NEW, duplicate(m2, m1.getRowCount(), m1.getColumnCount()));
198  }
199
200  public static final BooleanMatrix biProduct(final BooleanMatrix m1, final BooleanMatrix m2) {
201    return (BooleanMatrix) scale(m1, m2.getRowCount(), m2.getColumnCount())
202        .and(Ret.NEW, duplicate(m2, m1.getRowCount(), m1.getColumnCount()));
203  }
204
205  public static final BooleanMatrix semiProduct(final BooleanMatrix m1, final BooleanMatrix m2) {
206    return apposition(scaleV(m1, m2.getRowCount()), duplicateV(m2, m1.getRowCount()));
207  }
208
209  private static final BooleanMatrix duplicate(final BooleanMatrix m, final long rowFactor, final long columnFactor) {
210    return duplicateV(duplicateH(m, columnFactor), rowFactor);
211  }
212
213  private static final BooleanMatrix duplicateH(final BooleanMatrix m, final long columnFactor) {
214    BooleanMatrix h = null;
215    for (int i = 0; i < columnFactor; i++)
216      h = apposition(h, m);
217    return h;
218  }
219
220  private static final BooleanMatrix duplicateV(final BooleanMatrix m, final long rowFactor) {
221    BooleanMatrix v = null;
222    for (int i = 0; i < rowFactor; i++)
223      v = subposition(v, m);
224    return v;
225  }
226
227  private static final BooleanMatrix scale(final BooleanMatrix m, final long rowFactor, final long columnFactor) {
228    return scaleV(scaleH(m, columnFactor), rowFactor);
229  }
230
231  private static final BooleanMatrix scaleH(final BooleanMatrix m, final long columnFactor) {
232    BooleanMatrix h = null;
233    for (long j = 0; j < m.getColumnCount(); j++)
234      for (int f = 0; f < columnFactor; f++)
235        h = apposition(h, (BooleanMatrix) m.selectColumns(Ret.NEW, j));
236    return h;
237  }
238
239  private static final BooleanMatrix scaleV(final BooleanMatrix m, final long rowFactor) {
240    BooleanMatrix v = null;
241    for (long i = 0; i < m.getRowCount(); i++)
242      for (int f = 0; f < rowFactor; f++)
243        v = subposition(v, (BooleanMatrix) m.selectRows(Ret.NEW, i));
244    return v;
245  }
246
247  public static final BooleanMatrix andCol(final BooleanMatrix m, final Iterable<Integer> columns) {
248//    return StreamSupport.stream(columns.spliterator(), false).map(column -> m.selectColumns(Ret.NEW, column)).collect(
249//        () -> full(m.getRowCount(), 1),
250//        (x, y) -> x.and(Ret.ORIG, y),
251//        (x, y) -> x.and(Ret.ORIG, y));
252    final Iterator<Integer> it = columns.iterator();
253    if (it.hasNext()) {
254      final BooleanMatrix andCol = (BooleanMatrix) m.selectColumns(Ret.NEW, it.next());
255      while (it.hasNext())
256        andCol.and(Ret.ORIG, m.selectColumns(Ret.LINK, it.next()));
257      return andCol;
258    }
259    return full(m.getRowCount(), 1);
260  }
261
262  public static final BooleanMatrix andRow(final BooleanMatrix m, final Iterable<Integer> rows) {
263//    return StreamSupport.stream(rows.spliterator(), false).map(row -> m.selectRows(Ret.NEW, row)).collect(
264//        () -> full(1, m.getColumnCount()),
265//        (x, y) -> x.and(Ret.ORIG, y),
266//        (x, y) -> x.and(Ret.ORIG, y));
267    final Iterator<Integer> it = rows.iterator();
268    if (it.hasNext()) {
269      final BooleanMatrix andRow = (BooleanMatrix) m.selectRows(Ret.NEW, it.next());
270      while (it.hasNext())
271        andRow.and(Ret.ORIG, m.selectRows(Ret.LINK, it.next()));
272      return andRow;
273    }
274    return full(1, m.getColumnCount());
275  }
276
277  public static final BooleanMatrix andCol(final BooleanMatrix m, final Integer... columns) {
278    return andCol(m, Arrays.<Integer> asList(columns));
279  }
280
281  public static final BooleanMatrix andRow(final BooleanMatrix m, final Integer... rows) {
282    return andRow(m, Arrays.<Integer> asList(rows));
283  }
284
285  private static final boolean isSquare(final BooleanMatrix m) {
286    return m.getRowCount() == m.getColumnCount();
287  }
288
289  public static final BooleanMatrix product(final BooleanMatrix m1, final BooleanMatrix m2) {
290    return m1.mtimes(Ret.NEW, false, m2).toBooleanMatrix();
291  }
292
293  public static final BooleanMatrix power(final BooleanMatrix m, final int n) {
294    if (!isSquare(m))
295      throw new IllegalArgumentException();
296    if (n < 0)
297      throw new IllegalArgumentException();
298    if (n == 0)
299      return identity(m.getRowCount());
300    if (n == 1)
301      return clone(m);
302    if (n == 2)
303      return product(m, m);
304    return product(power(m, n - 1), m);
305  }
306
307  public static final BooleanMatrix reflexiveClosure(final BooleanMatrix m) {
308    if (!isSquare(m))
309      return null;
310    return m.or(Ret.NEW, identity(m.getRowCount())).toBooleanMatrix();
311  }
312
313  public static final BooleanMatrix reflexiveReduction(final BooleanMatrix m) {
314    if (!isSquare(m))
315      return null;
316    return m.and(Ret.NEW, negativeIdentity(m.getRowCount())).toBooleanMatrix();
317  }
318
319  public static final BooleanMatrix transitiveClosure(final BooleanMatrix m) {
320    if (!isSquare(m))
321      return null;
322    BooleanMatrix t = clone(m);
323    BooleanMatrix power = clone(m);
324    BooleanMatrix last = null;
325    do {
326      power = product(power, m);
327      last = clone(t);
328      t = t.or(Ret.NEW, power).toBooleanMatrix();
329    } while (!t.equals(last));
330    return t;
331  }
332
333  public static final BooleanMatrix transitiveReduction(final BooleanMatrix m) {
334    if (!isSquare(m))
335      return null;
336    return m.and(Ret.NEW, m.mtimes(Ret.NEW, false, transitiveClosure(m)).not(Ret.NEW)).toBooleanMatrix();
337  }
338}