diff options
Diffstat (limited to 'build/Bonmin/include/coin/CoinPackedMatrix.hpp')
| -rw-r--r-- | build/Bonmin/include/coin/CoinPackedMatrix.hpp | 947 |
1 files changed, 947 insertions, 0 deletions
diff --git a/build/Bonmin/include/coin/CoinPackedMatrix.hpp b/build/Bonmin/include/coin/CoinPackedMatrix.hpp new file mode 100644 index 0000000..c6837ac --- /dev/null +++ b/build/Bonmin/include/coin/CoinPackedMatrix.hpp @@ -0,0 +1,947 @@ +/* $Id: CoinPackedMatrix.hpp 1560 2012-11-24 00:29:01Z lou $ */ +// Copyright (C) 2000, International Business Machines +// Corporation and others. All Rights Reserved. +// This code is licensed under the terms of the Eclipse Public License (EPL). + +#ifndef CoinPackedMatrix_H +#define CoinPackedMatrix_H + +#include "CoinError.hpp" +#include "CoinTypes.hpp" +#ifndef CLP_NO_VECTOR +#include "CoinPackedVectorBase.hpp" +#include "CoinShallowPackedVector.hpp" +#else +class CoinRelFltEq; +#endif + +/** Sparse Matrix Base Class + + This class is intended to represent sparse matrices using row-major + or column-major ordering. The representation is very efficient for + adding, deleting, or retrieving major-dimension vectors. Adding + a minor-dimension vector is less efficient, but can be helped by + providing "extra" space as described in the next paragraph. Deleting + a minor-dimension vector requires inspecting all coefficients in the + matrix. Retrieving a minor-dimension vector would incur the same cost + and is not supported (except in the sense that you can write a loop to + retrieve all coefficients one at a time). Consider physically transposing + the matrix, or keeping a second copy with the other major-vector ordering. + + The sparse represention can be completely compact or it can have "extra" + space available at the end of each major vector. Incorporating extra + space into the sparse matrix representation can improve performance in + cases where new data needs to be inserted into the packed matrix against + the major-vector orientation (e.g, inserting a row into a matrix stored + in column-major order). + + For example if the matrix: + @verbatim + 3 1 0 -2 -1 0 0 -1 + 0 2 1.1 0 0 0 0 0 + 0 0 1 0 0 1 0 0 + 0 0 0 2.8 0 0 -1.2 0 + 5.6 0 0 0 1 0 0 1.9 + + was stored by rows (with no extra space) in + CoinPackedMatrix r then: + r.getElements() returns a vector containing: + 3 1 -2 -1 -1 2 1.1 1 1 2.8 -1.2 5.6 1 1.9 + r.getIndices() returns a vector containing: + 0 1 3 4 7 1 2 2 5 3 6 0 4 7 + r.getVectorStarts() returns a vector containing: + 0 5 7 9 11 14 + r.getNumElements() returns 14. + r.getMajorDim() returns 5. + r.getVectorSize(0) returns 5. + r.getVectorSize(1) returns 2. + r.getVectorSize(2) returns 2. + r.getVectorSize(3) returns 2. + r.getVectorSize(4) returns 3. + + If stored by columns (with no extra space) then: + c.getElements() returns a vector containing: + 3 5.6 1 2 1.1 1 -2 2.8 -1 1 1 -1.2 -1 1.9 + c.getIndices() returns a vector containing: + 0 4 0 1 1 2 0 3 0 4 2 3 0 4 + c.getVectorStarts() returns a vector containing: + 0 2 4 6 8 10 11 12 14 + c.getNumElements() returns 14. + c.getMajorDim() returns 8. + @endverbatim + + Compiling this class with CLP_NO_VECTOR defined will excise all methods + which use CoinPackedVectorBase, CoinPackedVector, or CoinShallowPackedVector + as parameters or return types. + + Compiling this class with COIN_FAST_CODE defined removes index range checks. +*/ +class CoinPackedMatrix { + friend void CoinPackedMatrixUnitTest(); + +public: + + + //--------------------------------------------------------------------------- + /**@name Query members */ + //@{ + /** Return the current setting of the extra gap. */ + inline double getExtraGap() const { return extraGap_; } + /** Return the current setting of the extra major. */ + inline double getExtraMajor() const { return extraMajor_; } + + /** Reserve sufficient space for appending major-ordered vectors. + If create is true, empty columns are created (for column generation) */ + void reserve(const int newMaxMajorDim, const CoinBigIndex newMaxSize, + bool create=false); + /** Clear the data, but do not free any arrays */ + void clear(); + + /** Whether the packed matrix is column major ordered or not. */ + inline bool isColOrdered() const { return colOrdered_; } + + /** Whether the packed matrix has gaps or not. */ + inline bool hasGaps() const { return (size_<start_[majorDim_]) ; } + + /** Number of entries in the packed matrix. */ + inline CoinBigIndex getNumElements() const { return size_; } + + /** Number of columns. */ + inline int getNumCols() const + { return colOrdered_ ? majorDim_ : minorDim_; } + + /** Number of rows. */ + inline int getNumRows() const + { return colOrdered_ ? minorDim_ : majorDim_; } + + /*! \brief A vector containing the elements in the packed matrix. + + Returns #elements_. Note that there might be gaps in this vector, + entries that do not belong to any major-dimension vector. To get + the actual elements one should look at this vector together with + vectorStarts (#start_) and vectorLengths (#length_). + */ + inline const double * getElements() const { return element_; } + + /*! \brief A vector containing the minor indices of the elements in + the packed matrix. + + Returns #index_. Note that there might be gaps in this list, + entries that do not belong to any major-dimension vector. To get + the actual elements one should look at this vector together with + vectorStarts (#start_) and vectorLengths (#length_). + */ + inline const int * getIndices() const { return index_; } + + /*! \brief The size of the <code>vectorStarts</code> array + + See #start_. + */ + inline int getSizeVectorStarts() const + { return ((majorDim_ > 0)?(majorDim_+1):(0)) ; } + + /*! \brief The size of the <code>vectorLengths</code> array + + See #length_. + */ + inline int getSizeVectorLengths() const { return majorDim_; } + + /*! \brief The positions where the major-dimension vectors start in + elements and indices. + + See #start_. + */ + inline const CoinBigIndex * getVectorStarts() const { return start_; } + + /*! \brief The lengths of the major-dimension vectors. + + See #length_. + */ + inline const int * getVectorLengths() const { return length_; } + + /** The position of the first element in the i'th major-dimension vector. + */ + CoinBigIndex getVectorFirst(const int i) const { +#ifndef COIN_FAST_CODE + if (i < 0 || i >= majorDim_) + throw CoinError("bad index", "vectorFirst", "CoinPackedMatrix"); +#endif + return start_[i]; + } + /** The position of the last element (well, one entry <em>past</em> the + last) in the i'th major-dimension vector. */ + CoinBigIndex getVectorLast(const int i) const { +#ifndef COIN_FAST_CODE + if (i < 0 || i >= majorDim_) + throw CoinError("bad index", "vectorLast", "CoinPackedMatrix"); +#endif + return start_[i] + length_[i]; + } + /** The length of i'th vector. */ + inline int getVectorSize(const int i) const { +#ifndef COIN_FAST_CODE + if (i < 0 || i >= majorDim_) + throw CoinError("bad index", "vectorSize", "CoinPackedMatrix"); +#endif + return length_[i]; + } +#ifndef CLP_NO_VECTOR + /** Return the i'th vector in matrix. */ + const CoinShallowPackedVector getVector(int i) const { +#ifndef COIN_FAST_CODE + if (i < 0 || i >= majorDim_) + throw CoinError("bad index", "vector", "CoinPackedMatrix"); +#endif + return CoinShallowPackedVector(length_[i], + index_ + start_[i], + element_ + start_[i], + false); + } +#endif + /** Returns an array containing major indices. The array is + getNumElements long and if getVectorStarts() is 0,2,5 then + the array would start 0,0,1,1,1,2... + This method is provided to go back from a packed format + to a triple format. It returns NULL if there are gaps in + matrix so user should use removeGaps() if there are any gaps. + It does this as this array has to match getElements() and + getIndices() and because it makes no sense otherwise. + The returned array is allocated with <code>new int[]</code>, + free it with <code>delete[]</code>. */ + int * getMajorIndices() const; + //@} + + //--------------------------------------------------------------------------- + /**@name Modifying members */ + //@{ + /*! \brief Set the dimensions of the matrix. + + The method name is deceptive; the effect is to append empty columns + and/or rows to the matrix to reach the specified dimensions. + A negative number for either dimension means that that dimension + doesn't change. An exception will be thrown if the specified dimensions + are smaller than the current dimensions. + */ + void setDimensions(int numrows, int numcols); + + /** Set the extra gap to be allocated to the specified value. */ + void setExtraGap(const double newGap); + /** Set the extra major to be allocated to the specified value. */ + void setExtraMajor(const double newMajor); +#ifndef CLP_NO_VECTOR + /*! Append a column to the end of the matrix. + + When compiled with COIN_DEBUG defined this method throws an exception + if the column vector specifies a nonexistent row index. Otherwise the + method assumes that every index fits into the matrix. + */ + void appendCol(const CoinPackedVectorBase& vec); +#endif + /*! Append a column to the end of the matrix. + + When compiled with COIN_DEBUG defined this method throws an exception + if the column vector specifies a nonexistent row index. Otherwise the + method assumes that every index fits into the matrix. + */ + void appendCol(const int vecsize, + const int *vecind, const double *vecelem); +#ifndef CLP_NO_VECTOR + /*! Append a set of columns to the end of the matrix. + + When compiled with COIN_DEBUG defined this method throws an exception + if any of the column vectors specify a nonexistent row index. Otherwise + the method assumes that every index fits into the matrix. + */ + void appendCols(const int numcols, + const CoinPackedVectorBase * const * cols); +#endif + /*! Append a set of columns to the end of the matrix. + + Returns the number of errors (nonexistent or duplicate row index). + No error checking is performed if \p numberRows < 0. + */ + int appendCols(const int numcols, + const CoinBigIndex * columnStarts, const int * row, + const double * element, int numberRows=-1); +#ifndef CLP_NO_VECTOR + /*! Append a row to the end of the matrix. + + When compiled with COIN_DEBUG defined this method throws an exception + if the row vector specifies a nonexistent column index. Otherwise the + method assumes that every index fits into the matrix. + */ + void appendRow(const CoinPackedVectorBase& vec); +#endif + /*! Append a row to the end of the matrix. + + When compiled with COIN_DEBUG defined this method throws an exception + if the row vector specifies a nonexistent column index. Otherwise the + method assumes that every index fits into the matrix. + */ + void appendRow(const int vecsize, + const int *vecind, const double *vecelem); +#ifndef CLP_NO_VECTOR + /*! Append a set of rows to the end of the matrix. + + When compiled with COIN_DEBUG defined this method throws an exception + if any of the row vectors specify a nonexistent column index. Otherwise + the method assumes that every index fits into the matrix. + */ + void appendRows(const int numrows, + const CoinPackedVectorBase * const * rows); +#endif + /*! Append a set of rows to the end of the matrix. + + Returns the number of errors (nonexistent or duplicate column index). + No error checking is performed if \p numberColumns < 0. + */ + int appendRows(const int numrows, + const CoinBigIndex * rowStarts, const int * column, + const double * element, int numberColumns=-1); + + /** Append the argument to the "right" of the current matrix. Imagine this + as adding new columns (don't worry about how the matrices are ordered, + that is taken care of). An exception is thrown if the number of rows + is different in the matrices. */ + void rightAppendPackedMatrix(const CoinPackedMatrix& matrix); + /** Append the argument to the "bottom" of the current matrix. Imagine this + as adding new rows (don't worry about how the matrices are ordered, + that is taken care of). An exception is thrown if the number of columns + is different in the matrices. */ + void bottomAppendPackedMatrix(const CoinPackedMatrix& matrix); + + /** Delete the columns whose indices are listed in <code>indDel</code>. */ + void deleteCols(const int numDel, const int * indDel); + /** Delete the rows whose indices are listed in <code>indDel</code>. */ + void deleteRows(const int numDel, const int * indDel); + + /** Replace the elements of a vector. The indices remain the same. + At most the number specified will be replaced. + The index is between 0 and major dimension of matrix */ + void replaceVector(const int index, + const int numReplace, const double * newElements); + /** Modify one element of packed matrix. An element may be added. + This works for either ordering + If the new element is zero it will be deleted unless + keepZero true */ + void modifyCoefficient(int row, int column, double newElement, + bool keepZero=false); + /** Return one element of packed matrix. + This works for either ordering + If it is not present will return 0.0 */ + double getCoefficient(int row, int column) const; + + /** Eliminate all elements in matrix whose + absolute value is less than threshold. + The column starts are not affected. Returns number of elements + eliminated. Elements eliminated are at end of each vector + */ + int compress(double threshold); + /** Eliminate all duplicate AND small elements in matrix + The column starts are not affected. Returns number of elements + eliminated. + */ + int eliminateDuplicates(double threshold); + /** Sort all columns so indices are increasing.in each column */ + void orderMatrix(); + /** Really clean up matrix. + a) eliminate all duplicate AND small elements in matrix + b) remove all gaps and set extraGap_ and extraMajor_ to 0.0 + c) reallocate arrays and make max lengths equal to lengths + d) orders elements + returns number of elements eliminated + */ + int cleanMatrix(double threshold=1.0e-20); + //@} + + //--------------------------------------------------------------------------- + /**@name Methods that reorganize the whole matrix */ + //@{ + /** Remove the gaps from the matrix if there were any + Can also remove small elements fabs() <= removeValue*/ + void removeGaps(double removeValue=-1.0); + + /** Extract a submatrix from matrix. Those major-dimension vectors of + the matrix comprise the submatrix whose indices are given in the + arguments. Does not allow duplicates. */ + void submatrixOf(const CoinPackedMatrix& matrix, + const int numMajor, const int * indMajor); + /** Extract a submatrix from matrix. Those major-dimension vectors of + the matrix comprise the submatrix whose indices are given in the + arguments. Allows duplicates and keeps order. */ + void submatrixOfWithDuplicates(const CoinPackedMatrix& matrix, + const int numMajor, const int * indMajor); +#if 0 + /** Extract a submatrix from matrix. Those major/minor-dimension vectors of + the matrix comprise the submatrix whose indices are given in the + arguments. */ + void submatrixOf(const CoinPackedMatrix& matrix, + const int numMajor, const int * indMajor, + const int numMinor, const int * indMinor); +#endif + + /** Copy method. This method makes an exact replica of the argument, + including the extra space parameters. */ + void copyOf(const CoinPackedMatrix& rhs); + /** Copy the arguments to the matrix. If <code>len</code> is a NULL pointer + then the matrix is assumed to have no gaps in it and <code>len</code> + will be created accordingly. */ + void copyOf(const bool colordered, + const int minor, const int major, const CoinBigIndex numels, + const double * elem, const int * ind, + const CoinBigIndex * start, const int * len, + const double extraMajor=0.0, const double extraGap=0.0); + /** Copy method. This method makes an exact replica of the argument, + including the extra space parameters. + If there is room it will re-use arrays */ + void copyReuseArrays(const CoinPackedMatrix& rhs); + + /*! \brief Make a reverse-ordered copy. + + This method makes an exact replica of the argument with the major + vector orientation changed from row (column) to column (row). + The extra space parameters are also copied and reversed. + (Cf. #reverseOrdering, which does the same thing in place.) + */ + void reverseOrderedCopyOf(const CoinPackedMatrix& rhs); + + /** Assign the arguments to the matrix. If <code>len</code> is a NULL + pointer then the matrix is assumed to have no gaps in it and + <code>len</code> will be created accordingly. <br> + <strong>NOTE 1</strong>: After this method returns the pointers + passed to the method will be NULL pointers! <br> + <strong>NOTE 2</strong>: When the matrix is eventually destructed the + arrays will be deleted by <code>delete[]</code>. Hence one should use + this method ONLY if all array swere allocated by <code>new[]</code>! */ + void assignMatrix(const bool colordered, + const int minor, const int major, + const CoinBigIndex numels, + double *& elem, int *& ind, + CoinBigIndex *& start, int *& len, + const int maxmajor = -1, const CoinBigIndex maxsize = -1); + + + + /** Assignment operator. This copies out the data, but uses the current + matrix's extra space parameters. */ + CoinPackedMatrix & operator=(const CoinPackedMatrix& rhs); + + /*! \brief Reverse the ordering of the packed matrix. + + Change the major vector orientation of the matrix data structures from + row (column) to column (row). (Cf. #reverseOrderedCopyOf, which does + the same thing but produces a new matrix.) + */ + void reverseOrdering(); + + /*! \brief Transpose the matrix. + + \note + If you start with a column-ordered matrix and invoke transpose, you + will have a row-ordered transposed matrix. To change the major vector + orientation (e.g., to transform a column-ordered matrix to a + column-ordered transposed matrix), invoke transpose() followed by + #reverseOrdering(). + */ + void transpose(); + + /*! \brief Swap the content of two packed matrices. */ + void swap(CoinPackedMatrix& matrix); + + //@} + + //--------------------------------------------------------------------------- + /**@name Matrix times vector methods */ + //@{ + /** Return <code>A * x</code> in <code>y</code>. + @pre <code>x</code> must be of size <code>numColumns()</code> + @pre <code>y</code> must be of size <code>numRows()</code> */ + void times(const double * x, double * y) const; +#ifndef CLP_NO_VECTOR + /** Return <code>A * x</code> in <code>y</code>. Same as the previous + method, just <code>x</code> is given in the form of a packed vector. */ + void times(const CoinPackedVectorBase& x, double * y) const; +#endif + /** Return <code>x * A</code> in <code>y</code>. + @pre <code>x</code> must be of size <code>numRows()</code> + @pre <code>y</code> must be of size <code>numColumns()</code> */ + void transposeTimes(const double * x, double * y) const; +#ifndef CLP_NO_VECTOR + /** Return <code>x * A</code> in <code>y</code>. Same as the previous + method, just <code>x</code> is given in the form of a packed vector. */ + void transposeTimes(const CoinPackedVectorBase& x, double * y) const; +#endif + //@} + + //--------------------------------------------------------------------------- + /**@name Helper functions used internally, but maybe useful externally. + + These methods do not worry about testing whether the packed matrix is + row or column major ordered; they operate under the assumption that the + correct version is invoked. In fact, a number of other methods simply + just call one of these after testing the ordering of the matrix. */ + //@{ + + //------------------------------------------------------------------------- + /**@name Queries */ + //@{ + /** Count the number of entries in every minor-dimension vector and + return an array containing these lengths. The returned array is + allocated with <code>new int[]</code>, free it with + <code>delete[]</code>. */ + int * countOrthoLength() const; + /** Count the number of entries in every minor-dimension vector and + fill in an array containing these lengths. */ + void countOrthoLength(int * counts) const; + /** Major dimension. For row ordered matrix this would be the number of + rows. */ + inline int getMajorDim() const { return majorDim_; } + /** Set major dimension. For row ordered matrix this would be the number of + rows. Use with great care.*/ + inline void setMajorDim(int value) { majorDim_ = value; } + /** Minor dimension. For row ordered matrix this would be the number of + columns. */ + inline int getMinorDim() const { return minorDim_; } + /** Set minor dimension. For row ordered matrix this would be the number of + columns. Use with great care.*/ + inline void setMinorDim(int value) { minorDim_ = value; } + /** Current maximum for major dimension. For row ordered matrix this many + rows can be added without reallocating the vector related to the + major dimension (<code>start_</code> and <code>length_</code>). */ + inline int getMaxMajorDim() const { return maxMajorDim_; } + + /** Dump the matrix on stdout. When in dire straits this method can + help. */ + void dumpMatrix(const char* fname = NULL) const; + + /// Print a single matrix element. + void printMatrixElement(const int row_val, const int col_val) const; + //@} + + //------------------------------------------------------------------------- + /*! @name Append vectors + + \details + When compiled with COIN_DEBUG defined these methods throw an exception + if the major (minor) vector contains an index that's invalid for the + minor (major) dimension. Otherwise the methods assume that every index + fits into the matrix. + */ + //@{ +#ifndef CLP_NO_VECTOR + /** Append a major-dimension vector to the end of the matrix. */ + void appendMajorVector(const CoinPackedVectorBase& vec); +#endif + /** Append a major-dimension vector to the end of the matrix. */ + void appendMajorVector(const int vecsize, const int *vecind, + const double *vecelem); +#ifndef CLP_NO_VECTOR + /** Append several major-dimensonvectors to the end of the matrix */ + void appendMajorVectors(const int numvecs, + const CoinPackedVectorBase * const * vecs); + + /** Append a minor-dimension vector to the end of the matrix. */ + void appendMinorVector(const CoinPackedVectorBase& vec); +#endif + /** Append a minor-dimension vector to the end of the matrix. */ + void appendMinorVector(const int vecsize, const int *vecind, + const double *vecelem); +#ifndef CLP_NO_VECTOR + /** Append several minor-dimension vectors to the end of the matrix */ + void appendMinorVectors(const int numvecs, + const CoinPackedVectorBase * const * vecs); +#endif + /*! \brief Append a set of rows (columns) to the end of a column (row) + ordered matrix. + + This case is when we know there are no gaps and majorDim_ will not + change. + + \todo + This method really belongs in the group of protected methods with + #appendMinor; there are no safeties here even with COIN_DEBUG. + Apparently this method was needed in ClpPackedMatrix and giving it + proper visibility was too much trouble. Should be moved. + */ + void appendMinorFast(const int number, + const CoinBigIndex * starts, const int * index, + const double * element); + //@} + + //------------------------------------------------------------------------- + /*! \name Append matrices + + \details + We'll document these methods assuming that the current matrix is + column major ordered (Hence in the <code>...SameOrdered()</code> + methods the argument is column ordered, in the + <code>OrthoOrdered()</code> methods the argument is row ordered.) + */ + //@{ + /** Append the columns of the argument to the right end of this matrix. + @pre <code>minorDim_ == matrix.minorDim_</code> <br> + This method throws an exception if the minor dimensions are not the + same. */ + void majorAppendSameOrdered(const CoinPackedMatrix& matrix); + /** Append the columns of the argument to the bottom end of this matrix. + @pre <code>majorDim_ == matrix.majorDim_</code> <br> + This method throws an exception if the major dimensions are not the + same. */ + void minorAppendSameOrdered(const CoinPackedMatrix& matrix); + /** Append the rows of the argument to the right end of this matrix. + @pre <code>minorDim_ == matrix.majorDim_</code> <br> + This method throws an exception if the minor dimension of the + current matrix is not the same as the major dimension of the + argument matrix. */ + void majorAppendOrthoOrdered(const CoinPackedMatrix& matrix); + /** Append the rows of the argument to the bottom end of this matrix. + @pre <code>majorDim_ == matrix.minorDim_</code> <br> + This method throws an exception if the major dimension of the + current matrix is not the same as the minor dimension of the + argument matrix. */ + void minorAppendOrthoOrdered(const CoinPackedMatrix& matrix); + //@} + + //----------------------------------------------------------------------- + /**@name Delete vectors */ + //@{ + /** Delete the major-dimension vectors whose indices are listed in + <code>indDel</code>. */ + void deleteMajorVectors(const int numDel, const int * indDel); + /** Delete the minor-dimension vectors whose indices are listed in + <code>indDel</code>. */ + void deleteMinorVectors(const int numDel, const int * indDel); + //@} + + //----------------------------------------------------------------------- + /**@name Various dot products. */ + //@{ + /** Return <code>A * x</code> (multiplied from the "right" direction) in + <code>y</code>. + @pre <code>x</code> must be of size <code>majorDim()</code> + @pre <code>y</code> must be of size <code>minorDim()</code> */ + void timesMajor(const double * x, double * y) const; +#ifndef CLP_NO_VECTOR + /** Return <code>A * x</code> (multiplied from the "right" direction) in + <code>y</code>. Same as the previous method, just <code>x</code> is + given in the form of a packed vector. */ + void timesMajor(const CoinPackedVectorBase& x, double * y) const; +#endif + /** Return <code>A * x</code> (multiplied from the "right" direction) in + <code>y</code>. + @pre <code>x</code> must be of size <code>minorDim()</code> + @pre <code>y</code> must be of size <code>majorDim()</code> */ + void timesMinor(const double * x, double * y) const; +#ifndef CLP_NO_VECTOR + /** Return <code>A * x</code> (multiplied from the "right" direction) in + <code>y</code>. Same as the previous method, just <code>x</code> is + given in the form of a packed vector. */ + void timesMinor(const CoinPackedVectorBase& x, double * y) const; +#endif + //@} + //@} + + //-------------------------------------------------------------------------- + /**@name Logical Operations. */ + //@{ +#ifndef CLP_NO_VECTOR + /*! \brief Test for equivalence. + + Two matrices are equivalent if they are both row- or column-ordered, + they have the same dimensions, and each (major) vector is equivalent. + The operator used to test for equality can be specified using the + \p FloatEqual template parameter. + */ + template <class FloatEqual> bool + isEquivalent(const CoinPackedMatrix& rhs, const FloatEqual& eq) const + { + // Both must be column order or both row ordered and must be of same size + if ((isColOrdered() ^ rhs.isColOrdered()) || + (getNumCols() != rhs.getNumCols()) || + (getNumRows() != rhs.getNumRows()) || + (getNumElements() != rhs.getNumElements())) + return false; + + for (int i=getMajorDim()-1; i >= 0; --i) { + CoinShallowPackedVector pv = getVector(i); + CoinShallowPackedVector rhsPv = rhs.getVector(i); + if ( !pv.isEquivalent(rhsPv,eq) ) + return false; + } + return true; + } + + /*! \brief Test for equivalence and report differences + + Equivalence is defined as for #isEquivalent. In addition, this method will + print differences to std::cerr. Intended for use in unit tests and + for debugging. + */ + bool isEquivalent2(const CoinPackedMatrix& rhs) const; +#else + /*! \brief Test for equivalence. + + Two matrices are equivalent if they are both row- or column-ordered, + they have the same dimensions, and each (major) vector is equivalent. + This method is optimised for speed. CoinPackedVector#isEquivalent is + replaced with more efficient code for repeated comparison of + equal-length vectors. The CoinRelFltEq operator is used. + */ + bool isEquivalent(const CoinPackedMatrix& rhs, const CoinRelFltEq & eq) const; +#endif + /*! \brief Test for equivalence. + + The test for element equality is the default CoinRelFltEq operator. + */ + bool isEquivalent(const CoinPackedMatrix& rhs) const; + //@} + + //-------------------------------------------------------------------------- + /*! \name Non-const methods + + These are to be used with great care when doing column generation, etc. + */ + //@{ + /** A vector containing the elements in the packed matrix. Note that there + might be gaps in this list, entries that do not belong to any + major-dimension vector. To get the actual elements one should look at + this vector together with #start_ and #length_. */ + inline double * getMutableElements() const { return element_; } + /** A vector containing the minor indices of the elements in the packed + matrix. Note that there might be gaps in this list, entries that do not + belong to any major-dimension vector. To get the actual elements one + should look at this vector together with #start_ and + #length_. */ + inline int * getMutableIndices() const { return index_; } + + /** The positions where the major-dimension vectors start in #element_ and + #index_. */ + inline CoinBigIndex * getMutableVectorStarts() const { return start_; } + /** The lengths of the major-dimension vectors. */ + inline int * getMutableVectorLengths() const { return length_; } + /// Change the size of the bulk store after modifying - be careful + inline void setNumElements(CoinBigIndex value) + { size_ = value;} + /*! NULLify element array + + Used when space is very tight. Does not free the space! + */ + inline void nullElementArray() {element_=NULL;} + + /*! NULLify start array + + Used when space is very tight. Does not free the space! + */ + inline void nullStartArray() {start_=NULL;} + + /*! NULLify length array + + Used when space is very tight. Does not free the space! + */ + inline void nullLengthArray() {length_=NULL;} + + /*! NULLify index array + + Used when space is very tight. Does not free the space! + */ + inline void nullIndexArray() {index_=NULL;} + //@} + + //-------------------------------------------------------------------------- + /*! \name Constructors and destructors */ + //@{ + /// Default Constructor creates an empty column ordered packed matrix + CoinPackedMatrix(); + + /// A constructor where the ordering and the gaps are specified + CoinPackedMatrix(const bool colordered, + const double extraMajor, const double extraGap); + + CoinPackedMatrix(const bool colordered, + const int minor, const int major, const CoinBigIndex numels, + const double * elem, const int * ind, + const CoinBigIndex * start, const int * len, + const double extraMajor, const double extraGap); + + CoinPackedMatrix(const bool colordered, + const int minor, const int major, const CoinBigIndex numels, + const double * elem, const int * ind, + const CoinBigIndex * start, const int * len); + + /** Create packed matrix from triples. + If colordered is true then the created matrix will be column ordered. + Duplicate matrix elements are allowed. The created matrix will have + the sum of the duplicates. <br> + For example if: <br> + rowIndices[0]=2; colIndices[0]=5; elements[0]=2.0 <br> + rowIndices[1]=2; colIndices[1]=5; elements[1]=0.5 <br> + then the created matrix will contain a value of 2.5 in row 2 and column 5.<br> + The matrix is created without gaps. + */ + CoinPackedMatrix(const bool colordered, + const int * rowIndices, + const int * colIndices, + const double * elements, + CoinBigIndex numels ); + + /// Copy constructor + CoinPackedMatrix(const CoinPackedMatrix& m); + + /*! \brief Copy constructor with fine tuning + + This constructor allows for the specification of an exact amount of extra + space and/or reverse ordering. + + \p extraForMajor is the exact number of spare major vector slots after + any possible reverse ordering. If \p extraForMajor < 0, all gaps and small + elements will be removed from the copy, otherwise gaps and small elements + are preserved. + + \p extraElements is the exact number of spare element entries. + + The usual multipliers, #extraMajor_ and #extraGap_, are set to zero. + */ + CoinPackedMatrix(const CoinPackedMatrix &m, + int extraForMajor, int extraElements, + bool reverseOrdering = false) ; + + /** Subset constructor (without gaps). Duplicates are allowed + and order is as given */ + CoinPackedMatrix (const CoinPackedMatrix & wholeModel, + int numberRows, const int * whichRows, + int numberColumns, const int * whichColumns); + + /// Destructor + virtual ~CoinPackedMatrix(); + //@} + + /*! \name Debug Utilities */ + //@{ + /*! \brief Scan the matrix for anomalies. + + Returns the number of anomalies. Scans the structure for gaps, + obviously bogus indices and coefficients, and inconsistencies. Gaps + are not an error unless #hasGaps() says the matrix should be + gap-free. Zeroes are not an error unless \p zeroesAreError is set to + true. + + Values for verbosity are: + - 0: No messages, just the return value + - 1: Messages about errors + - 2: If there are no errors, a message indicating the matrix was + checked is printed (positive confirmation). + - 3: Adds a bit more information about the matrix. + - 4: Prints warnings about zeroes even if they're not considered + errors. + + Obviously bogus coefficients are coefficients that are NaN or have + absolute value greater than 1e50. Zeros have absolute value less + than 1e-50. + */ + int verifyMtx(int verbosity = 1, bool zeroesAreError = false) const ; + //@} + + //-------------------------------------------------------------------------- +protected: + void gutsOfDestructor(); + void gutsOfCopyOf(const bool colordered, + const int minor, const int major, const CoinBigIndex numels, + const double * elem, const int * ind, + const CoinBigIndex * start, const int * len, + const double extraMajor=0.0, const double extraGap=0.0); + /// When no gaps we can do faster + void gutsOfCopyOfNoGaps(const bool colordered, + const int minor, const int major, + const double * elem, const int * ind, + const CoinBigIndex * start); + void gutsOfOpEqual(const bool colordered, + const int minor, const int major, const CoinBigIndex numels, + const double * elem, const int * ind, + const CoinBigIndex * start, const int * len); + void resizeForAddingMajorVectors(const int numVec, const int * lengthVec); + void resizeForAddingMinorVectors(const int * addedEntries); + + /*! \brief Append a set of rows (columns) to the end of a row (colum) + ordered matrix. + + If \p numberOther > 0 the method will check if any of the new rows + (columns) contain duplicate indices or invalid indices and return the + number of errors. A valid minor index must satisfy + \code 0 <= k < numberOther \endcode + If \p numberOther < 0 no checking is performed. + */ + int appendMajor(const int number, + const CoinBigIndex * starts, const int * index, + const double * element, int numberOther=-1); + /*! \brief Append a set of rows (columns) to the end of a column (row) + ordered matrix. + + If \p numberOther > 0 the method will check if any of the new rows + (columns) contain duplicate indices or indices outside the current + range for the major dimension and return the number of violations. + If \p numberOther <= 0 the major dimension will be expanded as + necessary and there are no checks for duplicate indices. + */ + int appendMinor(const int number, + const CoinBigIndex * starts, const int * index, + const double * element, int numberOther=-1); + +private: + inline CoinBigIndex getLastStart() const { + return majorDim_ == 0 ? 0 : start_[majorDim_]; + } + + //-------------------------------------------------------------------------- +protected: + /**@name Data members + The data members are protected to allow access for derived classes. */ + //@{ + /** A flag indicating whether the matrix is column or row major ordered. */ + bool colOrdered_; + /** This much times more space should be allocated for each major-dimension + vector (with respect to the number of entries in the vector) when the + matrix is resized. The purpose of these gaps is to allow fast insertion + of new minor-dimension vectors. */ + double extraGap_; + /** his much times more space should be allocated for major-dimension + vectors when the matrix is resized. The purpose of these gaps is to + allow fast addition of new major-dimension vectors. */ + double extraMajor_; + + /** List of nonzero element values. The entries in the gaps between + major-dimension vectors are undefined. */ + double *element_; + /** List of nonzero element minor-dimension indices. The entries in the gaps + between major-dimension vectors are undefined. */ + int *index_; + /** Starting positions of major-dimension vectors. */ + CoinBigIndex *start_; + /** Lengths of major-dimension vectors. */ + int *length_; + + /// number of vectors in matrix + int majorDim_; + /// size of other dimension + int minorDim_; + /// the number of nonzero entries + CoinBigIndex size_; + + /// max space allocated for major-dimension + int maxMajorDim_; + /// max space allocated for entries + CoinBigIndex maxSize_; + //@} +}; + +//############################################################################# +/*! \brief Test the methods in the CoinPackedMatrix class. + + The only reason for it not to be a member method is that this way + it doesn't have to be compiled into the library. And that's a gain, + because the library should be compiled with optimization on, but this + method should be compiled with debugging. +*/ +void +CoinPackedMatrixUnitTest(); + +#endif |