// FILE. . . . . d:/hak/hlt/src/hlt/math/fuzzy/FuzzyMatrix.java
// EDIT BY . . . Hassan Ait-Kaci
// ON MACHINE. . Hp-Zbook
// STARTED ON. . Wed Mar 21 11:24:34 2018
/**
* @version Last modified on Tue Dec 17 16:25:23 2019 by hak
* @author Hassan Aït-Kaci
* @copyright © by the author
*/
package hlt.math.fuzzy;
/**
* package hlt.math.fuzzy
* package documentation listing
*/
import hlt.language.tools.Debug;
import hlt.math.matrix.Matrix;
import hlt.math.matrix.NumberAlgebra;
// for the set of fuzzy degrees used by this fuzzy matrix (see end of file):
import hlt.language.util.DoubleArrayList;
// for the set of matrix indices representing similarity classes:
import hlt.language.util.IntArrayList;
/**
* This is a generic class defining linear algebra operations on
* matrices of fuzzy degrees in [0.0,1.0] in terms of its two
* redefinable binary fuzzy operations on [0.0,1.0]: the
* additive law sum and the multiplicative law
* product. If not overridden, the default implementations for
* sum and product are respectively Math.max
* and Math.min.
*
*
*
*
* Contents (package hlt.math.matrix package documentation listing)
*
*
*
* @see ../matrix/Matrix
* @see ../matrix/NumberAlgebra
* @see FuzzyAlgebra
*/
public class FuzzyMatrix extends Matrix
{
/**
*
*/
/**
* Create a new FuzzyMatrix using the default
* NumberAlgebra).
*/
public FuzzyMatrix ()
{
super();
// FuzzyAlgebra.setDefaultAlgebra();
}
/**
* Create a new FuzzyMatrix using the specified
* NumberAlgebra as the fuzzy operations.
*/
private FuzzyMatrix (NumberAlgebra algebra)
{
super();
NumberAlgebra.setCurrentAlgebra(algebra);
}
/**
* Construct a FuzzyMatrix of order order with all
* entries 0.0's.
*/
public FuzzyMatrix (int order)
{
super(order);
// FuzzyAlgebra.setDefaultAlgebra();
}
/**
* Create a new fuzzy matrix with a new rows-by-cols
* data array of 0.0's.
*/
public FuzzyMatrix (int rows, int cols)
{
super(rows,cols);
// FuzzyAlgebra.setDefaultAlgebra();
}
/**
* Create a new FuzzyMatrix sharing the given array
* data of doubles in [0.0,0.1] (trusting
* them to be so).
*/
public FuzzyMatrix (double[][] data)
{
super(data,!COPY);
// FuzzyAlgebra.setDefaultAlgebra();
}
/**
* If the flag copy is false, create a fuzzy matrix
* sharing the given data array; otherwise, create a fuzzy matrix with
* a new copy of the data array, in which case it also verifies that
* all the double degrees in data are indeed in the
* continuous interval [0.0,0.1].
*
*/
public FuzzyMatrix (double[][] data, boolean copy)
{
rows = data.length;
cols = data[0].length;
if (copy)
{
this.data = new double[rows][cols];
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
this.data[i][j] = FuzzyTools.checkFuzzyValue(data[i][j]);
}
else
this.data = data;
// FuzzyAlgebra.setDefaultAlgebra();
}
/**
* Construct a new FuzzyMatrix from the data array of the given
* FuzzyMatrix.
*/
public FuzzyMatrix (FuzzyMatrix M)
{
this(M.data,true);
}
/**
*
*/
/**
* The degrees of this fuzzy matrix
* are its entries. This set is represented as a list of
* doubles kept in ascending order.
*/
final protected DoubleArrayList degrees = new DoubleArrayList();
/* ************************************************************************ */
/**
*
*/
/**
*
*/
/**
* Modify this FuzzyMatrix to have the given two-dimensional
* data array of doubles and corresponding numbers of rows
* and columns. If the array is null, throw a runtime
* exception.
*/
public FuzzyMatrix setData (double[][] data)
{
return (FuzzyMatrix)super.setData(data);
}
/**
* Set the (i,j) entry of this Matrix to
* the given value and returns the previous value that was
* there. Throws a NonFuzzyValueException exception if
* degree is not within [0.0,1.0]. Throws a
* RuntimeException for indices out of bounds. N.B.:
* Matrix indices are counted from 1.
*/
public double set (int i, int j, double degree)
{
return super.set(i,j,FuzzyTools.checkFuzzyValue(degree));
}
/* ******************************************************************** */
/**
*
*
* The following public methods define the reflexive, symmetric,
* transitive, and similarity closure operations on a fuzzy
* matrix. Each closure operation comes in two versions: one that
* returns a new fuzzy matrix without modifying the invoking matrix,
* and one that modifies the data array of the invoking matrix in
* place and returns the invoking matrix. The "in-place" version's
* name of any operation is the same as the non-in-place version
* starting with "i_". Each pair of methods rely on a static
* data version method (whose name starts with data),
* acting on a double[][] data array and returning a
* resulting double[][] data array.
* As for all methods in this class, these work correctly assuming
* specifically that all FuzzyMatrix objects are well-defined
* (i.e., they are all square and with entries in
* [0.0,1.0]).
*/
/**
* Return a new FuzzyMatrix that is the reflexive
* closure of this FuzzyMatrix.
*/
public FuzzyMatrix reflexive_closure ()
{
return (new FuzzyMatrix(data)).i_reflexive_closure();
}
/**
* Modify this fuzzy matrix to its reflexive closure and return it(self).
*/
public FuzzyMatrix i_reflexive_closure ()
{
dataReflexiveClosure(data);
return this;
}
/**
* Update the data array of this FuzzyMatrix
* to its reflexive closure and return it(self).
*/
static final public double[][] dataReflexiveClosure (double[][] data)
{
for (int row=0; row < data.length; row++)
data[row][row] = 1.0;
return data;
}
/* ************************************************************************ */
/**
* Return true iff this FuzzyMatrix is
* anti-symmetric (i.e., symmetric entries may not be both
* non-zero).
*/
public boolean isAntiSymmetric ()
{
return dataIsAntiSymmetric(data);
}
/**
* Return true iff the specified data array
* is anti-symmetric (i.e., symmetric entries may not be both
* non-zero).
*/
static public boolean dataIsAntiSymmetric (double[][] data)
{
for (int row = 0; row < data.length-1; row++)
for (int col = row+1; col < data[0].length; col++)
if (data[row][col] != 0.0 && data[col][row] != 0.0)
return false;
return true;
}
/* ************************************************************************ */
/**
* Return a new FuzzyMatrix that is the symmetric
* closure of this FuzzyMatrix.
*/
public FuzzyMatrix symmetric_closure ()
{
return (new FuzzyMatrix(data)).i_symmetric_closure();
}
/**
* Modify this FuzzyMatrix to its symmetric closure and return it(self).
*/
public FuzzyMatrix i_symmetric_closure ()
{
dataSymmetricClosure(data);
return this;
}
/**
* Update the given data array its symmetric closure and
* return it(self).
*/
static final public double[][] dataSymmetricClosure (double[][] data)
{
for (int row = 0; row < data.length; row++)
for (int col = row+1; col < data[0].length; col++)
{
data[row][col] = sum(data[row][col],
data[col][row]);
data[col][row] = data[row][col];
}
return data;
}
/* ************************************************************************ */
/**
* Return a new FuzzyMatrix that is the transitive
* closure of this FuzzyMatrix.
*/
public FuzzyMatrix transitive_closure ()
{
return (new FuzzyMatrix(data)).i_transitive_closure();
}
/**
* Modify this FuzzyMatrix to its transitive closure and
* return it(self).
*/
public FuzzyMatrix i_transitive_closure ()
{
return setData(dataTransitiveClosure(data));
}
/**
* Compute the transitive closure of the fuzzy relation specified in
* the data array and return the resulting array. The
* algorithm goes as follows:
*
* Given a fuzzy matrix M, its transitive closure is the
* matrix M\* = ∪i=0,...,n
* Mi which is computed as the limit of the
* sequence N0 = M, and for k
* > 0, Nk = Nk-1
* × Nk-1 until it becomes stationary;
* i.e., Nk = Nk-1 =
* M\*.
*
*
* This has complexity
* O(n3log(n)).
*/
static final public double[][] dataTransitiveClosure (double[][] data)
{
double[][] newData = data;
double[][] oldData;
int it = 0;
do
{
// it++;
oldData = copyData(newData);
newData = square(oldData);
// System.err.println(">>> PREVIOUS DATA:\n");
// showDataArray(oldData);
// System.err.println(">>> SQUARED DATA:\n");
// showDataArray(newData);
// if (!equalData(newData,oldData))
// {
// String answer = Debug.step("continue computing dataTransitiveClosure? (\"q\" to quit)");
// if (Debug.isQuitString(answer))
// break;
// }
}
while
(!equalData(newData,oldData));
// System.err.println(">>> Number of iterations = "+it);
return newData;
}
/**
* Return a new double[][] array equal to the matrix-square
* of the given square data array.
*/
static final private double[][] square (double[][] data)
{
// System.err.println(">>> CHECKING FUZZY OPS");
// System.err.println(">>> 0.4 \\/ 0.6 = "+sum(0.4,0.6));
// System.err.println(">>> 0.4 /\\ 0.6 = "+product(0.4,0.6));
// System.err.println(">>> SQUARING A "+data.length+" by "+data[0].length+" DATA ARRAY");
// showDataArray(data);
double[][] newData = new double[data.length][data[0].length];
for (int row = 0; row < data.length; row++)
for (int col = 0; col < data[0].length; col++)
for (int k = 0; k < data.length; k++)
{
newData[row][col] = sum(newData[row][col],
product(data[row][k],
data[k][col]));
// if (newData[row][col] > 1.0)
// System.err.println(">>> Bad fuzzy entry: "+newData[row][col]);
}
// System.err.println(">>> THE RESULTING SQUARED MATRIX IS:\n");
// showDataArray(newData);
// // Debug.step("continue");
return newData;
}
/* ************************************************************************ */
/**
* Return a new FuzzyMatrix that is the preorder
* closure of this FuzzyMatrix.
*/
public FuzzyMatrix preorder_closure ()
{
return (new FuzzyMatrix(data)).i_preorder_closure();
}
/**
* Modify this fuzzy matrix to its preorder (i.e.,
* symmetric-transitive) closure and return it(self).
*/
public FuzzyMatrix i_preorder_closure ()
{
data = dataPreorderClosure(data);
return this;
}
/**
* Return a double[][] array that is the preorder
* (i.e., reflexive-transitive) closure of the given
* data.
*/
static public double[][] dataPreorderClosure (double[][] data)
{
return dataTransitiveClosure(dataReflexiveClosure(data));
}
/* ************************************************************************ */
/**
* Return a FuzzyMatrix that is the similarity closure
* of this FuzzyMatrix.
*/
public FuzzyMatrix similarity_closure ()
{
return reflexive_closure().i_symmetric_closure().i_transitive_closure();
}
/**
* Modify this FuzzyMatrix to its similarity closure and return it(self).
*/
public FuzzyMatrix i_similarity_closure ()
{
return i_reflexive_closure().i_symmetric_closure().i_transitive_closure();
}
/* ******************************************************************** */
/**
* Given a degree cut ∈ degrees,
* partition(cut) of this FuzzyMatrix (when it is a
* similarity relation on the set {0,...,N}), is an array of
* N lists of ints, each list containing the indices
* in the set {0,...,N} constituting a similarity class at a
* fuzzy approximation degree α ∈
* [cut,1.0] (i.e., it is a partition of the set
* {0,...,N} for similarity degrees that are not less than
* cut). The list at index i contains the indices of
* the elements in the class [i]α ordered in
* ascending order, where[i]α ≝
* {j ∈ {0,...,N} | data[i][j] ≥
* α}. Each class is uniquely represented and shared by
* all indices in the class (it is the same list object) for all
* indices it contains. For example, if for N=6, the matrix
* is:
*
*
*
*
* 0 1 2 3 4 5
* --- --- --- --- --- ---
* 0 | 1.0 0.5 0.0 0.5 0.4 0.2
* 1 | 0.5 1.0 0.0 0.5 0.4 0.0
* 2 | 0.0 0.0 1.0 0.0 0.0 0.0
* 3 | 0.5 0.5 0.0 1.0 0.4 1.2
* 4 | 0.4 0.4 0.0 0.4 1.0 0.2
* 5 | 0.2 0.2 0.0 0.2 0.2 1.0
*
* then its array degrees is [0.0,0.2,0.4,0.5,1.0]
* and its partition(0.4) array is:
*
* 0: A
* 1: A
* 2: B
* 3: A
* 4: A
* 5: C
* with the three shared index lists:
*
* A ≝ [0,1,3,4]
* (= [0]0.4
* = [1]0.4
* = [3]0.4
* = [4]0.4);
* B ≝ [2]
* (= [2]0.4); and,
* C ≝ [5]
* (= [5]0.4).
*
*/
public IntArrayList[] partition (double cut)
{
int rank = rows;
// The array of rank classes
IntArrayList[] classes = new IntArrayList[rank];
// initialize all classes to singletons
for (int i=0; i < rank; i++)
{
classes[i] = new IntArrayList();
classes[i].add(i);
}
// sweep through the upper right triangle and merge the partitions
// of equivalent pairs over or at the cut
for (int i=0; i < rank-1; i++)
// {
for (int j=i+1; j < rank; j++)
if (data[i][j] >= cut)
// merge the classes at indices i and j and sets all related elements classes
merge(classes,i,j);
return classes;
}
/**
* This merges the classes classes[i] and classes[j]
* into a new class keeping it sorted in increasing order, and sets
* classes[k] to be this new merged class for all indices
* k in this class.
*/
private void merge (IntArrayList[] classes, int i, int j)
{
IntArrayList c1 = classes[i];
IntArrayList c2 = classes[j];
if (c1 != c2) // otherwise this would keep going
if (c2.size() < c1.size())
{
for (int k=0; k < c2.size(); k++)
insertIndex(c2.get(k),c1);
// update all appropriate classes to the merged class
for (int k=0; k < c1.size(); k++)
classes[c1.get(k)] = c1;
}
else
{
for (int k=0; k < c1.size(); k++)
insertIndex(c1.get(k),c2);
// update all appropriate classes to the merged class
for (int k=0; k < c2.size(); k++)
classes[c2.get(k)] = c2;
}
}
/**
* Adds index to orderedClass keeping it in
* increasing order.
*/
private void insertIndex (int index, IntArrayList orderedClass)
{
int size = orderedClass.size();
int i = 0;
while (i < size && orderedClass.get(i) < index)
i++;
if (index != orderedClass.get(i))
orderedClass.add(i,index);
}
/* ******************************************************************** */
/**
*
*/
/**
* Return the supremum of its arguments as elements of a
* FuzzyAlgebra (i.e., their sum, as defined
* by the current FuzzyAlgebra in effect).
*/
static public final double sup (double x, double y)
{
return sum(x,y);
}
/**
* Return the infimum of its arguments as elements of a
* FuzzyAlgebra (i.e., their product, as
* defined by the current FuzzyAlgebra in effect).
*/
static public final double inf (double x, double y)
{
return product(x,y);
}
/**
* Return a new FuzzyMatrix that is the transpose of this
* one.
*/
public FuzzyMatrix transpose ()
{
return new FuzzyMatrix().setData(dataTranspose(data));
}
public FuzzyMatrix i_transpose ()
{
if (!isSquare())
throw new RuntimeException
("Cannot transpose a non-square matrix in place");
int rank = rank();
for (int i = 0; i < rank; i++)
for (int j = i+1; j < rank; j++)
{
double tmp = data[i][j];
data[i][j] = data[j][i];
data[j][i] = tmp;
}
return this;
}
/**
* Return the set of degrees of this fuzzy matrix.
*/
public final DoubleArrayList degrees ()
{
if (degrees.isEmpty())
computeDegrees();
return degrees;
}
/**
* Recompute and returns the set of degrees of this fuzzy matrix.
*/
public final DoubleArrayList computeDegrees ()
{
degrees.setSize(0); // erase all entries if any
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
addDegree(data[i][j]);
return degrees;
}
/**
* Inserts a double degree into this matrix' set of degree
* keeping this set sorted in increasing order, and returns the set.
*/
protected final DoubleArrayList addDegree (double degree)
{
int i = 0;
while (i < degrees.size() && degree > degrees.get(i))
i++;
if (degree != degrees.get(i))
// will shift degrees at indices to the right and insert degree at i
degrees.add(i,degree);
return degrees;
}
/**
* Return a new FuzzyMatrix with a data array that is
* a copy of this one's.
*/
public FuzzyMatrix copy ()
{
return copy(data);
}
/**
* Return a new FuzzyMatrix having a different data array
* than that of the given one, but containg equal array degrees as the
* given one.
*/
public FuzzyMatrix copy (FuzzyMatrix M)
{
return copy(M.data);
}
/**
* Return a new FuzzyMatrix whose data array is a copy
* of the given data array.
*/
public FuzzyMatrix copy (double[][] data)
{
return new FuzzyMatrix(data,COPY);
}
/* ******************************************************************** */
/**
*
*/
/**
* Just a convenience to remind that making a copy is in effect (can
* then be used instead of true).
*/
static boolean COPY = true;
/**
* A public handle to the canonical FuzzyAlgebra currently in
* effect.
*/
static public final FuzzyAlgebra fuzzyAlgebra ()
{
return (FuzzyAlgebra)NumberAlgebra.currentAlgebra();
}
/* ******************************************************************** */
/**
* Create and return a random rows-by-cols
* FuzzyMatrix.
*/
public static FuzzyMatrix random (int rows, int cols)
{
return new FuzzyMatrix().setData(randomDataArray(rows,cols));
}
}