Main Page   Groups   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Concepts

vnl_sparse_matrix.h

Go to the documentation of this file.
00001 #ifndef vnl_sparse_matrix_h_
00002 #define vnl_sparse_matrix_h_
00003 // This is vxl/vnl/vnl_sparse_matrix.h
00004 
00005 //: \file
00006 //  \brief Simple Sparse Matrix
00007 //  \author Rupert W. Curwen, GE CR&D, 20 Oct 98
00008 //   Simple sparse matrix.  Only those values which
00009 //    are non-zero are stored. The sparse matrix currently supports
00010 //    only getting/putting elements, and multiply by vector or another
00011 //    sparse matrix.
00012 //
00013 //    Each row is stored as a vector of vcl_pair<unsigned int,T>, where the first
00014 //    of the pair indicates the column index, and the second the
00015 //    value.  All rows are stored, as vcl_vector< row >;
00016 //
00017 
00018 //
00019 //     Modifications
00020 //
00021 //     Robin Flatland 5/31/99 Added pre_mult(lhs,result), where
00022 //                            lhs is a vector.
00023 //
00024 //     Robin Flatland 6/08/99 Added iterator that allows sequential
00025 //                            access to non-zero values in matrix.
00026 //                            Iterator is controlled using reset, next,
00027 //                            getrow, getcolumn, and value.
00028 //
00029 //     David Capel May 2000   Added set_row, scale_row, mult, vcat and const
00030 //                            methods where appropriate.
00031 
00032 #include <vcl_vector.h>
00033 #include <vnl/vnl_vector.h>
00034 #include <vcl_functional.h>
00035 
00036 //: Stores elements of sparse matrix
00037 //  Each pair consists of a position of an element in the matrix,
00038 //  and the value of that element
00039 template <class T>
00040 class vnl_sparse_matrix_pair {
00041 public:
00042   unsigned int first;
00043   T second;
00044 
00045 //: Constructs a pair with null values
00046   vnl_sparse_matrix_pair() : first(0), second(T(0)) {}
00047 
00048 //: Constructs a pair with position a and value b
00049   vnl_sparse_matrix_pair(unsigned int const& a, T const& b) : first(a), second(b) {}
00050 
00051   vnl_sparse_matrix_pair(const vnl_sparse_matrix_pair<T>& o) : first(o.first), second(o.second) {}
00052 
00053   vnl_sparse_matrix_pair<T>& operator=(vnl_sparse_matrix_pair const &o) {
00054     if (&o != this) {
00055       first = o.first;
00056       second = o.second;
00057     }
00058     return *this;
00059   }
00060 
00061   struct less : public vcl_binary_function<vnl_sparse_matrix_pair, vnl_sparse_matrix_pair, bool> {
00062     bool operator() (vnl_sparse_matrix_pair const& p1, vnl_sparse_matrix_pair const& p2) {
00063       return p1.first < p2.first;
00064     }
00065   };
00066 
00067 };
00068 
00069 
00070 //: Simple sparse matrix
00071 //  Stores non-zero elements as a sparse_matrix_pair
00072 template <class T>
00073 class vnl_sparse_matrix {
00074 public:
00075   typedef vnl_sparse_matrix_pair<T> pair_t;
00076 #if defined(VCL_SUNPRO_CC)
00077   // SunPro is the broken one.
00078   typedef vcl_vector < typename pair_t > row ;
00079   typedef vcl_vector < typename row > vnl_sparse_matrix_elements;
00080 #else
00081   typedef vcl_vector < pair_t > row ;
00082   typedef vcl_vector < row > vnl_sparse_matrix_elements;
00083 #endif
00084 
00085   // typedef vcl_vector<typename pair_t> row;
00086 
00087   //: Construct an empty matrix
00088   vnl_sparse_matrix();
00089 
00090   //: Construct an empty m*n matrix
00091   vnl_sparse_matrix(unsigned int m, unsigned int n);
00092 
00093   //: Construct an m*n Matrix and copy rhs into it.
00094   vnl_sparse_matrix(const vnl_sparse_matrix<T>& rhs);
00095 
00096   //: Copy another vnl_sparse_matrix<T> into this.
00097   vnl_sparse_matrix<T>& operator=(const vnl_sparse_matrix<T>& rhs);
00098 
00099   //: Multiply this*rhs, another sparse matrix.
00100   void mult(const vnl_sparse_matrix<T>& rhs, vnl_sparse_matrix<T>& result) const;
00101 
00102   //: Multiply this*rhs, where rhs is a vector.
00103   void mult(const vnl_vector<T>& rhs, vnl_vector<T>& result) const;
00104 
00105   //: Multiply this*p, a fortran order matrix.
00106   void mult(unsigned int n, unsigned int m, const T* p, T* q) const;
00107 
00108   //: Multiplies lhs*this, where lhs is a vector
00109   void pre_mult(const vnl_vector<T>& lhs, vnl_vector<T>& result) const;
00110 
00111   //: Add rhs to this.
00112   void add(const vnl_sparse_matrix<T>& rhs, vnl_sparse_matrix<T>& result) const;
00113 
00114   //: Subtract rhs from this.
00115   void subtract(const vnl_sparse_matrix<T>& rhs, vnl_sparse_matrix<T>& result) const;
00116 
00117   //: Get a reference to an entry in the matrix.
00118   T& operator()(unsigned int row, unsigned int column);
00119 
00120   //: Get diag(A_tranpose * A).
00121   // Useful for forming Jacobi preconditioners for linear solvers.
00122   void diag_AtA(vnl_vector<T>& result) const;
00123 
00124   //: Set a whole row at once. Much faster.
00125   void set_row(unsigned int r,
00126                vcl_vector<int> const& cols,
00127                vcl_vector<T> const& vals);
00128 
00129   //: Return row as vector of pairs
00130   //  Added to aid binary I/O
00131   row& get_row(unsigned int r) {return elements[r];}
00132 
00133   //: Laminate matrix A onto the bottom of this one
00134   vnl_sparse_matrix<T>& vcat(vnl_sparse_matrix<T> const& A);
00135 
00136   //: Get the number of rows in the matrix.
00137   unsigned int rows() const { return rs_; }
00138 
00139   //: Get the number of columns in the matrix.
00140   unsigned int columns() const { return cs_; }
00141 
00142   //: Return whether a given row is empty
00143   bool empty_row(unsigned int r) const { return elements[r].empty(); }
00144 
00145   //: This is occasionally useful.
00146   double sum_row(unsigned int r);
00147 
00148   //: Useful for normalizing row sums in convolution operators
00149   void scale_row(unsigned int r, T scale);
00150 
00151   //: Resizes the array to have r rows and c cols
00152   //    Currently not implemented.
00153   void resize( int r, int c );
00154 
00155   //: Resets the internal iterator
00156   void reset();
00157 
00158   //: Moves the internal iterator to next non-zero entry in matrix.
00159   // Returns true if there is another value, false otherwise. Use
00160   // in combination with methods reset, getrow, getcolumn, and value.
00161   bool next();
00162 
00163   //: Returns the row of the entry pointed to by internal iterator.
00164   int getrow();
00165 
00166   //: Returns the column of the entry pointed to by internal iterator.
00167   int getcolumn();
00168 
00169   //: Returns the value pointed to by the internal iterator.
00170   T value();
00171 
00172 
00173 protected:
00174   vnl_sparse_matrix_elements elements;
00175   unsigned int rs_, cs_;
00176 
00177   // internal iterator
00178   unsigned int itr_row;
00179   typename row::iterator itr_cur;
00180   bool itr_isreset;
00181 };
00182 
00183 
00184 #endif // vnl_sparse_matrix_h_

Generated at Wed Mar 12 01:13:16 2003 for ITK by doxygen 1.2.15 written by Dimitri van Heesch, © 1997-2000