This article describes the definition and usage of sparse matrix of Java data structures. Share it for your reference, as follows:
Triple class for sparse matrix nonzero elements:
package com.clarck.datastructure.matrix;/** * Compressed storage of sparse matrix* * Triple class of non-zero elements of sparse matrix* * @author clarck * */public class Triple implements Comparable<Triple> { // Row number, column number, element value, default access permissions int row, column, value; public Triple(int row, int column, int value) { if (row < 0 || column < 0) { throw new IllegalArgumentException("The row/column number of sparse matrix element triplets is not positive"); } this.row = row; this.colum = column; this.value = value; } /** * Copy the constructor and copy a triple* * @param elem */ public Triple(Triple elem) { this(elem.row, elem.colum, elem.value); } @Override public String toString() { return "(" + row + ", " + column + ", " + value + ")"; } /** * Are the two triples equal? Compare the position and element values*/ public boolean equals(Object obj) { if (!(obj instanceof Triple)) return false; Triple elem = (Triple) obj; return this.row == elem.row && this.colum == elem.colum && this.value == elem.value; } /** * Compare the sizes of two triplets according to the triplet position, regardless of the element value, and agree on the order of triplets sorting*/ @Override public int compareTo(Triple elem) { //The current triplet object is small if (this.row < elem.row || this.row == elem.row && this.colum < elem.colum) return -1; //Equal, different from the equals method if (this.row == elem.row && this.colum == elem.colum) return 0; //The current triple object is large return 1; } /** * Addition, += operator function* @param term */ public void add(Triple term) { if (this.compareTo(term) == 0) this.value += term.value; else throw new IllegalArgumentException("The exponents of the two items are different, and cannot be added"); } /** * Convention to delete elements* * @return */ public boolean removable() { //Elements not stored as 0 return this.value == 0; } /** * Return a triple of a symmetric position matrix element* @return */ public Triple toSymmetry() { return new Triple(this.colum, this.row, this.value); } /** * Addition operation, overload operator + * @return */ public Triple plus(Triple term) { Triple tmp = new Triple(this); tmp.add(term); return tmp; }}Sparse matrix classes stored in triplicate order:
package com.clarck.datastructure.matrix;import com.clarck.datastructure.linear.SeqList;/** * Compressed storage of sparse matrix* * Sparse matrix triple order table* * Sparse matrix class stored in triple order* * @author clarck * */public class SeqSparseMatrix { // Matrix rows and columns private int rows, columns; // Sparse matrix triple order table private SeqList<Triple> list; /** * Construct rows rows, columns column zero matrix* * @param rows * @param columns */ public SeqSparseMatrix(int rows, int columns) { if (rows <= 0 || columns <= 0) throw new IllegalArgumentException("The number of rows or columns of matrix is non-positive"); this.rows = rows; this.columns = columns; // Construct an empty order table and execute the SeqList() constructor this.list = new SeqList<Triple>(); } public SeqSparseMatrix(int rows, int columns, Triple[] elems) { this(rows, columns); // Insert a triple of an element in main order for (int i = 0; i < elems.length; i++) this.set(elems[i]); } /** * Return the j-th column element of the matrix row and column, the order search algorithm of the sorting order table, O(n) * * @param i * @param j * @return */ public int get(int i, int j) { if (i < 0 || i >= rows || j < 0 || j >= columns) throw new IndexOutOfBoundsException("The row or column number of the matrix element goes out of bounds"); Triple item = new Triple(i, j, 0); int k = 0; Triple elem = this.list.get(k); // Find item objects in the sorting order list while (k < this.list.length() && item.compareTo(elem) >= 0) { // Only compare the positions of triple elements, that is, elem.row == i && elem.column == j if (item.compareTo(elem) == 0) return elem.value; // Find (i, j), return matrix element k++; elem = this.list.get(k); } return 0; } /** * Set matrix element with triple * @param elem */ public void set(Triple elem) { this.set(elem.row, elem.colum, elem.value); } /** * Set the element value of the column column of the matrix to value, change or insert a triple of an element in the sorting order list in the main order of rows of the matrix, O(n) * * @param row * @param column * @param value */ public void set(int row, int column, int value) { // No element stored as 0 if (value == 0) return; if (row >= this.rows || column >= this.columns) throw new IllegalArgumentException("The row or column number of triple out of bounds"); Triple elem = new Triple(row, column, value); int i = 0; // Find the elem object in the sorted triple order table, or change or insert while (i < this.list.length()) { Triple item = this.list.get(i); // If elem exists, change the position matrix element if (elem.compareTo(item) == 0) { // Set the i-th element of the order table to elem this.list.set(i, elem); return; } // Walk backward when elem is large (elem.compareTo(item) >= 0) i++; else break; } this.list.insert(i, elem); } @Override public String toString() { String str = "Triple order table: " + this.list.toString() + "/n"; str += "sparse matrix" + this.getClass().getSimpleName() + "(" + rows + " * " + columns + "): /n"; int k = 0; // Returns the k-th element, if the k-specified sequence number is invalid, it returns null Triple elem = this.list.get(k++); for (int i = 0; i < this.rows; i++) { for (int j = 0; j < this.columns; j++) if (elem != null && i == elem.row && j == elem.colum) { str += String.format("%4d", elem.value); elem = this.list.get(k++); } else { str += String.format("%4d", 0); } str += "/n"; } return str; } /** * Return the matrix where the current matrix is added to smat, smatc=this+smat, does not change the current matrix, the algorithm adds to two polynomials* * @param smat * @return */ public SeqSparseMatrix plus(SeqSparseMatrix smat) { if (this.rows != smat.rows || this.columns != smat.columns) throw new IllegalArgumentException("The two matrices have different orders, and cannot be added"); // Construct rows*columns zero matrix SeqSparseMatrix smartc = new SeqSparseMatrix(this.rows, this.columns); int i = 0, j = 0; // traverse the order table of the two matrices respectively while (i < this.list.length() && j < smart.list.length()) { Triple elema = this.list.get(i); Triple elemb = smart.list.get(j); // If two triples represent matrix elements at the same position, the corresponding element values are added if (elema.compareTo(elemb) == 0) { // The addition result is not zero, then a new element is created if (elema.value + elemb.value != 0) smartc.list.append(new Triple(elema.row, elema.colum, elema.value + elemb.value)); i++; j++; } else if (elema.compareTo(elemb) < 0) { // Add the smaller triple copy to the last of the smatc order table // Copy the elema element to execute the Triple copy constructor method smartc.list.append(new Triple(elema)); i++; } else { smartc.list.append(new Triple(elemb)); j++; } } // Add the remaining triple copy of the current matrix order table to the last of the smatc order table while (i < this.list.length()) smartc.list.append(new Triple(this.list.get(i++))); // Add the remaining triple copy in smart to the last of the smatc order table while (j < smartc.list.length()) { Triple elem = smat.list.get(j++); if (elem != null) { smatc.list.append(new Triple(elem)); } } return smartc; } /** * The current matrix is added to the smat matrix, this+=smat, change the current matrix, and the algorithm adds the two polynomials* * @param smat */ public void add(SeqSparseMatrix smat) { if (this.rows != smat.rows || this.columns != smat.columns) throw new IllegalArgumentException("The two matrices have different orders, and cannot be added"); int i = 0, j = 0; // Insert (or add) each triplet of mat into the current matrix triplet order table while (i < this.list.length() && j < smat.list.length()) { Triple elema = this.list.get(i); Triple elemb = smart.list.get(j); // If two triplets represent matrix elements at the same position, the corresponding element values are added if (elema.compareTo(elemb) == 0) { // The addition result is not 0, then a new element is created if (elema.value + elemb.value != 0) this.list.set(i++, new Triple(elema.row, elema.colum, elema.value + elemb.value)); else this.list.remove(i); j++; } else if (elema.compareTo(elemb) < 0) { // Continue to look for the insert element of the elemb element i++; } else { // Copy the elemb element to insert the ith element as this.list.insert(i++, new Triple(elemb)); j++; } } // Copy the remaining triples in mat into the current matrix triplet order table while (j < smat.list.length()) { this.list.append(new Triple(smat.list.get(j++))); } } // Deep copy public SeqSparseMatrix(SeqSparseMatrix smat) { this(smat.rows, smat.columns); // Create an empty order table, default capacity this.list = new SeqList<Triple>(); // Copy all triple objects in smat for (int i = 0; i < smat.list.length(); i++) this.list.append(new Triple(smat.list.get(i))); } /** * Compare whether two matrices are equal*/ public boolean equals(Object obj) { if (this == obj) return true; if (!(obj instanceof SeqSparseMatrix)) return false; SeqSparseMatrix smat = (SeqSparseMatrix) obj; return this.rows == smat.rows && this.columns == smat.columns && this.list.equals(smat.list); } /** * Return transpose matrix* @return */ public SeqSparseMatrix transpose() { //Construct a zero matrix, specify the number of rows and columns SeqSparseMatrix trans = new SeqSparseMatrix(columns, rows); for (int i = 0; i < this.list.length(); i++) { //Insert the triple trans.set(this.list.get(i).toSymmetry()); } return trans; }}Test class:
package com.clarck.datastructure.matrix;/** * Compressed storage of sparse matrix* * Sparse matrix triple order table* * Sparse matrix represented by triple order table and its addition operations* * @author clarck * */public class SeqSparseMatrix_test { public static void main(String args[]) { Triple[] elemsa = { new Triple(0, 2, 11), new Triple(0, 4, 17), new Triple(1, 1, 20), new Triple(3, 0, 19), new Triple(3, 5, 28), new Triple(4, 4, 50) }; SeqSparseMatrix smata = new SeqSparseMatrix(5, 6, elemsa); System.out.print("A " + smata.toString()); Triple[] elemsb = { new Triple(0, 2, -11), new Triple(0, 4, -17), new Triple(2, 3, 51), new Triple(3, 0, 10), new Triple(4, 5, 99), new Triple(1, 1, 0) }; SeqSparseMatrix smatb = new SeqSparseMatrix(5,6,elemsb); System.out.print("B " + smatb.toString()); SeqSparseMatrix smatc = smata.plus(smatb); System.out.print("C=A+B"+smatc.toString()); System.out.println(); smata.add(smatb); System.out.print("A+=B" + smata.toString()); System.out.println("C.equals(A)?" + smatc.equals(smata)); SeqSparseMatrix smatd = new SeqSparseMatrix(smatb); smatb.set(0,2,1); System.out.print("B " + smatb.toString()); System.out.print("D " + smatd.toString()); System.out.println("A transpose" + smata.transpose().toString()); }}Running results:
A Triple order table: ((0, 2, 11), (0, 4, 17), (1, 1, 20), (3, 0, 19), (3, 5, 28), (4, 4, 50)) Sparse matrix SeqSparseMatrix(5 * 6): 0 0 11 0 17 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0 28 0 0 0 0 0 0 50 0B Triple order table: ((0, 2, -11), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))Sparse Matrix SeqSparseMatrix(5 * 6): 0 0 -11 0 -17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 28 0 0 0 0 0 50 99A+=B triple order table: ((1, 1, 20), (2, 3, 51), (3, 0, 29), (3, 5, 28), (4, 4, 50), (4, 5, 99)) sparse matrix SeqSparseMatrix(5 * 6): 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 51 0 0 29 0 0 0 0 0 28 0 0 0 0 0 0 50 99C.equals(A)?trueB triple order table: ((0, 2, 1), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))Sparse Matrix SeqSparseMatrix(5 * 6): 0 0 1 0 -17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 99A transposed triple order table: ((0, 3, 29), (1, 1, 20), (3, 2, 51), (4, 4, 50), (5, 3, 28), (5, 4, 99)) sparse matrix SeqSparseMatrix(6 * 5): 0 0 0 29 0 0 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 28 99
For more information about Java algorithms, readers who are interested in this site can view the topics: "Java Data Structure and Algorithm Tutorial", "Summary of Java Operation DOM Node Tips", "Summary of Java File and Directory Operation Tips" and "Summary of Java Cache Operation Tips"
I hope this article will be helpful to everyone's Java programming.