pnmatrix.java

Petri网分析工具PIPE is open-source

//######################################################################################
/**
 * This support class provides many general matrix manipulation functions, as well as
 * a number of specialised matrix operations pertaining to Petri net analysis.
 * @author Manos Papantoniou & Michael Camacho
 * @version February 2004

    Based on the Jama Matrix class, the PNMatrix class offers a small subset
    of the operations, and is used for matrices of integers only, as required
    by the petri net analyser project.

<P>
   This Class provides the fundamental operations of numerical
   linear algebra.  Various constructors create Matrices from two dimensional
   arrays of integer numbers.  Various "gets" and
   "sets" provide access to submatrices and matrix elements.  Several methods
   implement basic matrix arithmetic, including matrix addition and
   multiplication, and element-by-element array operations.
   Methods for reading and printing matrices are also included.
<P>
 */
//######################################################################################
package pipe.dataLayer;
//######################################################################################
import java.io.ByteArrayOutputStream;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.text.NumberFormat;
import java.util.Locale;
//######################################################################################
public class PNMatrix {

  /**
   * Array for internal storage of elements.
   * @serial internal array storage.
   */
  private int[][] A;

  /**
   * Row and column dimensions.
   * @serial row dimension.
   * @serial column dimension.
   */
  private int m, n;
//######################################################################################
  /**
   * Construct an m-by-n matrix of zeros.
   * @param m    Number of rows.
   * @param n    Number of colums.
   */
  public PNMatrix (int m, int n) {
    this.m = m;
    this.n = n;
    A = new int[m][n];
  }
//######################################################################################
  /**
   * Construct an m-by-n constant matrix.
   * @param m Number of rows.
   * @param n Number of colums.
   * @param s Fill the matrix with this scalar value.
   */
  public PNMatrix (int m, int n, int s) {
    this.m = m;
    this.n = n;
    A = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        A[i][j] = s;
      }
    }
  }
//######################################################################################
  /**
   * Construct a matrix from a 2-D array.
   * @param A Two-dimensional array of integers.
   * @exception IllegalArgumentException All rows must have the same length
   * @see #constructWithCopy
   */
  public PNMatrix (int[][] A) {
    if(A != null) {
      m = A.length;
      if(A.length >= 1) {
        n = A[0].length;
        for (int i = 0; i < m; i++) {
          if (A[i].length != n) {
            throw new IllegalArgumentException("All rows must have the same length.");
          }
        }
        this.A = A;
      }
    }
  }
//######################################################################################
  /**
   * Construct a matrix quickly without checking arguments.
   * @param A Two-dimensional array of integers.
   * @param m Number of rows.
   * @param n Number of colums.
   */
  public PNMatrix (int[][] A, int m, int n) {
    this.A = A;
    this.m = m;
    this.n = n;
  }
//######################################################################################
  /**
   * Construct a matrix from a one-dimensional packed array
   * @param vals One-dimensional array of integers, packed by columns (ala Fortran).
   * @param m Number of rows.
   * @exception IllegalArgumentException Array length must be a multiple of m.
   */
  public PNMatrix (int vals[], int m) {
    this.m = m;
    n = (m != 0 ? vals.length/m : 0);
    if (m*n != vals.length) {
      throw new IllegalArgumentException("Array length must be a multiple of m.");
    }
    A = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        A[i][j] = vals[i+j*m];
      }
    }
  }
//######################################################################################
  /**
   * Append a column matrix (vector) to the right of another matrix.
   * @param X Column matrix (vector) to append.
   * @return The matrix with the column vector appended to the right.
   * @exception ArrayIndexOutOfBoundsException Submatrix indices
   */
  public PNMatrix appendVector (PNMatrix X) {
    PNMatrix R = new PNMatrix(m, n+1);
    // the extended matrix
    R.setMatrix(0, m-1, 0, n-1, this);

    try {

      for (int i = 0; i < m; i++)
        R.set(i, n, X.get(i, 0));
    } catch(ArrayIndexOutOfBoundsException e) {
      throw new ArrayIndexOutOfBoundsException("Row indices incompatible");
    }
    return R;
  }
//######################################################################################
  /**
   * Check if a matrix has a row that satisfies the cardinality condition 1.1.b of the algorithm.
   * @return True if the matrix satisfies the condition and linear combination of columns followed by column elimination is required.
   */
  public int cardinalityCondition(){
    int cardRow = -1; // a value >= 0 means either pPlus or pMinus have cardinality == 1
    // and it is the value of the row where this condition occurs
    // -1 means that both pPlus and pMinus have cardinality != 1
    int pPlusCard = 0, pMinusCard = 0, countpPlus = 0, countpMinus = 0;
    int[] pPlus, pMinus; // arrays containing the indices of +ve and -ve
    int m = getRowDimension(), n = getColumnDimension();
    int pLength = n, mLength = n;

    for (int i = 0; i < m; i++){
      countpPlus = 0;
      countpMinus = 0;
      pPlus = getPositiveIndices(i); // get +ve indices of ith row
      pMinus = getNegativeIndices(i); // get -ve indices of ith row
      for (int j = 0; j < pLength; j++){
        if (pPlus[j] != 0) // if there is nonzero element count it
          countpPlus++;
      }
      for (int j = 0; j < mLength; j++){
        if (pMinus[j] != 0) // if there is nonzero element count it
          countpMinus++;
      }
      if (countpPlus == 1 || countpMinus == 1)
        return i;
    }
    return cardRow;
  }
//######################################################################################
  /**
   * Find the column index of the element in the pPlus or pMinus set, where pPlus or pMinus has cardinality == 1.
   * @return The column index, -1 if unsuccessful (this shouldn't happen under normal operation).
   */
  public int cardinalityOne(){
    int k = -1; // the col index of cardinality == 1 element

    int pPlusCard = 0, pMinusCard = 0, countpPlus = 0, countpMinus = 0;
    int[] pPlus, pMinus; // arrays containing the indices of +ve and -ve
    int m = getRowDimension(), n = getColumnDimension();
    int pLength = n, mLength = n;

    for (int i = 0; i < m; i++){
      countpPlus = 0;
      countpMinus = 0;
      pPlus = getPositiveIndices(i); // get +ve indices of ith row
      pMinus = getNegativeIndices(i); // get -ve indices of ith row
      for (int j = 0; j < pLength; j++){
        if (pPlus[j] != 0) // if there is nonzero element count it
          countpPlus++;
      }
      for (int j = 0; j < mLength; j++){
        if (pMinus[j] != 0) // if there is nonzero element count it
          countpMinus++;
      }
      if (countpPlus == 1)
        return pPlus[0] - 1;
      if (countpMinus == 1)
        return pMinus[0] - 1;
    }

    return k;
  }
//######################################################################################
  /**
   * Check if a matrix satisfies condition 1.1 of the algorithm.
   * @return True if the matrix satisfies the condition and column elimination is required.
   */
  public boolean checkCase11(){
    boolean satisfies11 = false; // true means there is an empty set pPlus or pMinus
    // false means that both pPlus and pMinus are non-empty
    boolean pPlusEmpty = true, pMinusEmpty = true;
    int[] pPlus, pMinus; // arrays containing the indices of +ve and -ve
    int m = getRowDimension();

    for (int i = 0; i < m; i++){
      pPlusEmpty = true;
      pMinusEmpty = true;
      pPlus = getPositiveIndices(i); // get +ve indices of ith row
      pMinus = getNegativeIndices(i); // get -ve indices of ith row
      int pLength = pPlus.length, mLength = pMinus.length;

      for (int j = 0; j < pLength; j++){
        if (pPlus[j] != 0) // if there is nonzero element then false (non-empty set)
          pPlusEmpty = false;
      }
      for (int j = 0; j < mLength; j++){
        if (pMinus[j] != 0) // if there is nonzero element then false (non-empty set)
          pMinusEmpty = false;
      }
      // if there is an empty set and it is not a zeros-only row then column elimination is possible
      if ((pPlusEmpty || pMinusEmpty) && !isZeroRow(i))
        return true;
      // reset pPlus and pMinus to 0
      for (int j = 0; j < pLength; j++)
        pPlus[j] = 0;

      for (int j = 0; j < mLength; j++)
        pMinus[j] = 0;
    }
    return satisfies11;
  }
//######################################################################################
  /**
   * Find the comlumn indices to be changed by linear combination.
   * @return An array of integers, these are the indices increased by 1 each.
   */
  public int[] colsToUpdate(){
    int js[] = null; // An array of integers with the comlumn indices to be changed by linear combination.
    //the col index of cardinality == 1 element

    int pPlusCard = 0, pMinusCard = 0, countpPlus = 0, countpMinus = 0;
    int[] pPlus, pMinus; // arrays containing the indices of +ve and -ve
    int m = getRowDimension(), n = getColumnDimension();
    int pLength = n, mLength = n;

    for (int i = 0; i < m; i++){
      countpPlus = 0;
      countpMinus = 0;
      pPlus = getPositiveIndices(i); // get +ve indices of ith row
      pMinus = getNegativeIndices(i); // get -ve indices of ith row
      for (int j = 0; j < pLength; j++){
        if (pPlus[j] != 0) // if there is nonzero element count it
          countpPlus++;
      }
      for (int j = 0; j < mLength; j++){
        if (pMinus[j] != 0) // if there is nonzero element count it
          countpMinus++;
      }
      // if pPlus has cardinality ==1 return all the elements in pMinus reduced by 1 each
      if (countpPlus == 1)
        return pMinus;

      // if pMinus has cardinality ==1 return all the elements in pPlus reduced by 1 each
      else if (countpMinus == 1)
        return pPlus;

    }

    return js;
  }
//######################################################################################
  /**
   * Construct a matrix from a copy of a 2-D array.
   * @param A Two-dimensional array of integers.
   * @return The copied matrix.
   * @exception IllegalArgumentException All rows must have the same length
   */
  public static PNMatrix constructWithCopy(int[][] A) {
    int m = A.length;
    int n = A[0].length;
    PNMatrix X = new PNMatrix(m,n);
    int[][] C = X.getArray();
    for (int i = 0; i < m; i++) {
      if (A[i].length != n) {
        throw new IllegalArgumentException
    ("All rows must have the same length.");
      }
      for (int j = 0; j < n; j++) {
        C[i][j] = A[i][j];
      }
    }
    return X;
  }
//######################################################################################
  /**
   * Make a deep copy of a matrix
   * @return The matrix copy.
   */
  public PNMatrix copy () {
    PNMatrix X = new PNMatrix(m,n);
    int[][] C = X.getArray();
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        C[i][j] = A[i][j];
      }
    }
    return X;
  }
//######################################################################################
  /**
   * Clone the IntMatrix object.
   * @return  The clone of the current matrix.
   */
  public Object clone () {
    return this.copy();
  }
//######################################################################################
  /**
   * Eliminate a column from the matrix, column index is toDelete
   * @param  toDelete  The column number to delete.
   * @return The matrix with the required row deleted.
   */
  public PNMatrix eliminateCol(int toDelete) {
    int m = getRowDimension(), n = getColumnDimension();
    PNMatrix reduced = new PNMatrix(m, n);
    int [] cols = new int [n-1]; // array of cols which will not be eliminated
    int count = 0;

    // find the col numbers which will not be eliminated
    for (int i = 0; i < n; i++) {
      // if an index will not be eliminated, keep it in the new array cols
      if (i != toDelete)
        cols[count++] = i;
    }
    // System.out.print("Eliminating column " + toDelete + " from matrix below... keeping columns ");
    // printArray(cols);
    // print(2, 0);
    //  System.out.println("Reduced matrix");
    reduced = getMatrix(0, m-1, cols);
    //  reduced.print(2, 0);

    return reduced;
  }
//######################################################################################
  /**
   * Access the internal two-dimensional array.
   * @return Pointer to the two-dimensional array of matrix elements.
   */
  public int[][] getArray () {
    return A;
  }
//######################################################################################
  /**
   * Copy the internal two-dimensional array.
   * @return Two-dimensional array copy of matrix elements.
   */
  public int[][] getArrayCopy () {
    int[][] C = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        C[i][j] = A[i][j];
      }
    }
    return C;
  }
//######################################################################################
  /**
   * Make a one-dimensional column packed copy of the internal array.
   * @return Matrix elements packed in a one-dimensional array by columns.
   */
  public int[] getColumnPackedCopy () {
    int[] vals = new int[m*n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        vals[i+j*m] = A[i][j];
      }
    }
    return vals;
  }
//######################################################################################
  /**
   * Make a one-dimensional row packed copy of the internal array.
   * @return Matrix elements packed in a one-dimensional array by rows.
   */
  public int[] getRowPackedCopy () {
    int[] vals = new int[m*n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        vals[i*n+j] = A[i][j];
      }
    }
    return vals;
  }
//######################################################################################
  /**
   * Get row dimension.
   * @return The number of rows.