Storm 1.10.0.1
A Modern Probabilistic Model Checker
Loading...
Searching...
No Matches
SparseMatrix.h
Go to the documentation of this file.
1#pragma once
2
3#include <algorithm>
4#include <cstdint>
5#include <iosfwd>
6#include <iterator>
7#include <vector>
8
9#include <boost/functional/hash.hpp>
10#include <boost/optional.hpp>
11#include <boost/range/irange.hpp>
12
16
18
19// Forward declaration for adapter classes.
20namespace storm {
21namespace adapters {
22template<typename ValueType>
24class EigenAdapter;
25class StormAdapter;
26} // namespace adapters
27} // namespace storm
28
29namespace storm {
30namespace storage {
31
32// Forward declare matrix class.
33template<typename T>
34class SparseMatrix;
35
37
38template<typename IndexType, typename ValueType>
40 public:
41 typedef IndexType index_type;
42 typedef ValueType value_type;
43
50 MatrixEntry(index_type column, value_type value);
51
57 MatrixEntry(std::pair<index_type, value_type>&& pair);
58
59 MatrixEntry() = default;
60 MatrixEntry(MatrixEntry const& other) = default;
61 MatrixEntry& operator=(MatrixEntry const& other) = default;
62 MatrixEntry(MatrixEntry&& other) = default;
63 MatrixEntry& operator=(MatrixEntry&& other) = default;
64
70 index_type const& getColumn() const;
71
77 void setColumn(index_type const& column);
78
84 value_type const& getValue() const;
85
91 void setValue(value_type const& value);
92
98 std::pair<index_type, value_type> const& getColumnValuePair() const;
99
105 MatrixEntry operator*(value_type factor) const;
106
107 bool operator==(MatrixEntry const& other) const;
108 bool operator!=(MatrixEntry const& other) const;
109
110 template<typename IndexTypePrime, typename ValueTypePrime>
111 friend std::ostream& operator<<(std::ostream& out, MatrixEntry<IndexTypePrime, ValueTypePrime> const& entry);
112
113 private:
114 // The actual matrix entry.
115 std::pair<index_type, value_type> entry;
116};
117
121template<typename IndexType, typename ValueType>
122std::size_t hash_value(MatrixEntry<IndexType, ValueType> const& matrixEntry) {
123 std::size_t seed = 0;
124 boost::hash_combine(seed, matrixEntry.getColumn());
125 boost::hash_combine(seed, matrixEntry.getValue());
126 return seed;
127}
128
132template<typename ValueType>
134 public:
136 typedef ValueType value_type;
137
153 SparseMatrixBuilder(index_type rows = 0, index_type columns = 0, index_type entries = 0, bool forceDimensions = true, bool hasCustomRowGrouping = false,
154 index_type rowGroups = 0);
155
163
177 void addNextValue(index_type row, index_type column, value_type const& value);
178
185 void newRowGroup(index_type startingRow);
186
187 /*
188 * Finalizes the sparse matrix to indicate that initialization process has been completed and the matrix
189 * may now be used. This must be called after all entries have been added to the matrix via addNextValue.
190 *
191 * @param overriddenRowCount If this is set to a value that is greater than the current number of rows,
192 * this will cause the finalize method to add empty rows at the end of the matrix until the given row count
193 * has been matched. Note that this will *not* override the row count that has been given upon construction
194 * (if any), but will only take effect if the matrix has been created without the number of rows given.
195 * @param overriddenColumnCount If this is set to a value that is greater than the current number of columns,
196 * this will cause the finalize method to set the number of columns to the given value. Note that this will
197 * *not* override the column count that has been given upon construction (if any), but will only take effect
198 * if the matrix has been created without the number of columns given. By construction, the matrix will have
199 * no entries in the columns that have been added this way.
200 * @param overriddenRowGroupCount If this is set to a value that is greater than the current number of row
201 * groups, this will cause the method to set the number of row groups to the given value. Note that this will
202 * *not* override the row group count that has been given upon construction (if any), but will only take
203 * effect if the matrix has been created without the number of row groups given. By construction, the row
204 * groups added this way will be empty.
205 */
206 SparseMatrix<value_type> build(index_type overriddenRowCount = 0, index_type overriddenColumnCount = 0, index_type overriddenRowGroupCount = 0);
207
213 index_type getLastRow() const;
214
221
228
237 void replaceColumns(std::vector<index_type> const& replacements, index_type offset);
238
246 void addDiagonalEntry(index_type row, ValueType const& value);
247
248 private:
249 // A flag indicating whether a row count was set upon construction.
250 bool initialRowCountSet;
251
252 // The row count that was initially set (if any).
253 index_type initialRowCount;
254
255 // A flag indicating whether a column count was set upon construction.
256 bool initialColumnCountSet;
257
258 // The column count that was initially set (if any).
259 index_type initialColumnCount;
260
261 // A flag indicating whether an entry count was set upon construction.
262 bool initialEntryCountSet;
263
264 // The number of entries in the matrix.
265 index_type initialEntryCount;
266
267 // A flag indicating whether the initially given dimensions are to be enforced on the resulting matrix.
268 bool forceInitialDimensions;
269
270 // A flag indicating whether the builder is to construct a custom row grouping for the matrix.
271 bool hasCustomRowGrouping;
272
273 // A flag indicating whether the number of row groups was set upon construction.
274 bool initialRowGroupCountSet;
275
276 // The number of row groups in the matrix.
277 index_type initialRowGroupCount;
278
279 // The vector that stores the row-group indices (if they are non-trivial).
280 boost::optional<std::vector<index_type>> rowGroupIndices;
281
282 // The storage for the columns and values of all entries in the matrix.
283 std::vector<MatrixEntry<index_type, value_type>> columnsAndValues;
284
285 // A vector containing the indices at which each given row begins. This index is to be interpreted as an
286 // index in the valueStorage and the columnIndications vectors. Put differently, the values of the entries
287 // in row i are valueStorage[rowIndications[i]] to valueStorage[rowIndications[i + 1]] where the last
288 // entry is not included anymore.
289 std::vector<index_type> rowIndications;
290
291 // Stores the current number of entries in the matrix. This is used for inserting an entry into a matrix
292 // with preallocated storage.
293 index_type currentEntryCount;
294
295 // Stores the row of the last entry in the matrix. This is used for correctly inserting an entry into a
296 // matrix.
297 index_type lastRow;
298
299 // Stores the column of the currently last entry in the matrix. This is used for correctly inserting an
300 // entry into a matrix.
301 index_type lastColumn;
302
303 // Stores the highest column at which an entry was inserted into the matrix.
304 index_type highestColumn;
305
306 // Stores the currently active row group. This is used for correctly constructing the row grouping of the
307 // matrix.
308 index_type currentRowGroupCount;
309
310 boost::optional<ValueType> pendingDiagonalEntry;
311};
312
327template<typename ValueType>
329 public:
330 // Declare adapter classes as friends to use internal data.
331 friend class storm::adapters::GmmxxAdapter<ValueType>;
334 friend class SparseMatrixBuilder<ValueType>;
335
337 typedef ValueType value_type;
338 typedef typename std::vector<MatrixEntry<index_type, value_type>>::iterator iterator;
339 typedef typename std::vector<MatrixEntry<index_type, value_type>>::const_iterator const_iterator;
340
344 class rows {
345 public:
353 rows(iterator begin, index_type entryCount);
354
360 iterator begin();
361
367 iterator end();
368
375
376 private:
377 // The pointer to the columnd and value of the first entry.
378 iterator beginIterator;
379
380 // The number of non-zero entries in the rows.
381 index_type entryCount;
382 };
383
388 public:
397
403 const_iterator begin() const;
404
410 const_iterator end() const;
411
418
419 private:
420 // The pointer to the column and value of the first entry.
421 const_iterator beginIterator;
422
423 // The number of non-zero entries in the rows.
424 index_type entryCount;
425 };
426
433
437 SparseMatrix();
438
445
453 SparseMatrix(SparseMatrix<value_type> const& other, bool insertDiagonalElements);
454
461
470 SparseMatrix(index_type columnCount, std::vector<index_type> const& rowIndications,
471 std::vector<MatrixEntry<index_type, value_type>> const& columnsAndValues, boost::optional<std::vector<index_type>> const& rowGroupIndices);
472
481 SparseMatrix(index_type columnCount, std::vector<index_type>&& rowIndications, std::vector<MatrixEntry<index_type, value_type>>&& columnsAndValues,
482 boost::optional<std::vector<index_type>>&& rowGroupIndices);
483
490
497
504 bool operator==(SparseMatrix<value_type> const& other) const;
505
511 index_type getRowCount() const;
512
519
526
533
542
546 void updateNonzeroEntryCount() const;
547
551 void updateDimensions() const;
552
558 void updateNonzeroEntryCount(std::make_signed<index_type>::type difference);
559
566
574
579
583 index_type getNumRowsInRowGroups(storm::storage::BitVector const& groupConstraint) const;
584
590 std::vector<index_type> const& getRowGroupIndices() const;
591
595 boost::integer_range<index_type> getRowGroupIndices(index_type group) const;
596
602 std::vector<index_type> swapRowGroupIndices(std::vector<index_type>&& newRowGrouping);
603
610 void setRowGroupIndices(std::vector<index_type> const& newRowGroupIndices);
611
617 bool hasTrivialRowGrouping() const;
618
624
633
643 storm::storage::BitVector getRowFilter(storm::storage::BitVector const& groupConstraint, storm::storage::BitVector const& columnConstraints) const;
644
653 storm::storage::BitVector getRowGroupFilter(storm::storage::BitVector const& rowConstraint, bool setIfForAllRowsInGroup) const;
654
662 void makeRowsAbsorbing(storm::storage::BitVector const& rows, bool dropZeroEntries = false);
663
671 void makeRowGroupsAbsorbing(storm::storage::BitVector const& rowGroupConstraint, bool dropZeroEntries = false);
672
682 void makeRowDirac(index_type row, index_type column, bool dropZeroEntries = false);
683
689 std::vector<ValueType> getRowSumVector() const;
690
699
709 std::vector<value_type> getConstrainedRowSumVector(storm::storage::BitVector const& rowConstraint, storm::storage::BitVector const& columnConstraint) const;
710
720 std::vector<value_type> getConstrainedRowGroupSumVector(storm::storage::BitVector const& rowGroupConstraint,
721 storm::storage::BitVector const& columnConstraint) const;
722
738 SparseMatrix getSubmatrix(bool useGroups, storm::storage::BitVector const& rowConstraint, storm::storage::BitVector const& columnConstraint,
739 bool insertDiagonalEntries = false, storm::storage::BitVector const& makeZeroColumns = storm::storage::BitVector()) const;
740
751 SparseMatrix restrictRows(storm::storage::BitVector const& rowsToKeep, bool allowEmptyRowGroups = false) const;
752
759 SparseMatrix permuteRows(std::vector<index_type> const& inversePermutation) const;
760
768 SparseMatrix permuteRowGroupsAndColumns(std::vector<index_type> const& inverseRowGroupPermutation, std::vector<index_type> const& columnPermutation) const;
769
778
782 void dropZeroEntries();
783
790 bool compareRows(index_type i1, index_type i2) const;
791
796
802 void swapRows(index_type const& row1, index_type const& row2);
803
811 SparseMatrix selectRowsFromRowGroups(std::vector<index_type> const& rowGroupToRowIndexMapping, bool insertDiagonalEntries = true) const;
812
822 SparseMatrix selectRowsFromRowIndexSequence(std::vector<index_type> const& rowIndexSequence, bool insertDiagonalEntries = true) const;
823
832 storm::storage::SparseMatrix<value_type> transpose(bool joinGroups = false, bool keepZeros = false) const;
833
842 SparseMatrix<ValueType> transposeSelectedRowsFromRowGroups(std::vector<uint64_t> const& rowGroupChoices, bool keepZeros = false) const;
843
848
853 void invertDiagonal();
854
859
865 void deleteDiagonalEntries(bool dropZeroEntries = false);
866
872 std::pair<storm::storage::SparseMatrix<value_type>, std::vector<value_type>> getJacobiDecomposition() const;
873
883 template<typename OtherValueType, typename ResultValueType = OtherValueType>
884 ResultValueType getPointwiseProductRowSum(storm::storage::SparseMatrix<OtherValueType> const& otherMatrix, index_type const& row) const;
885
896 template<typename OtherValueType, typename ResultValueType = OtherValueType>
897 std::vector<ResultValueType> getPointwiseProductRowSumVector(storm::storage::SparseMatrix<OtherValueType> const& otherMatrix) const;
898
907 void multiplyWithVector(std::vector<value_type> const& vector, std::vector<value_type>& result, std::vector<value_type> const* summand = nullptr) const;
908
909 void multiplyWithVectorForward(std::vector<value_type> const& vector, std::vector<value_type>& result,
910 std::vector<value_type> const* summand = nullptr) const;
911 void multiplyWithVectorBackward(std::vector<value_type> const& vector, std::vector<value_type>& result,
912 std::vector<value_type> const* summand = nullptr) const;
913
928 void multiplyAndReduce(storm::solver::OptimizationDirection const& dir, std::vector<uint64_t> const& rowGroupIndices, std::vector<ValueType> const& vector,
929 std::vector<ValueType> const* summand, std::vector<ValueType>& result, std::vector<uint64_t>* choices) const;
930
931 void multiplyAndReduceForward(storm::solver::OptimizationDirection const& dir, std::vector<uint64_t> const& rowGroupIndices,
932 std::vector<ValueType> const& vector, std::vector<ValueType> const* b, std::vector<ValueType>& result,
933 std::vector<uint64_t>* choices) const;
934 template<typename Compare>
935 void multiplyAndReduceForward(std::vector<uint64_t> const& rowGroupIndices, std::vector<ValueType> const& vector, std::vector<ValueType> const* summand,
936 std::vector<ValueType>& result, std::vector<uint64_t>* choices) const;
937
938 void multiplyAndReduceBackward(storm::solver::OptimizationDirection const& dir, std::vector<uint64_t> const& rowGroupIndices,
939 std::vector<ValueType> const& vector, std::vector<ValueType> const* b, std::vector<ValueType>& result,
940 std::vector<uint64_t>* choices) const;
941 template<typename Compare>
942 void multiplyAndReduceBackward(std::vector<uint64_t> const& rowGroupIndices, std::vector<ValueType> const& vector, std::vector<ValueType> const* b,
943 std::vector<ValueType>& result, std::vector<uint64_t>* choices) const;
944
952 value_type multiplyRowWithVector(index_type row, std::vector<value_type> const& vector) const;
953
963 void multiplyVectorWithMatrix(std::vector<value_type> const& vector, std::vector<value_type>& result) const;
964
970 void scaleRowsInPlace(std::vector<value_type> const& factors);
971
977 void divideRowsInPlace(std::vector<value_type> const& divisors);
978
986 void performSuccessiveOverRelaxationStep(ValueType omega, std::vector<ValueType>& x, std::vector<ValueType> const& b) const;
987
997 void performWalkerChaeStep(std::vector<ValueType> const& x, std::vector<ValueType> const& columnSums, std::vector<ValueType> const& b,
998 std::vector<ValueType> const& ax, std::vector<ValueType>& result) const;
999
1006 value_type getRowSum(index_type row) const;
1007
1012
1017
1021 bool isProbabilistic() const;
1022
1026 bool hasOnlyPositiveEntries() const;
1027
1035 template<typename OtherValueType>
1036 bool isSubmatrixOf(SparseMatrix<OtherValueType> const& matrix) const;
1037
1038 // Returns true if the matrix is the identity matrix
1039 bool isIdentityMatrix() const;
1040
1041 template<typename TPrime>
1042 friend std::ostream& operator<<(std::ostream& out, SparseMatrix<TPrime> const& matrix);
1043
1047 std::string getDimensionsAsString() const;
1048
1055 void printAsMatlabMatrix(std::ostream& out) const;
1056
1062 std::size_t hash() const;
1063
1071 const_rows getRows(index_type startRow, index_type endRow) const;
1072
1080 rows getRows(index_type startRow, index_type endRow);
1081
1088 const_rows getRow(index_type row) const;
1089
1096 rows getRow(index_type row);
1097
1104 const_rows getRow(index_type rowGroup, index_type offset) const;
1105
1112 rows getRow(index_type rowGroup, index_type offset);
1113
1120 const_rows getRowGroup(index_type rowGroup) const;
1121
1128 rows getRowGroup(index_type rowGroup);
1129
1136 const_iterator begin(index_type row) const;
1137
1145
1151 const_iterator begin() const;
1152
1158 iterator begin();
1159
1166 const_iterator end(index_type row) const;
1167
1174 iterator end(index_type row);
1175
1181 const_iterator end() const;
1182
1188 iterator end();
1189
1193 template<typename NewValueType>
1195 std::vector<MatrixEntry<SparseMatrix::index_type, NewValueType>> newColumnsAndValues;
1196 std::vector<SparseMatrix::index_type> newRowIndications(rowIndications);
1197 boost::optional<std::vector<SparseMatrix::index_type>> newRowGroupIndices(rowGroupIndices);
1198
1199 newColumnsAndValues.resize(columnsAndValues.size());
1200 std::transform(
1201 columnsAndValues.begin(), columnsAndValues.end(), newColumnsAndValues.begin(), [](MatrixEntry<SparseMatrix::index_type, ValueType> const& a) {
1202 return MatrixEntry<SparseMatrix::index_type, NewValueType>(a.getColumn(), storm::utility::convertNumber<NewValueType, ValueType>(a.getValue()));
1203 });
1204
1205 return SparseMatrix<NewValueType>(columnCount, std::move(newRowIndications), std::move(newColumnsAndValues), std::move(newRowGroupIndices));
1206 }
1207
1208 private:
1221 SparseMatrix getSubmatrix(storm::storage::BitVector const& rowGroupConstraint, storm::storage::BitVector const& columnConstraint,
1222 std::vector<index_type> const& rowGroupIndices, bool insertDiagonalEntries = false,
1223 storm::storage::BitVector const& makeZeroColumns = storm::storage::BitVector()) const;
1224
1225 // The number of rows of the matrix.
1226 index_type rowCount;
1227
1228 // The number of columns of the matrix.
1229 mutable index_type columnCount;
1230
1231 // The number of entries in the matrix.
1232 index_type entryCount;
1233
1234 // The number of nonzero entries in the matrix.
1235 mutable index_type nonzeroEntryCount;
1236
1237 // The storage for the columns and values of all entries in the matrix.
1238 std::vector<MatrixEntry<index_type, value_type>> columnsAndValues;
1239
1240 // A vector containing the indices at which each given row begins. This index is to be interpreted as an
1241 // index in the valueStorage and the columnIndications vectors. Put differently, the values of the entries
1242 // in row i are valueStorage[rowIndications[i]] to valueStorage[rowIndications[i + 1]] where the last
1243 // entry is not included anymore.
1244 std::vector<index_type> rowIndications;
1245
1246 // A flag indicating whether the matrix has a trivial row grouping. Note that this may be true and yet
1247 // there may be row group indices, because they were requested from the outside.
1248 bool trivialRowGrouping;
1249
1250 // A vector indicating the row groups of the matrix. This needs to be mutible in case we create it on-the-fly.
1251 mutable boost::optional<std::vector<index_type>> rowGroupIndices;
1252};
1253
1254} // namespace storage
1255} // namespace storm
A bit vector that is internally represented as a vector of 64-bit values.
Definition BitVector.h:16
MatrixEntry operator*(value_type factor) const
Multiplies the entry with the given factor and returns the result.
value_type const & getValue() const
Retrieves the value of the matrix entry.
std::pair< index_type, value_type > const & getColumnValuePair() const
Retrieves a pair of column and value that characterizes this entry.
MatrixEntry(MatrixEntry &&other)=default
void setColumn(index_type const &column)
Sets the column of the current entry.
MatrixEntry()=default
MatrixEntry(MatrixEntry const &other)=default
index_type const & getColumn() const
Retrieves the column of the matrix entry.
bool operator!=(MatrixEntry const &other) const
void setValue(value_type const &value)
Sets the value of the entry in the matrix.
MatrixEntry & operator=(MatrixEntry &&other)=default
MatrixEntry & operator=(MatrixEntry const &other)=default
ValueType value_type
IndexType index_type
friend std::ostream & operator<<(std::ostream &out, MatrixEntry< IndexTypePrime, ValueTypePrime > const &entry)
bool operator==(MatrixEntry const &other) const
This class represents a number of consecutive rows of the matrix.
const_iterator end() const
Retrieves an iterator that points past the last entry of the rows.
index_type getNumberOfEntries() const
Retrieves the number of entries in the rows.
const_iterator begin() const
Retrieves an iterator that points to the beginning of the rows.
This class represents a number of consecutive rows of the matrix.
iterator end()
Retrieves an iterator that points past the last entry of the rows.
iterator begin()
Retrieves an iterator that points to the beginning of the rows.
index_type getNumberOfEntries() const
Retrieves the number of entries in the rows.
A class that can be used to build a sparse matrix by adding value by value.
index_type getCurrentRowGroupCount() const
Retrieves the current row group count.
index_type getLastRow() const
Retrieves the most recently used row.
void addNextValue(index_type row, index_type column, value_type const &value)
Sets the matrix entry at the given row and column to the given value.
void replaceColumns(std::vector< index_type > const &replacements, index_type offset)
Replaces all columns with id > offset according to replacements.
void newRowGroup(index_type startingRow)
Starts a new row group in the matrix.
index_type getLastColumn() const
Retrieves the most recently used row.
void addDiagonalEntry(index_type row, ValueType const &value)
Makes sure that a diagonal entry will be inserted at the given row.
SparseMatrix< value_type > build(index_type overriddenRowCount=0, index_type overriddenColumnCount=0, index_type overriddenRowGroupCount=0)
A class that holds a possibly non-square matrix in the compressed row storage format.
void divideRowsInPlace(std::vector< value_type > const &divisors)
Divides each row of the matrix, i.e., divides each element in row i with divisors[i].
void convertToEquationSystem()
Transforms the matrix into an equation system.
SparseMatrix()
Constructs an empty sparse matrix.
void swapRows(index_type const &row1, index_type const &row2)
Swaps the two rows.
bool operator==(SparseMatrix< value_type > const &other) const
Determines whether the current and the given matrix are semantically equal.
const_rows getRow(index_type row) const
Returns an object representing the given row.
index_type getSizeOfLargestRowGroup() const
Returns the size of the largest row group of the matrix.
SparseMatrix selectRowsFromRowGroups(std::vector< index_type > const &rowGroupToRowIndexMapping, bool insertDiagonalEntries=true) const
Selects exactly one row from each row group of this matrix and returns the resulting matrix.
void multiplyWithVectorForward(std::vector< value_type > const &vector, std::vector< value_type > &result, std::vector< value_type > const *summand=nullptr) const
index_type getEntryCount() const
Returns the number of entries in the matrix.
const_rows getRows(index_type startRow, index_type endRow) const
Returns an object representing the consecutive rows given by the parameters.
index_type getNonconstantEntryCount() const
Returns the number of non-constant entries.
void multiplyVectorWithMatrix(std::vector< value_type > const &vector, std::vector< value_type > &result) const
Multiplies the vector to the matrix from the left and writes the result to the given result vector.
void multiplyAndReduceBackward(storm::solver::OptimizationDirection const &dir, std::vector< uint64_t > const &rowGroupIndices, std::vector< ValueType > const &vector, std::vector< ValueType > const *b, std::vector< ValueType > &result, std::vector< uint64_t > *choices) const
index_type getNumRowsInRowGroups(storm::storage::BitVector const &groupConstraint) const
Returns the total number of rows that are in one of the specified row groups.
void makeRowsAbsorbing(storm::storage::BitVector const &rows, bool dropZeroEntries=false)
This function makes the given rows absorbing.
std::vector< ResultValueType > getPointwiseProductRowSumVector(storm::storage::SparseMatrix< OtherValueType > const &otherMatrix) const
Performs a pointwise matrix multiplication of the matrix with the given matrix and returns a vector c...
void multiplyWithVector(std::vector< value_type > const &vector, std::vector< value_type > &result, std::vector< value_type > const *summand=nullptr) const
Multiplies the matrix with the given vector and writes the result to the given result vector.
void updateNonzeroEntryCount() const
Recompute the nonzero entry count.
bool isProbabilistic() const
Checks for each row whether it sums to one.
void multiplyWithVectorBackward(std::vector< value_type > const &vector, std::vector< value_type > &result, std::vector< value_type > const *summand=nullptr) const
SparseMatrix getSubmatrix(bool useGroups, storm::storage::BitVector const &rowConstraint, storm::storage::BitVector const &columnConstraint, bool insertDiagonalEntries=false, storm::storage::BitVector const &makeZeroColumns=storm::storage::BitVector()) const
Creates a submatrix of the current matrix by dropping all rows and columns whose bits are not set to ...
void performWalkerChaeStep(std::vector< ValueType > const &x, std::vector< ValueType > const &columnSums, std::vector< ValueType > const &b, std::vector< ValueType > const &ax, std::vector< ValueType > &result) const
Performs one step of the Walker-Chae technique.
void updateDimensions() const
Recomputes the number of columns and the number of non-zero entries.
void printAsMatlabMatrix(std::ostream &out) const
Prints the matrix in a dense format, as also used by e.g.
void performSuccessiveOverRelaxationStep(ValueType omega, std::vector< ValueType > &x, std::vector< ValueType > const &b) const
Performs one step of the successive over-relaxation technique.
std::vector< value_type > getConstrainedRowSumVector(storm::storage::BitVector const &rowConstraint, storm::storage::BitVector const &columnConstraint) const
Computes a vector whose i-th entry is the sum of the entries in the i-th selected row where only thos...
BitVector duplicateRowsInRowgroups() const
Finds duplicate rows in a rowgroup.
bool compareRows(index_type i1, index_type i2) const
Compares two rows.
const_rows getRowGroup(index_type rowGroup) const
Returns an object representing the given row group.
SparseMatrix permuteRows(std::vector< index_type > const &inversePermutation) const
Permute rows of the matrix according to the vector.
void setRowGroupIndices(std::vector< index_type > const &newRowGroupIndices)
Sets the row grouping to the given one.
void negateAllNonDiagonalEntries()
Negates (w.r.t.
const_iterator begin() const
Retrieves an iterator that points to the beginning of the first row of the matrix.
std::vector< index_type > swapRowGroupIndices(std::vector< index_type > &&newRowGrouping)
Swaps the grouping of rows of this matrix.
SparseMatrix restrictRows(storm::storage::BitVector const &rowsToKeep, bool allowEmptyRowGroups=false) const
Restrict rows in grouped rows matrix.
std::vector< ValueType > getRowSumVector() const
Sums the entries in all rows.
friend class storm::adapters::StormAdapter
SparseMatrix< NewValueType > toValueType() const
Returns a copy of the matrix with the chosen internal data type.
value_type multiplyRowWithVector(index_type row, std::vector< value_type > const &vector) const
Multiplies a single row of the matrix with the given vector and returns the result.
MatrixStatus
An enum representing the internal state of the matrix.
SparseMatrix< ValueType > transposeSelectedRowsFromRowGroups(std::vector< uint64_t > const &rowGroupChoices, bool keepZeros=false) const
Transposes the matrix w.r.t.
void multiplyAndReduceForward(storm::solver::OptimizationDirection const &dir, std::vector< uint64_t > const &rowGroupIndices, std::vector< ValueType > const &vector, std::vector< ValueType > const *b, std::vector< ValueType > &result, std::vector< uint64_t > *choices) const
value_type getRowSum(index_type row) const
Computes the sum of the entries in a given row.
SparseMatrix permuteRowGroupsAndColumns(std::vector< index_type > const &inverseRowGroupPermutation, std::vector< index_type > const &columnPermutation) const
Permutes row groups and columns of the matrix according to the given permutations.
void multiplyAndReduce(storm::solver::OptimizationDirection const &dir, std::vector< uint64_t > const &rowGroupIndices, std::vector< ValueType > const &vector, std::vector< ValueType > const *summand, std::vector< ValueType > &result, std::vector< uint64_t > *choices) const
Multiplies the matrix with the given vector, reduces it according to the given direction and and writ...
index_type getRowGroupCount() const
Returns the number of row groups in the matrix.
void dropZeroEntries()
Removes all zero entries from this.
bool isSubmatrixOf(SparseMatrix< OtherValueType > const &matrix) const
Checks if the current matrix is a submatrix of the given matrix, where a matrix A is called a submatr...
ResultValueType getPointwiseProductRowSum(storm::storage::SparseMatrix< OtherValueType > const &otherMatrix, index_type const &row) const
Performs a pointwise multiplication of the entries in the given row of this matrix and the entries of...
SparseMatrix< value_type > & operator=(SparseMatrix< value_type > const &other)
Assigns the contents of the given matrix to the current one by deep-copying its contents.
void makeRowGroupsAbsorbing(storm::storage::BitVector const &rowGroupConstraint, bool dropZeroEntries=false)
This function makes the groups of rows given by the bit vector absorbing.
std::string getDimensionsAsString() const
Returns a string describing the dimensions of the matrix.
index_type getColumnCount() const
Returns the number of columns of the matrix.
std::pair< storm::storage::SparseMatrix< value_type >, std::vector< value_type > > getJacobiDecomposition() const
Calculates the Jacobi decomposition of this sparse matrix.
void makeRowDirac(index_type row, index_type column, bool dropZeroEntries=false)
This function makes the given row Dirac.
std::vector< MatrixEntry< index_type, value_type > >::const_iterator const_iterator
value_type getConstrainedRowSum(index_type row, storm::storage::BitVector const &columns) const
Sums the entries in the given row and columns.
void deleteDiagonalEntries(bool dropZeroEntries=false)
Sets all diagonal elements to zero.
bool hasTrivialRowGrouping() const
Retrieves whether the matrix has a trivial row grouping.
void invertDiagonal()
Inverts all entries on the diagonal, i.e.
storm::storage::BitVector getRowGroupFilter(storm::storage::BitVector const &rowConstraint, bool setIfForAllRowsInGroup) const
Returns the indices of all row groups selected by the row constraints.
void makeRowGroupingTrivial()
Makes the row grouping of this matrix trivial.
SparseMatrix selectRowsFromRowIndexSequence(std::vector< index_type > const &rowIndexSequence, bool insertDiagonalEntries=true) const
Selects the rows that are given by the sequence of row indices, allowing to select rows arbitrarily o...
std::size_t hash() const
Calculates a hash value over all values contained in the matrix.
std::vector< index_type > const & getRowGroupIndices() const
Returns the grouping of rows of this matrix.
std::vector< MatrixEntry< index_type, value_type > >::iterator iterator
index_type getRowGroupSize(index_type group) const
Returns the size of the given row group.
std::vector< value_type > getConstrainedRowGroupSumVector(storm::storage::BitVector const &rowGroupConstraint, storm::storage::BitVector const &columnConstraint) const
Computes a vector whose entries represent the sums of selected columns for all rows in selected row g...
storm::storage::SparseMatrix< value_type > transpose(bool joinGroups=false, bool keepZeros=false) const
Transposes the matrix.
bool hasOnlyPositiveEntries() const
Checks whether each present entry is strictly positive (omitted entries are not considered).
friend std::ostream & operator<<(std::ostream &out, SparseMatrix< TPrime > const &matrix)
index_type getRowCount() const
Returns the number of rows of the matrix.
SparseMatrixIndexType index_type
index_type getNonzeroEntryCount() const
Returns the cached number of nonzero entries in the matrix.
const_iterator end() const
Retrieves an iterator that points past the end of the last row of the matrix.
index_type getNonconstantRowGroupCount() const
Returns the number of rowGroups that contain a non-constant value.
void scaleRowsInPlace(std::vector< value_type > const &factors)
Scales each row of the matrix, i.e., multiplies each element in row i with factors[i].
index_type getRowGroupEntryCount(index_type const group) const
Returns the number of entries in the given row group of the matrix.
storm::storage::BitVector getRowFilter(storm::storage::BitVector const &groupConstraint) const
Returns a bitvector representing the set of rows, with all indices set that correspond to one of the ...
SparseMatrix filterEntries(storm::storage::BitVector const &rowFilter) const
Returns a copy of this matrix that only considers entries in the selected rows.
std::size_t hash_value(MatrixEntry< IndexType, ValueType > const &matrixEntry)
Computes the hash value of a matrix entry.
storm::storage::sparse::state_type SparseMatrixIndexType
LabParser.cpp.