001/**
002 *                    BioJava development code
003 *
004 * This code may be freely distributed and modified under the
005 * terms of the GNU Lesser General Public Licence.  This should
006 * be distributed with the code.  If you do not have a copy,
007 * see:
008 *
009 *      http://www.gnu.org/copyleft/lesser.html
010 *
011 * Copyright for this code is held jointly by the individual
012 * authors.  These should be listed in @author doc comments.
013 *
014 * For more information on the BioJava project and its aims,
015 * or to join the biojava-l mailing list, visit the home page
016 * at:
017 *
018 *      http://www.biojava.org/
019 *
020 * Created on 5 Mar 2013
021 * Created by Andreas Prlic
022 *
023 * @since 3.0.6
024 */
025package org.biojava.nbio.structure.math;
026
027import java.io.Serializable;
028
029
030/**
031 *
032 *  A sparse, square matrix, implementing using two arrays of sparse
033 *  vectors, one representation for the rows and one for the columns.
034 *
035 *  For matrix-matrix product, we might also want to store the
036 *  column representation.
037 *
038 * Derived from http://introcs.cs.princeton.edu/java/44st/SparseMatrix.java.html
039 *
040 *  For additional documentation, see <a href="http://introcs.cs.princeton.edu/44st">Section 4.4</a> of
041 *  <i>Introduction to Programming in Java: An Interdisciplinary Approach</i> by Robert Sedgewick and Kevin Wayne.
042 *
043 *
044 **/
045
046public class SparseSquareMatrix implements Serializable {
047        /**
048         *
049         */
050        private static final long serialVersionUID = -5217767192992868955L;
051
052        private final int N;           // N-by-N matrix
053        private SparseVector[] rows;   // the rows, each row is a sparse vector
054
055        /** initialize an N-by-N matrix of all 0s
056         *
057         * @param N - size
058         */
059        public SparseSquareMatrix(int N) {
060                this.N  = N;
061                rows = new SparseVector[N];
062
063                for (int i = 0; i < N; i++)
064                        rows[i] = new SparseVector(N);
065        }
066
067        /** set A[i][j] = value
068         *
069         * @param i
070         * @param j
071         * @param value
072         */
073        public void put(int i, int j, double value) {
074
075                if (i < 0 || i >= N) throw new IllegalArgumentException("Illegal index");
076                if (j < 0 || j >= N) throw new IllegalArgumentException("Illegal index");
077
078                rows[i].put(j, value);
079        }
080
081        /** access a value at i,j
082         *
083         * @param i
084         * @param j
085         * @return return A[i][j]
086         */
087        public double get(int i, int j) {
088
089                if (i < 0 || i >= N) throw new IllegalArgumentException("Illegal index " + i + " should be > 0 and < " + N);
090                if (j < 0 || j >= N) throw new IllegalArgumentException("Illegal index " + j + " should be > 0 and < " + N);
091
092                return rows[i].get(j);
093        }
094
095        /**  return the number of nonzero entries (not the most efficient implementation)
096         *
097         * @return
098         */
099        public int nnz() {
100
101                int sum = 0;
102
103                for (int i = 0; i < N; i++)
104                        sum += rows[i].nnz();
105
106                return sum;
107        }
108
109        /**
110         *
111         * @param x
112         * @return  return the matrix-vector product b = Ax
113         */
114        public SparseVector times(SparseVector x) {
115
116                SparseSquareMatrix A = this;
117
118                if (N != x.size()) throw new IllegalArgumentException("Dimensions disagree. " + N + " != " + x.size());
119
120                SparseVector b = new SparseVector(N);
121
122                for (int i = 0; i < N; i++)
123                        b.put(i, A.rows[i].dot(x));
124
125                return b;
126        }
127
128        /** return C = A + B
129         *
130         * @param B
131         * @return
132         */
133        public SparseSquareMatrix plus(SparseSquareMatrix B) {
134
135                SparseSquareMatrix A = this;
136
137                if (A.N != B.N) throw new IllegalArgumentException("Dimensions disagree. " + A.N + " != " + B.N);
138
139                SparseSquareMatrix C = new SparseSquareMatrix(N);
140
141                for (int i = 0; i < N; i++)
142                        C.rows[i] = A.rows[i].plus(B.rows[i]);
143
144                return C;
145        }
146
147
148        @Override
149        public String toString() {
150
151                StringBuilder s = new StringBuilder();
152
153                s.append( "N = ");
154                s.append( N);
155                s.append(", nonzeros = ");
156                s.append( nnz());
157                s.append( System.getProperty("line.separator"));
158                for (int i = 0; i < N; i++) {
159                        s.append(i);
160                        s.append(": ");
161                        s.append( rows[i]);
162                        s.append( System.getProperty("line.separator"));
163                }
164
165                return s.toString();
166        }
167
168}