core/vnl/vnl_sparse_matrix.h
Go to the documentation of this file.
00001 // This is core/vnl/vnl_sparse_matrix.h
00002 #ifndef vnl_sparse_matrix_h_
00003 #define vnl_sparse_matrix_h_
00004 #ifdef VCL_NEEDS_PRAGMA_INTERFACE
00005 #pragma interface
00006 #endif
00007 //:
00008 //  \file
00009 //  \brief Simple sparse matrix
00010 //
00011 //    Only those values which
00012 //    are non-zero are stored. The sparse matrix currently supports
00013 //    only getting/putting elements, and multiply by vector or another
00014 //    sparse matrix.
00015 //
00016 //    Each row is stored as a vector of vcl_pair<unsigned int,T>, where the first
00017 //    of the pair indicates the column index, and the second the
00018 //    value.  All rows are stored, as vcl_vector< row >;
00019 //
00020 //  \author Rupert W. Curwen, GE CR&D
00021 //  \date   20 Oct 98
00022 //
00023 // \verbatim
00024 //  Modifications
00025 //   Robin Flatland 5/31/99 Added pre_mult(lhs,result), where
00026 //                          lhs is a vector.
00027 //
00028 //   Robin Flatland 6/08/99 Added iterator that allows sequential
00029 //                          access to non-zero values in matrix.
00030 //                          Iterator is controlled using reset, next,
00031 //                          getrow, getcolumn, and value.
00032 //
00033 //   David Capel May 2000   Added set_row, scale_row, mult, vcat and const
00034 //                          methods where appropriate.
00035 //   Peter Vanroose - Jan.2009 - Added several methods, modelled after vnl_matrix<T>:
00036 //     const version of operator()(unsigned int, unsigned int)
00037 //     T get(unsigned int, unsigned int)
00038 //     void put(unsigned int, unsigned int, T)
00039 //     void clear()
00040 //     vnl_sparse_matrix& normalize_rows()
00041 //     bool operator==()
00042 //     bool operator!=()
00043 //     unary minus of a matrix
00044 //     addition of two matrices
00045 //     subtraction of two matrices
00046 //     multiplication of two matrices
00047 //     in-place addition of two matrices
00048 //     in-place subtraction of two matrices
00049 //     in-place multiplication of two matrices
00050 //     scalar multiplication of a matrix
00051 //     in-place scalar multiplication of a matrix
00052 //     scalar division of a matrix
00053 //     in-place scalar division of a matrix
00054 //   Peter Vanroose - Oct.2010 - Added set_identity()
00055 //   Peter Vanroose - Mar.2011 - Added transpose() and conjugate_transpose()
00056 // \endverbatim
00057 
00058 #include <vcl_vector.h>
00059 #include <vnl/vnl_vector.h>
00060 #include <vcl_functional.h>
00061 
00062 //: Stores elements of sparse matrix
00063 //  Only those values which
00064 //  are non-zero are stored. The sparse matrix currently supports
00065 //  only getting/putting elements, and multiply by vector or another
00066 //  sparse matrix.
00067 //
00068 //  Each row is stored as a vector of vcl_pair<unsigned int,T>, where the first
00069 //  of the pair indicates the column index, and the second the
00070 //  value.  All rows are stored, as vcl_vector< row >;
00071 //
00072 template <class T>
00073 class vnl_sparse_matrix_pair
00074 {
00075  public:
00076   unsigned int first;
00077   T second;
00078 
00079   //: Constructs a pair with null values
00080   vnl_sparse_matrix_pair() : first(0), second(T(0)) {}
00081 
00082   //: Constructs a pair with position a and value b
00083   vnl_sparse_matrix_pair(unsigned int const& a, T const& b) : first(a), second(b) {}
00084 
00085   vnl_sparse_matrix_pair(const vnl_sparse_matrix_pair<T>& o) : first(o.first), second(o.second) {}
00086 
00087   vnl_sparse_matrix_pair<T>& operator=(vnl_sparse_matrix_pair const &o) {
00088     if (&o != this) {
00089       first = o.first;
00090       second = o.second;
00091     }
00092     return *this;
00093   }
00094 
00095   struct less : public vcl_binary_function<vnl_sparse_matrix_pair, vnl_sparse_matrix_pair, bool>
00096   {
00097     bool operator() (vnl_sparse_matrix_pair const& p1, vnl_sparse_matrix_pair const& p2) {
00098       return p1.first < p2.first;
00099     }
00100   };
00101 };
00102 
00103 
00104 //: Simple sparse matrix
00105 //  Stores non-zero elements as a sparse_matrix_pair
00106 template <class T>
00107 class vnl_sparse_matrix
00108 {
00109  public:
00110   typedef vnl_sparse_matrix_pair<T> pair_t;
00111 #if defined(VCL_SUNPRO_CC)
00112   // SunPro is the broken one.
00113   typedef vcl_vector < typename pair_t > row;
00114   typedef vcl_vector < typename row > vnl_sparse_matrix_elements;
00115 #else
00116   typedef vcl_vector < pair_t > row;
00117   typedef vcl_vector < row > vnl_sparse_matrix_elements;
00118 #endif
00119 
00120   //: Construct an empty matrix
00121   vnl_sparse_matrix();
00122 
00123   //: Construct an empty m*n matrix
00124   vnl_sparse_matrix(unsigned int m, unsigned int n);
00125 
00126   //: Construct an m*n Matrix and copy rhs into it.
00127   vnl_sparse_matrix(vnl_sparse_matrix<T> const& rhs);
00128 
00129   //: Copy another vnl_sparse_matrix<T> into this.
00130   vnl_sparse_matrix<T>& operator=(vnl_sparse_matrix<T> const& rhs);
00131 
00132   //: Multiply this*rhs, where rhs is a vector.
00133   void mult(vnl_vector<T> const& rhs, vnl_vector<T>& result) const;
00134 
00135   //: Multiply this*p, a fortran order matrix.
00136   void mult(unsigned int n, unsigned int m, T const* p, T* q) const;
00137 
00138   //: Multiplies lhs*this, where lhs is a vector
00139   void pre_mult(const vnl_vector<T>& lhs, vnl_vector<T>& result) const;
00140 
00141   //: Get a reference to an entry in the matrix.
00142   T& operator()(unsigned int row, unsigned int column);
00143 
00144   //: Get the value of an entry in the matrix.
00145   T operator()(unsigned int row, unsigned int column) const;
00146 
00147   //: Get an entry in the matrix.
00148   //  This is the "const" version of operator().
00149   T get(unsigned int row, unsigned int column) const;
00150 
00151   //: Put (i.e., add or overwrite) an entry into the matrix.
00152   void put(unsigned int row, unsigned int column, T value);
00153 
00154   //: Get diag(A_transpose * A).
00155   // Useful for forming Jacobi preconditioners for linear solvers.
00156   void diag_AtA(vnl_vector<T>& result) const;
00157 
00158   //: Set a whole row at once. Much faster. Returns *this.
00159   vnl_sparse_matrix& set_row(unsigned int r,
00160                              vcl_vector<int> const& cols,
00161                              vcl_vector<T> const& vals);
00162 
00163   //: Return row as vector of pairs
00164   //  Added to aid binary I/O
00165   row& get_row(unsigned int r) {return elements[r];}
00166 
00167   //: Laminate matrix A onto the bottom of this one
00168   vnl_sparse_matrix<T>& vcat(vnl_sparse_matrix<T> const& A);
00169 
00170   //: Get the number of rows in the matrix.
00171   unsigned int rows() const { return rs_; }
00172 
00173   //: Get the number of columns in the matrix.
00174   unsigned int columns() const { return cs_; }
00175 
00176   //: Get the number of columns in the matrix.
00177   unsigned int cols() const { return cs_; }
00178 
00179   //: Return whether a given row is empty
00180   bool empty_row(unsigned int r) const { return elements[r].empty(); }
00181 
00182   //: This is occasionally useful.
00183   T sum_row(unsigned int r);
00184 
00185   //: Useful for normalizing row sums in convolution operators
00186   vnl_sparse_matrix& scale_row(unsigned int r, T scale);
00187 
00188   //: Set all elements to null
00189   void clear() { elements.clear(); }
00190 
00191   //: Resizes the array to have r rows and c cols -- sets elements to null
00192   void set_size( int r, int c );
00193 
00194   //: Resizes the array to have r rows and c cols
00195   void resize( int r, int c );
00196 
00197   //: Resets the internal iterator
00198   void reset() const;
00199 
00200   //: Moves the internal iterator to next non-zero entry in matrix.
00201   // Returns true if there is another value, false otherwise. Use
00202   // in combination with methods reset, getrow, getcolumn, and value.
00203   bool next() const;
00204 
00205   //: Returns the row of the entry pointed to by internal iterator.
00206   int getrow() const;
00207 
00208   //: Returns the column of the entry pointed to by internal iterator.
00209   int getcolumn() const;
00210 
00211   //: Returns the value pointed to by the internal iterator.
00212   T value() const;
00213 
00214   //: Comparison
00215   bool operator==(vnl_sparse_matrix<T> const& rhs) const;
00216 
00217   //: Inequality
00218   bool operator!=(vnl_sparse_matrix<T> const& rhs) const
00219   { return !operator==(rhs); }
00220 
00221   //: Unary minus
00222   vnl_sparse_matrix<T> operator-() const;
00223 
00224   //: addition
00225   vnl_sparse_matrix<T> operator+(vnl_sparse_matrix<T> const& rhs) const;
00226 
00227   //: subtraction
00228   vnl_sparse_matrix<T> operator-(vnl_sparse_matrix<T> const& rhs) const;
00229 
00230   //: multiplication
00231   vnl_sparse_matrix<T> operator*(vnl_sparse_matrix<T> const& rhs) const;
00232 
00233   //: in-place addition
00234   vnl_sparse_matrix<T>& operator+=(vnl_sparse_matrix<T> const& rhs);
00235 
00236   //: in-place subtraction
00237   vnl_sparse_matrix<T>& operator-=(vnl_sparse_matrix<T> const& rhs);
00238 
00239   //: in-place multiplication
00240   vnl_sparse_matrix<T>& operator*=(vnl_sparse_matrix<T> const& rhs);
00241 
00242   //: scalar multiplication
00243   vnl_sparse_matrix<T> operator*(T const& rhs) const;
00244 
00245   //: in-place scalar multiplication
00246   vnl_sparse_matrix<T>& operator*=(T const& rhs);
00247 
00248   //: scalar division
00249   vnl_sparse_matrix<T> operator/(T const& rhs) const;
00250 
00251   //: in-place scalar division
00252   vnl_sparse_matrix<T>& operator/=(T const& rhs);
00253 
00254   //: returns a new sparse matrix, viz. the transpose of this
00255   vnl_sparse_matrix<T> transpose() const;
00256 
00257   //: returns a new sparse matrix, viz. the conjugate (or Hermitian) transpose of this
00258   vnl_sparse_matrix<T> conjugate_transpose() const;
00259 
00260   //: Sets this matrix to an identity matrix, then returns "*this".
00261   //  Returning "*this" allows e.g. passing an identity matrix as argument to
00262   //  a function f, without having to name the constructed matrix:
00263   //  \code
00264   //     f(vnl_sparse_matrix<double>(5000,5000).set_identity());
00265   //  \endcode
00266   //  Returning "*this" also allows "chaining" two or more operations:
00267   //  e.g., to set a matrix to identity, then add an other matrix to it:
00268   //  \code
00269   //     M.set_identity() += M2;
00270   //  \endcode
00271   //  If the matrix is not square, anyhow set main diagonal to 1, the rest to 0.
00272   vnl_sparse_matrix& set_identity();
00273 
00274   //: Normalizes each row so it is a unit vector, and returns "*this".
00275   //  Zero rows are not modified
00276   //  Returning "*this" allows "chaining" two or more operations:
00277   //  \code
00278   //     M.normalize_rows() += M2;
00279   //  \endcode
00280   //  Note that there is no method normalize_columns() since its implementation
00281   //  would be much more inefficient than normalize_rows()!
00282   vnl_sparse_matrix& normalize_rows();
00283 
00284   // These three methods are used to implement their operator() variants
00285   // They should ideally be protected, but for backward compatibility reasons
00286   // they continue to be public for a while ...
00287 
00288   //: Add rhs to this.
00289   //  Deprecated for direct use: please use operator "+" instead.
00290   void add(const vnl_sparse_matrix<T>& rhs, vnl_sparse_matrix<T>& result) const;
00291 
00292   //: Subtract rhs from this.
00293   //  Deprecated for direct use: please use operator "-" instead.
00294   void subtract(const vnl_sparse_matrix<T>& rhs, vnl_sparse_matrix<T>& result) const;
00295 
00296   //: Multiply this*rhs, another sparse matrix.
00297   //  Deprecated for direct use: please use operator "*" instead.
00298   void mult(vnl_sparse_matrix<T> const& rhs, vnl_sparse_matrix<T>& result) const;
00299 
00300  protected:
00301   vnl_sparse_matrix_elements elements;
00302   unsigned int rs_, cs_;
00303 
00304   // internal iterator
00305   mutable unsigned int itr_row;
00306   mutable typename row::const_iterator itr_cur;
00307   mutable bool itr_isreset;
00308 };
00309 
00310 // non-member arithmetical operators.
00311 
00312 //:
00313 // \relatesalso vnl_matrix
00314 template<class T>
00315 inline vnl_sparse_matrix<T> operator*(T const& value, vnl_sparse_matrix<T> const& m)
00316 {
00317   return m * value;
00318 }
00319 
00320 
00321 #endif // vnl_sparse_matrix_h_