1/* $Id: CoinPackedMatrix.hpp 1505 2011-11-20 16:00:54Z forrest $ */
2// Copyright (C) 2000, International Business Machines
3// Corporation and others. All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#ifndef CoinPackedMatrix_H
7#define CoinPackedMatrix_H
8
9#include "CoinError.hpp"
10#include "CoinTypes.hpp"
11#ifndef CLP_NO_VECTOR
12#include "CoinPackedVectorBase.hpp"
13#include "CoinShallowPackedVector.hpp"
14#else
15class CoinRelFltEq;
16#endif
17
18/** Sparse Matrix Base Class
19
20 This class is intended to represent sparse matrices using row-major
21 or column-major ordering. The representation is very efficient for
22 adding, deleting, or retrieving major-dimension vectors. Adding
23 a minor-dimension vector is less efficient, but can be helped by
24 providing "extra" space as described in the next paragraph. Deleting
25 a minor-dimension vector requires inspecting all coefficients in the
26 matrix. Retrieving a minor-dimension vector would incur the same cost
27 and is not supported (except in the sense that you can write a loop to
28 retrieve all coefficients one at a time). Consider physically transposing
29 the matrix, or keeping a second copy with the other major-vector ordering.
30
31 The sparse represention can be completely compact or it can have "extra"
32 space available at the end of each major vector. Incorporating extra
33 space into the sparse matrix representation can improve performance in
34 cases where new data needs to be inserted into the packed matrix against
35 the major-vector orientation (e.g, inserting a row into a matrix stored
36 in column-major order).
37
38 For example if the matrix:
39 @verbatim
40 3 1 0 -2 -1 0 0 -1
41 0 2 1.1 0 0 0 0 0
42 0 0 1 0 0 1 0 0
43 0 0 0 2.8 0 0 -1.2 0
44 5.6 0 0 0 1 0 0 1.9
45
46 was stored by rows (with no extra space) in
47 CoinPackedMatrix r then:
48 r.getElements() returns a vector containing:
49 3 1 -2 -1 -1 2 1.1 1 1 2.8 -1.2 5.6 1 1.9
50 r.getIndices() returns a vector containing:
51 0 1 3 4 7 1 2 2 5 3 6 0 4 7
52 r.getVectorStarts() returns a vector containing:
53 0 5 7 9 11 14
54 r.getNumElements() returns 14.
55 r.getMajorDim() returns 5.
56 r.getVectorSize(0) returns 5.
57 r.getVectorSize(1) returns 2.
58 r.getVectorSize(2) returns 2.
59 r.getVectorSize(3) returns 2.
60 r.getVectorSize(4) returns 3.
61
62 If stored by columns (with no extra space) then:
63 c.getElements() returns a vector containing:
64 3 5.6 1 2 1.1 1 -2 2.8 -1 1 1 -1.2 -1 1.9
65 c.getIndices() returns a vector containing:
66 0 4 0 1 1 2 0 3 0 4 2 3 0 4
67 c.getVectorStarts() returns a vector containing:
68 0 2 4 6 8 10 11 12 14
69 c.getNumElements() returns 14.
70 c.getMajorDim() returns 8.
71 @endverbatim
72
73 Compiling this class with CLP_NO_VECTOR defined will excise all methods
74 which use CoinPackedVectorBase, CoinPackedVector, or CoinShallowPackedVector
75 as parameters or return types.
76
77 Compiling this class with COIN_FAST_CODE defined removes index range checks.
78*/
79class CoinPackedMatrix {
80 friend void CoinPackedMatrixUnitTest();
81
82public:
83
84
85 //---------------------------------------------------------------------------
86 /**@name Query members */
87 //@{
88 /** Return the current setting of the extra gap. */
89 inline double getExtraGap() const { return extraGap_; }
90 /** Return the current setting of the extra major. */
91 inline double getExtraMajor() const { return extraMajor_; }
92
93 /** Reserve sufficient space for appending major-ordered vectors.
94 If create is true, empty columns are created (for column generation) */
95 void reserve(const int newMaxMajorDim, const CoinBigIndex newMaxSize,
96 bool create=false);
97 /** Clear the data, but do not free any arrays */
98 void clear();
99
100 /** Whether the packed matrix is column major ordered or not. */
101 inline bool isColOrdered() const { return colOrdered_; }
102
103 /** Whether the packed matrix has gaps or not. */
104 inline bool hasGaps() const { return (size_<start_[majorDim_]) ; }
105
106 /** Number of entries in the packed matrix. */
107 inline CoinBigIndex getNumElements() const { return size_; }
108
109 /** Number of columns. */
110 inline int getNumCols() const
111 { return colOrdered_ ? majorDim_ : minorDim_; }
112
113 /** Number of rows. */
114 inline int getNumRows() const
115 { return colOrdered_ ? minorDim_ : majorDim_; }
116
117 /*! \brief A vector containing the elements in the packed matrix.
118
119 Returns #elements_. Note that there might be gaps in this vector,
120 entries that do not belong to any major-dimension vector. To get
121 the actual elements one should look at this vector together with
122 vectorStarts (#start_) and vectorLengths (#length_).
123 */
124 inline const double * getElements() const { return element_; }
125
126 /*! \brief A vector containing the minor indices of the elements in
127 the packed matrix.
128
129 Returns #index_. Note that there might be gaps in this list,
130 entries that do not belong to any major-dimension vector. To get
131 the actual elements one should look at this vector together with
132 vectorStarts (#start_) and vectorLengths (#length_).
133 */
134 inline const int * getIndices() const { return index_; }
135
136 /*! \brief The size of the <code>vectorStarts</code> array
137
138 See #start_.
139 */
140 inline int getSizeVectorStarts() const
141 { return ((majorDim_ > 0)?(majorDim_+1):(0)) ; }
142
143 /*! \brief The size of the <code>vectorLengths</code> array
144
145 See #length_.
146 */
147 inline int getSizeVectorLengths() const { return majorDim_; }
148
149 /*! \brief The positions where the major-dimension vectors start in
150 elements and indices.
151
152 See #start_.
153 */
154 inline const CoinBigIndex * getVectorStarts() const { return start_; }
155
156 /*! \brief The lengths of the major-dimension vectors.
157
158 See #length_.
159 */
160 inline const int * getVectorLengths() const { return length_; }
161
162 /** The position of the first element in the i'th major-dimension vector.
163 */
164 CoinBigIndex getVectorFirst(const int i) const {
165#ifndef COIN_FAST_CODE
166 if (i < 0 || i >= majorDim_)
167 throw CoinError("bad index", "vectorFirst", "CoinPackedMatrix");
168#endif
169 return start_[i];
170 }
171 /** The position of the last element (well, one entry <em>past</em> the
172 last) in the i'th major-dimension vector. */
173 CoinBigIndex getVectorLast(const int i) const {
174#ifndef COIN_FAST_CODE
175 if (i < 0 || i >= majorDim_)
176 throw CoinError("bad index", "vectorLast", "CoinPackedMatrix");
177#endif
178 return start_[i] + length_[i];
179 }
180 /** The length of i'th vector. */
181 inline int getVectorSize(const int i) const {
182#ifndef COIN_FAST_CODE
183 if (i < 0 || i >= majorDim_)
184 throw CoinError("bad index", "vectorSize", "CoinPackedMatrix");
185#endif
186 return length_[i];
187 }
188#ifndef CLP_NO_VECTOR
189 /** Return the i'th vector in matrix. */
190 const CoinShallowPackedVector getVector(int i) const {
191#ifndef COIN_FAST_CODE
192 if (i < 0 || i >= majorDim_)
193 throw CoinError("bad index", "vector", "CoinPackedMatrix");
194#endif
195 return CoinShallowPackedVector(length_[i],
196 index_ + start_[i],
197 element_ + start_[i],
198 false);
199 }
200#endif
201 /** Returns an array containing major indices. The array is
202 getNumElements long and if getVectorStarts() is 0,2,5 then
203 the array would start 0,0,1,1,1,2...
204 This method is provided to go back from a packed format
205 to a triple format. It returns NULL if there are gaps in
206 matrix so user should use removeGaps() if there are any gaps.
207 It does this as this array has to match getElements() and
208 getIndices() and because it makes no sense otherwise.
209 The returned array is allocated with <code>new int[]</code>,
210 free it with <code>delete[]</code>. */
211 int * getMajorIndices() const;
212 //@}
213
214 //---------------------------------------------------------------------------
215 /**@name Modifying members */
216 //@{
217 /*! \brief Set the dimensions of the matrix.
218
219 The method name is deceptive; the effect is to append empty columns
220 and/or rows to the matrix to reach the specified dimensions.
221 A negative number for either dimension means that that dimension
222 doesn't change. An exception will be thrown if the specified dimensions
223 are smaller than the current dimensions.
224 */
225 void setDimensions(int numrows, int numcols);
226
227 /** Set the extra gap to be allocated to the specified value. */
228 void setExtraGap(const double newGap);
229 /** Set the extra major to be allocated to the specified value. */
230 void setExtraMajor(const double newMajor);
231#ifndef CLP_NO_VECTOR
232 /*! Append a column to the end of the matrix.
233
234 When compiled with COIN_DEBUG defined this method throws an exception
235 if the column vector specifies a nonexistent row index. Otherwise the
236 method assumes that every index fits into the matrix.
237 */
238 void appendCol(const CoinPackedVectorBase& vec);
239#endif
240 /*! Append a column to the end of the matrix.
241
242 When compiled with COIN_DEBUG defined this method throws an exception
243 if the column vector specifies a nonexistent row index. Otherwise the
244 method assumes that every index fits into the matrix.
245 */
246 void appendCol(const int vecsize,
247 const int *vecind, const double *vecelem);
248#ifndef CLP_NO_VECTOR
249 /*! Append a set of columns to the end of the matrix.
250
251 When compiled with COIN_DEBUG defined this method throws an exception
252 if any of the column vectors specify a nonexistent row index. Otherwise
253 the method assumes that every index fits into the matrix.
254 */
255 void appendCols(const int numcols,
256 const CoinPackedVectorBase * const * cols);
257#endif
258 /*! Append a set of columns to the end of the matrix.
259
260 Returns the number of errors (nonexistent or duplicate row index).
261 No error checking is performed if \p numberRows < 0.
262 */
263 int appendCols(const int numcols,
264 const CoinBigIndex * columnStarts, const int * row,
265 const double * element, int numberRows=-1);
266#ifndef CLP_NO_VECTOR
267 /*! Append a row to the end of the matrix.
268
269 When compiled with COIN_DEBUG defined this method throws an exception
270 if the row vector specifies a nonexistent column index. Otherwise the
271 method assumes that every index fits into the matrix.
272 */
273 void appendRow(const CoinPackedVectorBase& vec);
274#endif
275 /*! Append a row to the end of the matrix.
276
277 When compiled with COIN_DEBUG defined this method throws an exception
278 if the row vector specifies a nonexistent column index. Otherwise the
279 method assumes that every index fits into the matrix.
280 */
281 void appendRow(const int vecsize,
282 const int *vecind, const double *vecelem);
283#ifndef CLP_NO_VECTOR
284 /*! Append a set of rows to the end of the matrix.
285
286 When compiled with COIN_DEBUG defined this method throws an exception
287 if any of the row vectors specify a nonexistent column index. Otherwise
288 the method assumes that every index fits into the matrix.
289 */
290 void appendRows(const int numrows,
291 const CoinPackedVectorBase * const * rows);
292#endif
293 /*! Append a set of rows to the end of the matrix.
294
295 Returns the number of errors (nonexistent or duplicate column index).
296 No error checking is performed if \p numberColumns < 0.
297 */
298 int appendRows(const int numrows,
299 const CoinBigIndex * rowStarts, const int * column,
300 const double * element, int numberColumns=-1);
301
302 /** Append the argument to the "right" of the current matrix. Imagine this
303 as adding new columns (don't worry about how the matrices are ordered,
304 that is taken care of). An exception is thrown if the number of rows
305 is different in the matrices. */
306 void rightAppendPackedMatrix(const CoinPackedMatrix& matrix);
307 /** Append the argument to the "bottom" of the current matrix. Imagine this
308 as adding new rows (don't worry about how the matrices are ordered,
309 that is taken care of). An exception is thrown if the number of columns
310 is different in the matrices. */
311 void bottomAppendPackedMatrix(const CoinPackedMatrix& matrix);
312
313 /** Delete the columns whose indices are listed in <code>indDel</code>. */
314 void deleteCols(const int numDel, const int * indDel);
315 /** Delete the rows whose indices are listed in <code>indDel</code>. */
316 void deleteRows(const int numDel, const int * indDel);
317
318 /** Replace the elements of a vector. The indices remain the same.
319 At most the number specified will be replaced.
320 The index is between 0 and major dimension of matrix */
321 void replaceVector(const int index,
322 const int numReplace, const double * newElements);
323 /** Modify one element of packed matrix. An element may be added.
324 This works for either ordering
325 If the new element is zero it will be deleted unless
326 keepZero true */
327 void modifyCoefficient(int row, int column, double newElement,
328 bool keepZero=false);
329 /** Return one element of packed matrix.
330 This works for either ordering
331 If it is not present will return 0.0 */
332 double getCoefficient(int row, int column) const;
333
334 /** Eliminate all elements in matrix whose
335 absolute value is less than threshold.
336 The column starts are not affected. Returns number of elements
337 eliminated. Elements eliminated are at end of each vector
338 */
339 int compress(double threshold);
340 /** Eliminate all duplicate AND small elements in matrix
341 The column starts are not affected. Returns number of elements
342 eliminated.
343 */
344 int eliminateDuplicates(double threshold);
345 /** Sort all columns so indices are increasing.in each column */
346 void orderMatrix();
347 /** Really clean up matrix.
348 a) eliminate all duplicate AND small elements in matrix
349 b) remove all gaps and set extraGap_ and extraMajor_ to 0.0
350 c) reallocate arrays and make max lengths equal to lengths
351 d) orders elements
352 returns number of elements eliminated
353 */
354 int cleanMatrix(double threshold=1.0e-20);
355 //@}
356
357 //---------------------------------------------------------------------------
358 /**@name Methods that reorganize the whole matrix */
359 //@{
360 /** Remove the gaps from the matrix if there were any
361 Can also remove small elements fabs() <= removeValue*/
362 void removeGaps(double removeValue=-1.0);
363
364 /** Extract a submatrix from matrix. Those major-dimension vectors of
365 the matrix comprise the submatrix whose indices are given in the
366 arguments. Does not allow duplicates. */
367 void submatrixOf(const CoinPackedMatrix& matrix,
368 const int numMajor, const int * indMajor);
369 /** Extract a submatrix from matrix. Those major-dimension vectors of
370 the matrix comprise the submatrix whose indices are given in the
371 arguments. Allows duplicates and keeps order. */
372 void submatrixOfWithDuplicates(const CoinPackedMatrix& matrix,
373 const int numMajor, const int * indMajor);
374#if 0
375 /** Extract a submatrix from matrix. Those major/minor-dimension vectors of
376 the matrix comprise the submatrix whose indices are given in the
377 arguments. */
378 void submatrixOf(const CoinPackedMatrix& matrix,
379 const int numMajor, const int * indMajor,
380 const int numMinor, const int * indMinor);
381#endif
382
383 /** Copy method. This method makes an exact replica of the argument,
384 including the extra space parameters. */
385 void copyOf(const CoinPackedMatrix& rhs);
386 /** Copy the arguments to the matrix. If <code>len</code> is a NULL pointer
387 then the matrix is assumed to have no gaps in it and <code>len</code>
388 will be created accordingly. */
389 void copyOf(const bool colordered,
390 const int minor, const int major, const CoinBigIndex numels,
391 const double * elem, const int * ind,
392 const CoinBigIndex * start, const int * len,
393 const double extraMajor=0.0, const double extraGap=0.0);
394 /** Copy method. This method makes an exact replica of the argument,
395 including the extra space parameters.
396 If there is room it will re-use arrays */
397 void copyReuseArrays(const CoinPackedMatrix& rhs);
398
399 /*! \brief Make a reverse-ordered copy.
400
401 This method makes an exact replica of the argument with the major
402 vector orientation changed from row (column) to column (row).
403 The extra space parameters are also copied and reversed.
404 (Cf. #reverseOrdering, which does the same thing in place.)
405 */
406 void reverseOrderedCopyOf(const CoinPackedMatrix& rhs);
407
408 /** Assign the arguments to the matrix. If <code>len</code> is a NULL
409 pointer then the matrix is assumed to have no gaps in it and
410 <code>len</code> will be created accordingly. <br>
411 <strong>NOTE 1</strong>: After this method returns the pointers
412 passed to the method will be NULL pointers! <br>
413 <strong>NOTE 2</strong>: When the matrix is eventually destructed the
414 arrays will be deleted by <code>delete[]</code>. Hence one should use
415 this method ONLY if all array swere allocated by <code>new[]</code>! */
416 void assignMatrix(const bool colordered,
417 const int minor, const int major,
418 const CoinBigIndex numels,
419 double *& elem, int *& ind,
420 CoinBigIndex *& start, int *& len,
421 const int maxmajor = -1, const CoinBigIndex maxsize = -1);
422
423
424
425 /** Assignment operator. This copies out the data, but uses the current
426 matrix's extra space parameters. */
427 CoinPackedMatrix & operator=(const CoinPackedMatrix& rhs);
428
429 /*! \brief Reverse the ordering of the packed matrix.
430
431 Change the major vector orientation of the matrix data structures from
432 row (column) to column (row). (Cf. #reverseOrderedCopyOf, which does
433 the same thing but produces a new matrix.)
434 */
435 void reverseOrdering();
436
437 /*! \brief Transpose the matrix.
438
439 \note
440 If you start with a column-ordered matrix and invoke transpose, you
441 will have a row-ordered transposed matrix. To change the major vector
442 orientation (e.g., to transform a column-ordered matrix to a
443 column-ordered transposed matrix), invoke transpose() followed by
444 #reverseOrdering().
445 */
446 void transpose();
447
448 /*! \brief Swap the content of two packed matrices. */
449 void swap(CoinPackedMatrix& matrix);
450
451 //@}
452
453 //---------------------------------------------------------------------------
454 /**@name Matrix times vector methods */
455 //@{
456 /** Return <code>A * x</code> in <code>y</code>.
457 @pre <code>x</code> must be of size <code>numColumns()</code>
458 @pre <code>y</code> must be of size <code>numRows()</code> */
459 void times(const double * x, double * y) const;
460#ifndef CLP_NO_VECTOR
461 /** Return <code>A * x</code> in <code>y</code>. Same as the previous
462 method, just <code>x</code> is given in the form of a packed vector. */
463 void times(const CoinPackedVectorBase& x, double * y) const;
464#endif
465 /** Return <code>x * A</code> in <code>y</code>.
466 @pre <code>x</code> must be of size <code>numRows()</code>
467 @pre <code>y</code> must be of size <code>numColumns()</code> */
468 void transposeTimes(const double * x, double * y) const;
469#ifndef CLP_NO_VECTOR
470 /** Return <code>x * A</code> in <code>y</code>. Same as the previous
471 method, just <code>x</code> is given in the form of a packed vector. */
472 void transposeTimes(const CoinPackedVectorBase& x, double * y) const;
473#endif
474 //@}
475
476 //---------------------------------------------------------------------------
477 /**@name Helper functions used internally, but maybe useful externally.
478
479 These methods do not worry about testing whether the packed matrix is
480 row or column major ordered; they operate under the assumption that the
481 correct version is invoked. In fact, a number of other methods simply
482 just call one of these after testing the ordering of the matrix. */
483 //@{
484
485 //-------------------------------------------------------------------------
486 /**@name Queries */
487 //@{
488 /** Count the number of entries in every minor-dimension vector and
489 return an array containing these lengths. The returned array is
490 allocated with <code>new int[]</code>, free it with
491 <code>delete[]</code>. */
492 int * countOrthoLength() const;
493 /** Count the number of entries in every minor-dimension vector and
494 fill in an array containing these lengths. */
495 void countOrthoLength(int * counts) const;
496 /** Major dimension. For row ordered matrix this would be the number of
497 rows. */
498 inline int getMajorDim() const { return majorDim_; }
499 /** Set major dimension. For row ordered matrix this would be the number of
500 rows. Use with great care.*/
501 inline void setMajorDim(int value) { majorDim_ = value; }
502 /** Minor dimension. For row ordered matrix this would be the number of
503 columns. */
504 inline int getMinorDim() const { return minorDim_; }
505 /** Set minor dimension. For row ordered matrix this would be the number of
506 columns. Use with great care.*/
507 inline void setMinorDim(int value) { minorDim_ = value; }
508 /** Current maximum for major dimension. For row ordered matrix this many
509 rows can be added without reallocating the vector related to the
510 major dimension (<code>start_</code> and <code>length_</code>). */
511 inline int getMaxMajorDim() const { return maxMajorDim_; }
512
513 /** Dump the matrix on stdout. When in dire straits this method can
514 help. */
515 void dumpMatrix(const char* fname = nullptr) const;
516
517 /// Print a single matrix element.
518 void printMatrixElement(const int row_val, const int col_val) const;
519 //@}
520
521 //-------------------------------------------------------------------------
522 /*! @name Append vectors
523
524 \details
525 When compiled with COIN_DEBUG defined these methods throw an exception
526 if the major (minor) vector contains an index that's invalid for the
527 minor (major) dimension. Otherwise the methods assume that every index
528 fits into the matrix.
529 */
530 //@{
531#ifndef CLP_NO_VECTOR
532 /** Append a major-dimension vector to the end of the matrix. */
533 void appendMajorVector(const CoinPackedVectorBase& vec);
534#endif
535 /** Append a major-dimension vector to the end of the matrix. */
536 void appendMajorVector(const int vecsize, const int *vecind,
537 const double *vecelem);
538#ifndef CLP_NO_VECTOR
539 /** Append several major-dimensonvectors to the end of the matrix */
540 void appendMajorVectors(const int numvecs,
541 const CoinPackedVectorBase * const * vecs);
542
543 /** Append a minor-dimension vector to the end of the matrix. */
544 void appendMinorVector(const CoinPackedVectorBase& vec);
545#endif
546 /** Append a minor-dimension vector to the end of the matrix. */
547 void appendMinorVector(const int vecsize, const int *vecind,
548 const double *vecelem);
549#ifndef CLP_NO_VECTOR
550 /** Append several minor-dimension vectors to the end of the matrix */
551 void appendMinorVectors(const int numvecs,
552 const CoinPackedVectorBase * const * vecs);
553#endif
554 /*! \brief Append a set of rows (columns) to the end of a column (row)
555 ordered matrix.
556
557 This case is when we know there are no gaps and majorDim_ will not
558 change.
559
560 \todo
561 This method really belongs in the group of protected methods with
562 #appendMinor; there are no safeties here even with COIN_DEBUG.
563 Apparently this method was needed in ClpPackedMatrix and giving it
564 proper visibility was too much trouble. Should be moved.
565 */
566 void appendMinorFast(const int number,
567 const CoinBigIndex * starts, const int * index,
568 const double * element);
569 //@}
570
571 //-------------------------------------------------------------------------
572 /*! \name Append matrices
573
574 \details
575 We'll document these methods assuming that the current matrix is
576 column major ordered (Hence in the <code>...SameOrdered()</code>
577 methods the argument is column ordered, in the
578 <code>OrthoOrdered()</code> methods the argument is row ordered.)
579 */
580 //@{
581 /** Append the columns of the argument to the right end of this matrix.
582 @pre <code>minorDim_ == matrix.minorDim_</code> <br>
583 This method throws an exception if the minor dimensions are not the
584 same. */
585 void majorAppendSameOrdered(const CoinPackedMatrix& matrix);
586 /** Append the columns of the argument to the bottom end of this matrix.
587 @pre <code>majorDim_ == matrix.majorDim_</code> <br>
588 This method throws an exception if the major dimensions are not the
589 same. */
590 void minorAppendSameOrdered(const CoinPackedMatrix& matrix);
591 /** Append the rows of the argument to the right end of this matrix.
592 @pre <code>minorDim_ == matrix.majorDim_</code> <br>
593 This method throws an exception if the minor dimension of the
594 current matrix is not the same as the major dimension of the
595 argument matrix. */
596 void majorAppendOrthoOrdered(const CoinPackedMatrix& matrix);
597 /** Append the rows of the argument to the bottom end of this matrix.
598 @pre <code>majorDim_ == matrix.minorDim_</code> <br>
599 This method throws an exception if the major dimension of the
600 current matrix is not the same as the minor dimension of the
601 argument matrix. */
602 void minorAppendOrthoOrdered(const CoinPackedMatrix& matrix);
603 //@}
604
605 //-----------------------------------------------------------------------
606 /**@name Delete vectors */
607 //@{
608 /** Delete the major-dimension vectors whose indices are listed in
609 <code>indDel</code>. */
610 void deleteMajorVectors(const int numDel, const int * indDel);
611 /** Delete the minor-dimension vectors whose indices are listed in
612 <code>indDel</code>. */
613 void deleteMinorVectors(const int numDel, const int * indDel);
614 //@}
615
616 //-----------------------------------------------------------------------
617 /**@name Various dot products. */
618 //@{
619 /** Return <code>A * x</code> (multiplied from the "right" direction) in
620 <code>y</code>.
621 @pre <code>x</code> must be of size <code>majorDim()</code>
622 @pre <code>y</code> must be of size <code>minorDim()</code> */
623 void timesMajor(const double * x, double * y) const;
624#ifndef CLP_NO_VECTOR
625 /** Return <code>A * x</code> (multiplied from the "right" direction) in
626 <code>y</code>. Same as the previous method, just <code>x</code> is
627 given in the form of a packed vector. */
628 void timesMajor(const CoinPackedVectorBase& x, double * y) const;
629#endif
630 /** Return <code>A * x</code> (multiplied from the "right" direction) in
631 <code>y</code>.
632 @pre <code>x</code> must be of size <code>minorDim()</code>
633 @pre <code>y</code> must be of size <code>majorDim()</code> */
634 void timesMinor(const double * x, double * y) const;
635#ifndef CLP_NO_VECTOR
636 /** Return <code>A * x</code> (multiplied from the "right" direction) in
637 <code>y</code>. Same as the previous method, just <code>x</code> is
638 given in the form of a packed vector. */
639 void timesMinor(const CoinPackedVectorBase& x, double * y) const;
640#endif
641 //@}
642 //@}
643
644 //--------------------------------------------------------------------------
645 /**@name Logical Operations. */
646 //@{
647#ifndef CLP_NO_VECTOR
648 /*! \brief Test for equivalence.
649
650 Two matrices are equivalent if they are both row- or column-ordered,
651 they have the same dimensions, and each (major) vector is equivalent.
652 The operator used to test for equality can be specified using the
653 \p FloatEqual template parameter.
654 */
655 template <class FloatEqual> bool
656 isEquivalent(const CoinPackedMatrix& rhs, const FloatEqual& eq) const
657 {
658 // Both must be column order or both row ordered and must be of same size
659 if ((isColOrdered() ^ rhs.isColOrdered()) ||
660 (getNumCols() != rhs.getNumCols()) ||
661 (getNumRows() != rhs.getNumRows()) ||
662 (getNumElements() != rhs.getNumElements()))
663 return false;
664
665 for (int i=getMajorDim()-1; i >= 0; --i) {
666 CoinShallowPackedVector pv = getVector(i);
667 CoinShallowPackedVector rhsPv = rhs.getVector(i);
668 if ( !pv.isEquivalent(rhsPv,eq) )
669 return false;
670 }
671 return true;
672 }
673
674 /*! \brief Test for equivalence and report differences
675
676 Equivalence is defined as for #isEquivalent. In addition, this method will
677 print differences to std::cerr. Intended for use in unit tests and
678 for debugging.
679 */
680 bool isEquivalent2(const CoinPackedMatrix& rhs) const;
681#else
682 /*! \brief Test for equivalence.
683
684 Two matrices are equivalent if they are both row- or column-ordered,
685 they have the same dimensions, and each (major) vector is equivalent.
686 This method is optimised for speed. CoinPackedVector#isEquivalent is
687 replaced with more efficient code for repeated comparison of
688 equal-length vectors. The CoinRelFltEq operator is used.
689 */
690 bool isEquivalent(const CoinPackedMatrix& rhs, const CoinRelFltEq & eq) const;
691#endif
692 /*! \brief Test for equivalence.
693
694 The test for element equality is the default CoinRelFltEq operator.
695 */
696 bool isEquivalent(const CoinPackedMatrix& rhs) const;
697 //@}
698
699 //--------------------------------------------------------------------------
700 /*! \name Non-const methods
701
702 These are to be used with great care when doing column generation, etc.
703 */
704 //@{
705 /** A vector containing the elements in the packed matrix. Note that there
706 might be gaps in this list, entries that do not belong to any
707 major-dimension vector. To get the actual elements one should look at
708 this vector together with #start_ and #length_. */
709 inline double * getMutableElements() const { return element_; }
710 /** A vector containing the minor indices of the elements in the packed
711 matrix. Note that there might be gaps in this list, entries that do not
712 belong to any major-dimension vector. To get the actual elements one
713 should look at this vector together with #start_ and
714 #length_. */
715 inline int * getMutableIndices() const { return index_; }
716
717 /** The positions where the major-dimension vectors start in #element_ and
718 #index_. */
719 inline CoinBigIndex * getMutableVectorStarts() const { return start_; }
720 /** The lengths of the major-dimension vectors. */
721 inline int * getMutableVectorLengths() const { return length_; }
722 /// Change the size of the bulk store after modifying - be careful
723 inline void setNumElements(CoinBigIndex value)
724 { size_ = value;}
725 /*! NULLify element array
726
727 Used when space is very tight. Does not free the space!
728 */
729 inline void nullElementArray() {element_=nullptr;}
730
731 /*! NULLify start array
732
733 Used when space is very tight. Does not free the space!
734 */
735 inline void nullStartArray() {start_=nullptr;}
736
737 /*! NULLify length array
738
739 Used when space is very tight. Does not free the space!
740 */
741 inline void nullLengthArray() {length_=nullptr;}
742
743 /*! NULLify index array
744
745 Used when space is very tight. Does not free the space!
746 */
747 inline void nullIndexArray() {index_=nullptr;}
748 //@}
749
750 //--------------------------------------------------------------------------
751 /*! \name Constructors and destructors */
752 //@{
753 /// Default Constructor creates an empty column ordered packed matrix
754 CoinPackedMatrix();
755
756 /// A constructor where the ordering and the gaps are specified
757 CoinPackedMatrix(const bool colordered,
758 const double extraMajor, const double extraGap);
759
760 CoinPackedMatrix(const bool colordered,
761 const int minor, const int major, const CoinBigIndex numels,
762 const double * elem, const int * ind,
763 const CoinBigIndex * start, const int * len,
764 const double extraMajor, const double extraGap);
765
766 CoinPackedMatrix(const bool colordered,
767 const int minor, const int major, const CoinBigIndex numels,
768 const double * elem, const int * ind,
769 const CoinBigIndex * start, const int * len);
770
771 /** Create packed matrix from triples.
772 If colordered is true then the created matrix will be column ordered.
773 Duplicate matrix elements are allowed. The created matrix will have
774 the sum of the duplicates. <br>
775 For example if: <br>
776 rowIndices[0]=2; colIndices[0]=5; elements[0]=2.0 <br>
777 rowIndices[1]=2; colIndices[1]=5; elements[1]=0.5 <br>
778 then the created matrix will contain a value of 2.5 in row 2 and column 5.<br>
779 The matrix is created without gaps.
780 */
781 CoinPackedMatrix(const bool colordered,
782 const int * rowIndices,
783 const int * colIndices,
784 const double * elements,
785 CoinBigIndex numels );
786
787 /// Copy constructor
788 CoinPackedMatrix(const CoinPackedMatrix& m);
789
790 /** Copy constructor - fine tuning - allowing extra space and/or reverse ordering.
791 extraForMajor is exact extra after any possible reverse ordering.
792 extraMajor_ and extraGap_ set to zero.
793 */
794 CoinPackedMatrix(const CoinPackedMatrix& m, int extraForMajor, int extraElements, bool reverseOrdering=false);
795
796 /** Subset constructor (without gaps). Duplicates are allowed
797 and order is as given */
798 CoinPackedMatrix (const CoinPackedMatrix & wholeModel,
799 int numberRows, const int * whichRows,
800 int numberColumns, const int * whichColumns);
801
802 /// Destructor
803 virtual ~CoinPackedMatrix();
804 //@}
805
806 /*! \name Debug Utilities */
807 //@{
808 /*! \brief Scan the matrix for anomalies.
809
810 Returns the number of anomalies. Scans the structure for gaps,
811 obviously bogus indices and coefficients, and inconsistencies. Gaps
812 are not an error unless #hasGaps() says the matrix should be
813 gap-free. Zeroes are not an error unless \p zeroesAreError is set to
814 true.
815
816 Values for verbosity are:
817 - 0: No messages, just the return value
818 - 1: Messages about errors
819 - 2: If there are no errors, a message indicating the matrix was
820 checked is printed (positive confirmation).
821 - 3: Adds a bit more information about the matrix.
822 - 4: Prints warnings about zeroes even if they're not considered
823 errors.
824
825 Obviously bogus coefficients are coefficients that are NaN or have
826 absolute value greater than 1e50. Zeros have absolute value less
827 than 1e-50.
828 */
829 int verifyMtx(int verbosity = 1, bool zeroesAreError = false) const ;
830 //@}
831
832 //--------------------------------------------------------------------------
833protected:
834 void gutsOfDestructor();
835 void gutsOfCopyOf(const bool colordered,
836 const int minor, const int major, const CoinBigIndex numels,
837 const double * elem, const int * ind,
838 const CoinBigIndex * start, const int * len,
839 const double extraMajor=0.0, const double extraGap=0.0);
840 /// When no gaps we can do faster
841 void gutsOfCopyOfNoGaps(const bool colordered,
842 const int minor, const int major,
843 const double * elem, const int * ind,
844 const CoinBigIndex * start);
845 void gutsOfOpEqual(const bool colordered,
846 const int minor, const int major, const CoinBigIndex numels,
847 const double * elem, const int * ind,
848 const CoinBigIndex * start, const int * len);
849 void resizeForAddingMajorVectors(const int numVec, const int * lengthVec);
850 void resizeForAddingMinorVectors(const int * addedEntries);
851
852 /*! \brief Append a set of rows (columns) to the end of a row (colum)
853 ordered matrix.
854
855 If \p numberOther > 0 the method will check if any of the new rows
856 (columns) contain duplicate indices or invalid indices and return the
857 number of errors. A valid minor index must satisfy
858 \code 0 <= k < numberOther \endcode
859 If \p numberOther < 0 no checking is performed.
860 */
861 int appendMajor(const int number,
862 const CoinBigIndex * starts, const int * index,
863 const double * element, int numberOther=-1);
864 /*! \brief Append a set of rows (columns) to the end of a column (row)
865 ordered matrix.
866
867 If \p numberOther > 0 the method will check if any of the new rows
868 (columns) contain duplicate indices or indices outside the current
869 range for the major dimension and return the number of violations.
870 If \p numberOther <= 0 the major dimension will be expanded as
871 necessary and there are no checks for duplicate indices.
872 */
873 int appendMinor(const int number,
874 const CoinBigIndex * starts, const int * index,
875 const double * element, int numberOther=-1);
876
877private:
878 inline CoinBigIndex getLastStart() const {
879 return majorDim_ == 0 ? 0 : start_[majorDim_];
880 }
881
882 //--------------------------------------------------------------------------
883protected:
884 /**@name Data members
885 The data members are protected to allow access for derived classes. */
886 //@{
887 /** A flag indicating whether the matrix is column or row major ordered. */
888 bool colOrdered_;
889 /** This much times more space should be allocated for each major-dimension
890 vector (with respect to the number of entries in the vector) when the
891 matrix is resized. The purpose of these gaps is to allow fast insertion
892 of new minor-dimension vectors. */
893 double extraGap_;
894 /** his much times more space should be allocated for major-dimension
895 vectors when the matrix is resized. The purpose of these gaps is to
896 allow fast addition of new major-dimension vectors. */
897 double extraMajor_;
898
899 /** List of nonzero element values. The entries in the gaps between
900 major-dimension vectors are undefined. */
901 double *element_;
902 /** List of nonzero element minor-dimension indices. The entries in the gaps
903 between major-dimension vectors are undefined. */
904 int *index_;
905 /** Starting positions of major-dimension vectors. */
906 CoinBigIndex *start_;
907 /** Lengths of major-dimension vectors. */
908 int *length_;
909
910 /// number of vectors in matrix
911 int majorDim_;
912 /// size of other dimension
913 int minorDim_;
914 /// the number of nonzero entries
915 CoinBigIndex size_;
916
917 /// max space allocated for major-dimension
918 int maxMajorDim_;
919 /// max space allocated for entries
920 CoinBigIndex maxSize_;
921 //@}
922};
923
924//#############################################################################
925/*! \brief Test the methods in the CoinPackedMatrix class.
926
927 The only reason for it not to be a member method is that this way
928 it doesn't have to be compiled into the library. And that's a gain,
929 because the library should be compiled with optimization on, but this
930 method should be compiled with debugging.
931*/
932void
933CoinPackedMatrixUnitTest();
934
935#endif
936