1#include <boost/functional/hash.hpp>
26template<
typename IndexType,
typename ValueType>
31template<
typename IndexType,
typename ValueType>
36template<
typename IndexType,
typename ValueType>
38 return this->entry.first;
41template<
typename IndexType,
typename ValueType>
43 this->entry.first = column;
46template<
typename IndexType,
typename ValueType>
48 return this->entry.second;
51template<
typename IndexType,
typename ValueType>
53 this->entry.second = value;
56template<
typename IndexType,
typename ValueType>
61template<
typename IndexType,
typename ValueType>
63 return MatrixEntry(this->getColumn(), this->getValue() * factor);
66template<
typename IndexType,
typename ValueType>
68 return this->entry.first == other.entry.first && this->entry.second == other.entry.second;
71template<
typename IndexType,
typename ValueType>
73 return !(*
this == other);
76template<
typename IndexTypePrime,
typename ValueTypePrime>
82template<
typename ValueType>
85 : initialRowCountSet(rows != 0),
86 initialRowCount(rows),
87 initialColumnCountSet(columns != 0),
88 initialColumnCount(columns),
89 initialEntryCountSet(entries != 0),
90 initialEntryCount(entries),
91 forceInitialDimensions(forceDimensions),
92 hasCustomRowGrouping(hasCustomRowGrouping),
93 initialRowGroupCountSet(rowGroups != 0),
94 initialRowGroupCount(rowGroups),
102 currentRowGroupCount(0) {
104 if (initialRowCountSet) {
105 rowIndications.reserve(initialRowCount + 1);
107 if (initialEntryCountSet) {
108 columnsAndValues.reserve(initialEntryCount);
110 if (hasCustomRowGrouping) {
111 rowGroupIndices = std::vector<index_type>();
113 if (initialRowGroupCountSet && hasCustomRowGrouping) {
114 rowGroupIndices.get().reserve(initialRowGroupCount + 1);
116 rowIndications.push_back(0);
119template<
typename ValueType>
121 : initialRowCountSet(false),
123 initialColumnCountSet(false),
124 initialColumnCount(0),
125 initialEntryCountSet(false),
126 initialEntryCount(0),
127 forceInitialDimensions(false),
128 hasCustomRowGrouping(!matrix.trivialRowGrouping),
129 initialRowGroupCountSet(false),
130 initialRowGroupCount(0),
132 columnsAndValues(
std::move(matrix.columnsAndValues)),
133 rowIndications(
std::move(matrix.rowIndications)),
134 currentEntryCount(matrix.entryCount),
135 currentRowGroupCount() {
136 lastRow = matrix.rowCount == 0 ? 0 : matrix.rowCount - 1;
137 lastColumn = columnsAndValues.empty() ? 0 : columnsAndValues.back().getColumn();
138 highestColumn = matrix.getColumnCount() == 0 ? 0 : matrix.getColumnCount() - 1;
141 if (hasCustomRowGrouping) {
142 rowGroupIndices = std::move(matrix.rowGroupIndices);
143 if (!rowGroupIndices->empty()) {
144 rowGroupIndices.get().pop_back();
146 currentRowGroupCount = rowGroupIndices->empty() ? 0 : rowGroupIndices.get().size() - 1;
150 if (!rowIndications.empty()) {
151 rowIndications.pop_back();
155template<
typename ValueType>
158 STORM_LOG_THROW(row >= lastRow, storm::exceptions::InvalidArgumentException,
159 "Adding an element in row " << row <<
", but an element in row " << lastRow <<
" has already been added.");
160 STORM_LOG_ASSERT(columnsAndValues.size() == currentEntryCount,
"Unexpected size of columnsAndValues vector.");
163 if (pendingDiagonalEntry) {
164 index_type diagColumn = hasCustomRowGrouping ? currentRowGroupCount - 1 : lastRow;
165 if (row > lastRow || column >= diagColumn) {
166 ValueType diagValue = std::move(pendingDiagonalEntry.get());
167 pendingDiagonalEntry = boost::none;
169 if (row == lastRow && column == diagColumn) {
172 addNextValue(row, column, diagValue + value);
176 addNextValue(lastRow, diagColumn, diagValue);
183 bool fixCurrentRow = row == lastRow && column < lastColumn;
186 if (row == lastRow && column == lastColumn && rowIndications.back() < currentEntryCount) {
187 columnsAndValues.back().setValue(columnsAndValues.back().getValue() + value);
190 if (row != lastRow) {
192 assert(rowIndications.size() == lastRow + 1);
193 rowIndications.resize(row + 1, currentEntryCount);
200 columnsAndValues.emplace_back(column, value);
201 highestColumn = std::max(highestColumn, column);
207 STORM_LOG_TRACE(
"Fix row " << row <<
" as column " << column <<
" is added out-of-order.");
209 std::sort(columnsAndValues.begin() + rowIndications.back(), columnsAndValues.end(),
211 return a.getColumn() < b.getColumn();
214 auto insertIt = columnsAndValues.begin() + rowIndications.back();
215 uint64_t elementsToRemove = 0;
216 for (
auto it = insertIt + 1; it != columnsAndValues.end(); ++it) {
218 if (it->getColumn() == insertIt->getColumn()) {
220 insertIt->setValue(insertIt->getValue() + it->getValue());
228 static_cast<void>(std::unique(columnsAndValues.begin() + rowIndications.back(), columnsAndValues.end(),
232 if (elementsToRemove > 0) {
233 STORM_LOG_WARN(
"Unordered insertion into matrix builder caused duplicate entries.");
234 currentEntryCount -= elementsToRemove;
235 columnsAndValues.resize(columnsAndValues.size() - elementsToRemove);
237 lastColumn = columnsAndValues.back().getColumn();
242 if (forceInitialDimensions) {
243 STORM_LOG_THROW(!initialRowCountSet || lastRow < initialRowCount, storm::exceptions::OutOfRangeException,
244 "Cannot insert value at illegal row " << lastRow <<
".");
245 STORM_LOG_THROW(!initialColumnCountSet || lastColumn < initialColumnCount, storm::exceptions::OutOfRangeException,
246 "Cannot insert value at illegal column " << lastColumn <<
".");
247 STORM_LOG_THROW(!initialEntryCountSet || currentEntryCount <= initialEntryCount, storm::exceptions::OutOfRangeException,
248 "Too many entries in matrix, expected only " << initialEntryCount <<
".");
252template<
typename ValueType>
254 STORM_LOG_THROW(hasCustomRowGrouping, storm::exceptions::InvalidStateException,
"Matrix was not created to have a custom row grouping.");
255 STORM_LOG_THROW(startingRow >= lastRow, storm::exceptions::InvalidStateException,
"Illegal row group with negative size.");
258 if (pendingDiagonalEntry) {
259 STORM_LOG_ASSERT(currentRowGroupCount > 0,
"Diagonal entry was set before opening the first row group.");
260 index_type diagColumn = currentRowGroupCount - 1;
261 ValueType diagValue = std::move(pendingDiagonalEntry.get());
262 pendingDiagonalEntry = boost::none;
263 addNextValue(lastRow, diagColumn, diagValue);
266 rowGroupIndices.get().push_back(startingRow);
267 ++currentRowGroupCount;
270 if (lastRow + 1 < startingRow) {
272 assert(rowIndications.size() == lastRow + 1);
273 rowIndications.resize(startingRow, currentEntryCount);
275 lastRow = startingRow - 1;
280template<
typename ValueType>
284 if (pendingDiagonalEntry) {
285 index_type diagColumn = hasCustomRowGrouping ? currentRowGroupCount - 1 : lastRow;
286 ValueType diagValue = std::move(pendingDiagonalEntry.get());
287 pendingDiagonalEntry = boost::none;
288 addNextValue(lastRow, diagColumn, diagValue);
291 bool hasEntries = currentEntryCount != 0;
293 uint_fast64_t rowCount = hasEntries ? lastRow + 1 : 0;
296 if (hasCustomRowGrouping) {
297 if (lastRow < rowGroupIndices->back()) {
302 if (initialRowCountSet && forceInitialDimensions) {
303 STORM_LOG_THROW(rowCount <= initialRowCount, storm::exceptions::InvalidStateException,
304 "Expected not more than " << initialRowCount <<
" rows, but got " << rowCount <<
".");
305 rowCount = std::max(rowCount, initialRowCount);
308 rowCount = std::max(rowCount, overriddenRowCount);
312 rowIndications.push_back(currentEntryCount);
319 rowIndications.push_back(currentEntryCount);
322 "Wrong sizes of row indications vector: (Rowcount) " << rowCount <<
" != " << (rowIndications.size() - 1) <<
" (Vector).");
323 uint_fast64_t columnCount = hasEntries ? highestColumn + 1 : 0;
324 if (initialColumnCountSet && forceInitialDimensions) {
325 STORM_LOG_THROW(columnCount <= initialColumnCount, storm::exceptions::InvalidStateException,
326 "Expected not more than " << initialColumnCount <<
" columns, but got " << columnCount <<
".");
327 columnCount = std::max(columnCount, initialColumnCount);
329 columnCount = std::max(columnCount, overriddenColumnCount);
331 uint_fast64_t entryCount = currentEntryCount;
332 if (initialEntryCountSet && forceInitialDimensions) {
333 STORM_LOG_THROW(entryCount == initialEntryCount, storm::exceptions::InvalidStateException,
334 "Expected " << initialEntryCount <<
" entries, but got " << entryCount <<
".");
338 if (hasCustomRowGrouping) {
339 uint_fast64_t rowGroupCount = currentRowGroupCount;
340 if (initialRowGroupCountSet && forceInitialDimensions) {
341 STORM_LOG_THROW(rowGroupCount <= initialRowGroupCount, storm::exceptions::InvalidStateException,
342 "Expected not more than " << initialRowGroupCount <<
" row groups, but got " << rowGroupCount <<
".");
343 rowGroupCount = std::max(rowGroupCount, initialRowGroupCount);
345 rowGroupCount = std::max(rowGroupCount, overriddenRowGroupCount);
347 for (
index_type i = currentRowGroupCount;
i <= rowGroupCount; ++
i) {
348 rowGroupIndices.get().push_back(rowCount);
352 return SparseMatrix<ValueType>(columnCount, std::move(rowIndications), std::move(columnsAndValues), std::move(rowGroupIndices));
355template<
typename ValueType>
360template<
typename ValueType>
362 if (this->hasCustomRowGrouping) {
363 return currentRowGroupCount;
365 return getLastRow() + 1;
369template<
typename ValueType>
375template<
typename ValueType>
383 std::cout <<
"\t---- group " << group <<
"/" << (rowGroupIndices.size() - 1) <<
" ---- \n";
384 endGroups = group < rowGroupIndices.size() - 1 ? rowGroupIndices[group + 1] : rowIndications.size();
387 endRows =
i < rowIndications.size() - 1 ? rowIndications[
i + 1] : columnsAndValues.size();
389 std::cout <<
"Row " <<
i <<
" (" << rowIndications[
i] <<
" - " << endRows <<
")" <<
": ";
391 std::cout <<
"(" << columnsAndValues[pos].getColumn() <<
": " << columnsAndValues[pos].getValue() <<
") ";
398template<
typename ValueType>
402 for (
index_type row = 0; row < rowIndications.size(); ++row) {
403 bool changed =
false;
404 auto startRow = std::next(columnsAndValues.begin(), rowIndications[row]);
405 auto endRow = row < rowIndications.size() - 1 ? std::next(columnsAndValues.begin(), rowIndications[row + 1]) : columnsAndValues.end();
406 for (
auto entry = startRow; entry != endRow; ++entry) {
407 if (entry->getColumn() >= offset) {
409 entry->setColumn(replacements[entry->getColumn() - offset]);
412 maxColumn = std::max(maxColumn, entry->getColumn());
416 std::sort(startRow, endRow,
423 "Columns not sorted.");
427 highestColumn = maxColumn;
428 lastColumn = columnsAndValues.empty() ? 0 : columnsAndValues.back().getColumn();
431template<
typename ValueType>
433 STORM_LOG_THROW(row >= lastRow, storm::exceptions::InvalidArgumentException,
434 "Adding a diagonal element in row " << row <<
", but an element in row " << lastRow <<
" has already been added.");
435 if (pendingDiagonalEntry) {
436 if (row == lastRow) {
438 pendingDiagonalEntry.get() += value;
442 index_type column = hasCustomRowGrouping ? currentRowGroupCount - 1 : lastRow;
443 ValueType diagValue = std::move(pendingDiagonalEntry.get());
444 pendingDiagonalEntry = boost::none;
445 addNextValue(lastRow, column, diagValue);
448 pendingDiagonalEntry = value;
449 if (lastRow != row) {
450 assert(rowIndications.size() == lastRow + 1);
451 rowIndications.resize(row + 1, currentEntryCount);
457template<
typename ValueType>
462template<
typename ValueType>
464 return beginIterator;
467template<
typename ValueType>
469 return beginIterator + entryCount;
472template<
typename ValueType>
474 return this->entryCount;
477template<
typename ValueType>
482template<
typename ValueType>
484 return beginIterator;
487template<
typename ValueType>
489 return beginIterator + entryCount;
492template<
typename ValueType>
494 return this->entryCount;
497template<
typename ValueType>
499 : rowCount(0), columnCount(0), entryCount(0), nonzeroEntryCount(0), columnsAndValues(), rowIndications(), rowGroupIndices() {
503template<
typename ValueType>
505 : rowCount(other.rowCount),
506 columnCount(other.columnCount),
507 entryCount(other.entryCount),
508 nonzeroEntryCount(other.nonzeroEntryCount),
509 columnsAndValues(other.columnsAndValues),
510 rowIndications(other.rowIndications),
511 trivialRowGrouping(other.trivialRowGrouping),
512 rowGroupIndices(other.rowGroupIndices) {
516template<
typename ValueType>
520 *
this = other.
getSubmatrix(
false, rowConstraint, columnConstraint, insertDiagonalElements);
523template<
typename ValueType>
525 : rowCount(other.rowCount),
526 columnCount(other.columnCount),
527 entryCount(other.entryCount),
528 nonzeroEntryCount(other.nonzeroEntryCount),
529 columnsAndValues(
std::move(other.columnsAndValues)),
530 rowIndications(
std::move(other.rowIndications)),
531 trivialRowGrouping(other.trivialRowGrouping),
532 rowGroupIndices(
std::move(other.rowGroupIndices)) {
535 other.columnCount = 0;
536 other.entryCount = 0;
539template<
typename ValueType>
542 boost::optional<std::vector<index_type>>
const& rowGroupIndices)
543 : rowCount(rowIndications.size() - 1),
544 columnCount(columnCount),
545 entryCount(columnsAndValues.size()),
546 nonzeroEntryCount(0),
547 columnsAndValues(columnsAndValues),
548 rowIndications(rowIndications),
549 trivialRowGrouping(!rowGroupIndices),
550 rowGroupIndices(rowGroupIndices) {
551 this->updateNonzeroEntryCount();
554template<
typename ValueType>
557 boost::optional<std::vector<index_type>>&& rowGroupIndices)
558 : columnCount(columnCount),
559 nonzeroEntryCount(0),
560 columnsAndValues(
std::move(columnsAndValues)),
561 rowIndications(
std::move(rowIndications)),
562 rowGroupIndices(
std::move(rowGroupIndices)) {
565 this->rowCount = this->rowIndications.size() - 1;
566 this->entryCount = this->columnsAndValues.size();
567 this->trivialRowGrouping = !this->rowGroupIndices;
568 this->updateNonzeroEntryCount();
571template<
typename ValueType>
574 if (
this != &other) {
575 rowCount = other.rowCount;
576 columnCount = other.columnCount;
577 entryCount = other.entryCount;
578 nonzeroEntryCount = other.nonzeroEntryCount;
580 columnsAndValues = other.columnsAndValues;
581 rowIndications = other.rowIndications;
582 rowGroupIndices = other.rowGroupIndices;
583 trivialRowGrouping = other.trivialRowGrouping;
588template<
typename ValueType>
591 if (
this != &other) {
592 rowCount = other.rowCount;
593 columnCount = other.columnCount;
594 entryCount = other.entryCount;
595 nonzeroEntryCount = other.nonzeroEntryCount;
597 columnsAndValues = std::move(other.columnsAndValues);
598 rowIndications = std::move(other.rowIndications);
599 rowGroupIndices = std::move(other.rowGroupIndices);
600 trivialRowGrouping = other.trivialRowGrouping;
605template<
typename ValueType>
607 if (
this == &other) {
611 bool equalityResult =
true;
613 equalityResult &= this->getRowCount() == other.
getRowCount();
614 if (!equalityResult) {
618 if (!equalityResult) {
626 if (!equalityResult) {
633 for (
const_iterator it1 = this->begin(row), ite1 = this->end(row), it2 = other.
begin(row), ite2 = other.
end(row); it1 != ite1 && it2 != ite2;
642 if ((it1 == ite1) || (it2 == ite2)) {
643 equalityResult = (it1 == ite1) ^ (it2 == ite2);
646 if (it1->getColumn() != it2->getColumn() || it1->getValue() != it2->getValue()) {
647 equalityResult =
false;
652 if (!equalityResult) {
657 return equalityResult;
660template<
typename ValueType>
665template<
typename ValueType>
670template<
typename ValueType>
675template<
typename ValueType>
678 if (!this->hasTrivialRowGrouping()) {
679 for (
auto row : this->getRowGroupIndices(group)) {
680 result += (this->rowIndications[row + 1] - this->rowIndications[row]);
683 result += (this->rowIndications[group + 1] - this->rowIndications[group]);
688template<
typename ValueType>
690 return nonzeroEntryCount;
693template<
typename ValueType>
695 this->nonzeroEntryCount = 0;
696 for (
auto const& element : *
this) {
697 if (element.getValue() != storm::utility::zero<ValueType>()) {
698 ++this->nonzeroEntryCount;
703template<
typename ValueType>
705 this->nonzeroEntryCount += difference;
708template<
typename ValueType>
710 this->nonzeroEntryCount = 0;
711 this->columnCount = 0;
712 for (
auto const& element : *
this) {
713 if (element.getValue() != storm::utility::zero<ValueType>()) {
714 ++this->nonzeroEntryCount;
715 this->columnCount = std::max(element.getColumn() + 1, this->columnCount);
720template<
typename ValueType>
722 if (!this->hasTrivialRowGrouping()) {
723 return rowGroupIndices.get().size() - 1;
729template<
typename ValueType>
731 return this->getRowGroupIndices()[group + 1] - this->getRowGroupIndices()[group];
734template<
typename ValueType>
736 if (this->hasTrivialRowGrouping()) {
740 index_type previousGroupStart = 0;
741 for (
auto const&
i : rowGroupIndices.get()) {
742 res = std::max(res,
i - previousGroupStart);
743 previousGroupStart =
i;
748template<
typename ValueType>
750 if (this->hasTrivialRowGrouping()) {
753 index_type numRows = 0;
755 while (rowGroupIndex < this->getRowGroupCount()) {
756 index_type start = this->getRowGroupIndices()[rowGroupIndex];
758 index_type end = this->getRowGroupIndices()[rowGroupIndex];
760 numRows += end - start;
766template<
typename ValueType>
769 if (!this->rowGroupIndices) {
770 STORM_LOG_ASSERT(trivialRowGrouping,
"Only trivial row-groupings can be constructed on-the-fly.");
773 return rowGroupIndices.get();
776template<
typename ValueType>
779 "Invalid row group index:" << group <<
". Only " << this->getRowGroupCount() <<
" row groups available.");
780 if (this->rowGroupIndices) {
781 return boost::irange(rowGroupIndices.get()[group], rowGroupIndices.get()[group + 1]);
783 return boost::irange(group, group + 1);
787template<
typename ValueType>
789 std::vector<index_type> result;
790 if (this->rowGroupIndices) {
791 result = std::move(rowGroupIndices.get());
792 rowGroupIndices = std::move(newRowGrouping);
797template<
typename ValueType>
799 trivialRowGrouping =
false;
800 rowGroupIndices = newRowGroupIndices;
803template<
typename ValueType>
805 return trivialRowGrouping;
808template<
typename ValueType>
810 if (trivialRowGrouping) {
813 "Row grouping is supposed to be trivial but actually it is not.");
815 trivialRowGrouping =
true;
816 rowGroupIndices = boost::none;
820template<
typename ValueType>
823 for (
auto group : groupConstraint) {
824 res.setMultiple(getRowGroupIndices()[group], getRowGroupSize(group));
829template<
typename ValueType>
833 for (
auto group : groupConstraint) {
834 for (
auto row : this->getRowGroupIndices(group)) {
835 bool choiceSatisfiesColumnConstraint =
true;
836 for (
auto const& entry : this->getRow(row)) {
837 if (!columnConstraint.
get(entry.getColumn())) {
838 choiceSatisfiesColumnConstraint =
false;
842 if (choiceSatisfiesColumnConstraint) {
843 result.set(row,
true);
850template<
typename ValueType>
852 STORM_LOG_ASSERT(!this->hasTrivialRowGrouping(),
"Tried to get a row group filter but this matrix does not have row groups");
854 auto const& groupIndices = this->getRowGroupIndices();
855 if (setIfForAllRowsInGroup) {
856 for (uint64_t group = 0; group < this->getRowGroupCount(); ++group) {
857 if (rowConstraint.
getNextUnsetIndex(groupIndices[group]) >= groupIndices[group + 1]) {
859 result.set(group,
true);
863 for (uint64_t group = 0; group < this->getRowGroupCount(); ++group) {
864 if (rowConstraint.
getNextSetIndex(groupIndices[group]) < groupIndices[group + 1]) {
866 result.set(group,
true);
873template<
typename ValueType>
877 for (
auto row :
rows) {
878 makeRowDirac(row, row,
false);
880 if (dropZeroEntries) {
881 this->dropZeroEntries();
885template<
typename ValueType>
889 if (!this->hasTrivialRowGrouping()) {
890 for (
auto rowGroup : rowGroupConstraint) {
891 for (
index_type row = this->getRowGroupIndices()[rowGroup]; row < this->getRowGroupIndices()[rowGroup + 1]; ++row) {
892 makeRowDirac(row, rowGroup,
false);
896 for (
auto rowGroup : rowGroupConstraint) {
897 makeRowDirac(rowGroup, rowGroup,
false);
900 if (dropZeroEntries) {
901 this->dropZeroEntries();
905template<
typename ValueType>
908 iterator columnValuePtrEnd = this->end(row);
912 if (columnValuePtr >= columnValuePtrEnd) {
913 throw storm::exceptions::InvalidStateException()
914 <<
"Illegal call to SparseMatrix::makeRowDirac: cannot make row " << row <<
" absorbing, because there is no entry in this row.";
916 iterator lastColumnValuePtr = this->end(row) - 1;
921 while (columnValuePtr->getColumn() < column && columnValuePtr != lastColumnValuePtr) {
923 --this->nonzeroEntryCount;
925 columnValuePtr->setValue(storm::utility::zero<ValueType>());
930 ++this->nonzeroEntryCount;
932 columnValuePtr->setValue(storm::utility::one<ValueType>());
933 columnValuePtr->setColumn(column);
934 for (++columnValuePtr; columnValuePtr != columnValuePtrEnd; ++columnValuePtr) {
936 --this->nonzeroEntryCount;
938 columnValuePtr->setValue(storm::utility::zero<ValueType>());
940 if (dropZeroEntries) {
941 this->dropZeroEntries();
945template<
typename ValueType>
951 for (; it1 != end1 && it2 != end2; ++it1, ++it2) {
956 if (it1 == end1 && it2 == end2) {
962template<
typename ValueType>
965 for (
size_t rowgroup = 0; rowgroup < this->getRowGroupCount(); ++rowgroup) {
966 for (
size_t row1 = this->getRowGroupIndices().at(rowgroup); row1 < this->getRowGroupIndices().at(rowgroup + 1); ++row1) {
967 for (
size_t row2 = row1; row2 < this->getRowGroupIndices().at(rowgroup + 1); ++row2) {
968 if (compareRows(row1, row2)) {
977template<
typename ValueType>
984 index_type largerRow = getRow(row1).getNumberOfEntries() > getRow(row2).getNumberOfEntries() ? row1 : row2;
985 index_type smallerRow = largerRow == row1 ? row2 : row1;
986 index_type rowSizeDifference = getRow(largerRow).getNumberOfEntries() - getRow(smallerRow).getNumberOfEntries();
989 auto copyRow = getRow(largerRow);
990 std::vector<MatrixEntry<index_type, value_type>> largerRowContents(copyRow.begin(), copyRow.end());
992 if (largerRow < smallerRow) {
993 auto writeIt = getRows(largerRow, smallerRow + 1).begin();
996 for (
auto& smallerRowEntry : getRow(smallerRow)) {
997 *writeIt = std::move(smallerRowEntry);
1003 for (
auto& intermediateRowEntry : getRows(largerRow + 1, smallerRow)) {
1004 *writeIt = std::move(intermediateRowEntry);
1009 writeIt = getRow(smallerRow).begin();
1013 for (
auto& largerRowEntry : largerRowContents) {
1014 *writeIt = std::move(largerRowEntry);
1018 STORM_LOG_ASSERT(writeIt == getRow(smallerRow).end(),
"Unexpected position of write iterator.");
1022 for (
index_type row = largerRow + 1; row <= smallerRow; ++row) {
1023 rowIndications[row] -= rowSizeDifference;
1027 auto writeIt = getRows(smallerRow, largerRow + 1).end() - 1;
1030 auto copyRow = getRow(smallerRow);
1031 for (
auto smallerRowEntryIt = copyRow.end() - 1; smallerRowEntryIt != copyRow.begin() - 1; --smallerRowEntryIt) {
1032 *writeIt = std::move(*smallerRowEntryIt);
1038 for (
auto intermediateRowEntryIt = getRows(smallerRow + 1, largerRow).end() - 1;
1039 intermediateRowEntryIt != getRows(smallerRow + 1, largerRow).begin() - 1; --intermediateRowEntryIt) {
1040 *writeIt = std::move(*intermediateRowEntryIt);
1045 writeIt = getRow(smallerRow).end() - 1;
1049 for (
auto largerRowEntryIt = largerRowContents.rbegin(); largerRowEntryIt != largerRowContents.rend(); ++largerRowEntryIt) {
1050 *writeIt = std::move(*largerRowEntryIt);
1054 STORM_LOG_ASSERT(writeIt == getRow(smallerRow).begin() - 1,
"Unexpected position of write iterator.");
1059 for (
index_type row = smallerRow + 1; row <= largerRow; ++row) {
1060 rowIndications[row] += rowSizeDifference;
1066template<
typename ValueType>
1068 std::vector<ValueType> result(this->getRowCount());
1071 for (
auto resultIt = result.begin(), resultIte = result.end(); resultIt != resultIte; ++resultIt, ++row) {
1072 *resultIt = getRowSum(row);
1078template<
typename ValueType>
1080 ValueType result = storm::utility::zero<ValueType>();
1081 for (
const_iterator it = this->begin(row), ite = this->end(row); it != ite; ++it) {
1082 if (constraint.
get(it->getColumn())) {
1083 result += it->getValue();
1089template<
typename ValueType>
1094 for (
auto row : rowConstraint) {
1095 result[currentRowCount++] = getConstrainedRowSum(row, columnConstraint);
1100template<
typename ValueType>
1103 std::vector<ValueType> result;
1104 result.reserve(this->getNumRowsInRowGroups(rowGroupConstraint));
1105 if (!this->hasTrivialRowGrouping()) {
1106 for (
auto rowGroup : rowGroupConstraint) {
1107 for (
index_type row = this->getRowGroupIndices()[rowGroup]; row < this->getRowGroupIndices()[rowGroup + 1]; ++row) {
1108 result.push_back(getConstrainedRowSum(row, columnConstraint));
1112 for (
auto rowGroup : rowGroupConstraint) {
1113 result.push_back(getConstrainedRowSum(rowGroup, columnConstraint));
1119template<
typename ValueType>
1124 return getSubmatrix(rowConstraint, columnConstraint, this->getRowGroupIndices(), insertDiagonalElements, makeZeroColumns);
1127 std::vector<index_type> fakeRowGroupIndices(rowCount + 1);
1129 for (std::vector<index_type>::iterator it = fakeRowGroupIndices.begin(); it != fakeRowGroupIndices.end(); ++it, ++
i) {
1132 auto res = getSubmatrix(rowConstraint, columnConstraint, fakeRowGroupIndices, insertDiagonalElements, makeZeroColumns);
1136 if (!this->hasTrivialRowGrouping()) {
1137 std::vector<index_type> newRowGroupIndices;
1138 newRowGroupIndices.push_back(0);
1139 auto selectedRowIt = rowConstraint.
begin();
1142 for (
index_type group = 0; group < this->getRowGroupCount(); ++group) {
1144 while (*selectedRowIt < this->getRowGroupIndices()[group + 1]) {
1148 if (newRowCount > 0) {
1149 newRowGroupIndices.push_back(newRowGroupIndices.back() + newRowCount);
1153 res.trivialRowGrouping =
false;
1154 res.rowGroupIndices = newRowGroupIndices;
1161template<
typename ValueType>
1165 STORM_LOG_THROW(!rowGroupConstraint.
empty() && !columnConstraint.
empty(), storm::exceptions::InvalidArgumentException,
"Cannot build empty submatrix.");
1171 std::unique_ptr<std::vector<index_type>> tmp;
1172 if (rowGroupConstraint != columnConstraint) {
1175 std::vector<index_type>
const& rowBitsSetBeforeIndex = tmp ? *tmp : columnBitsSetBeforeIndex;
1178 index_type subEntries = 0;
1179 index_type subRows = 0;
1180 index_type rowGroupCount = 0;
1181 for (
auto index : rowGroupConstraint) {
1182 subRows += rowGroupIndices[index + 1] - rowGroupIndices[index];
1183 for (
index_type i = rowGroupIndices[index];
i < rowGroupIndices[index + 1]; ++
i) {
1184 bool foundDiagonalElement =
false;
1186 for (
const_iterator it = this->begin(
i), ite = this->end(
i); it != ite; ++it) {
1187 if (columnConstraint.
get(it->getColumn()) && (makeZeroColumns.
size() == 0 || !makeZeroColumns.
get(it->getColumn()))) {
1190 if (columnBitsSetBeforeIndex[it->getColumn()] == rowBitsSetBeforeIndex[index]) {
1191 foundDiagonalElement =
true;
1197 if (insertDiagonalEntries && !foundDiagonalElement && rowGroupCount < submatrixColumnCount) {
1205 SparseMatrixBuilder<ValueType> matrixBuilder(subRows, submatrixColumnCount, subEntries,
true, !this->hasTrivialRowGrouping());
1211 for (
auto index : rowGroupConstraint) {
1212 if (!this->hasTrivialRowGrouping()) {
1213 matrixBuilder.newRowGroup(rowCount);
1215 for (index_type
i = rowGroupIndices[index];
i < rowGroupIndices[index + 1]; ++
i) {
1216 bool insertedDiagonalElement =
false;
1218 for (const_iterator it = this->begin(
i), ite = this->end(
i); it !=
ite; ++it) {
1219 if (columnConstraint.
get(it->getColumn()) && (makeZeroColumns.
size() == 0 || !makeZeroColumns.
get(it->getColumn()))) {
1220 if (columnBitsSetBeforeIndex[it->getColumn()] == rowBitsSetBeforeIndex[index]) {
1221 insertedDiagonalElement =
true;
1222 }
else if (insertDiagonalEntries && !insertedDiagonalElement && columnBitsSetBeforeIndex[it->getColumn()] > rowBitsSetBeforeIndex[index]) {
1223 matrixBuilder.addNextValue(rowCount, rowGroupCount, storm::utility::zero<ValueType>());
1224 insertedDiagonalElement =
true;
1227 matrixBuilder.addNextValue(rowCount, columnBitsSetBeforeIndex[it->getColumn()], it->getValue());
1230 if (insertDiagonalEntries && !insertedDiagonalElement && rowGroupCount < submatrixColumnCount) {
1231 matrixBuilder.addNextValue(rowCount, rowGroupCount, storm::utility::zero<ValueType>());
1238 return matrixBuilder.build();
1241template<
typename ValueType>
1247 for (
auto row : rowsToKeep) {
1248 entryCount += this->getRow(row).getNumberOfEntries();
1252 index_type firstTrailingEmptyRowGroup = this->getRowGroupCount();
1253 for (
auto groupIndexIt = this->getRowGroupIndices().rbegin() + 1; groupIndexIt != this->getRowGroupIndices().rend(); ++groupIndexIt) {
1257 --firstTrailingEmptyRowGroup;
1259 STORM_LOG_THROW(allowEmptyRowGroups || firstTrailingEmptyRowGroup == this->getRowGroupCount(), storm::exceptions::InvalidArgumentException,
1260 "Empty rows are not allowed, but row group " << firstTrailingEmptyRowGroup <<
" is empty.");
1265 for (
index_type rowGroup = 0; rowGroup < firstTrailingEmptyRowGroup; ++rowGroup) {
1268 bool rowGroupEmpty =
true;
1269 for (
index_type row = rowsToKeep.
getNextSetIndex(this->getRowGroupIndices()[rowGroup]); row < this->getRowGroupIndices()[rowGroup + 1];
1271 rowGroupEmpty =
false;
1272 for (
auto const& entry : this->getRow(row)) {
1273 builder.
addNextValue(newRow, entry.getColumn(), entry.getValue());
1277 STORM_LOG_THROW(allowEmptyRowGroups || !rowGroupEmpty, storm::exceptions::InvalidArgumentException,
1278 "Empty rows are not allowed, but row group " << rowGroup <<
" is empty.");
1286template<
typename ValueType>
1290 for (
auto row : rowFilter) {
1291 entryCount += getRow(row).getNumberOfEntries();
1296 for (
auto row : rowFilter) {
1297 for (
auto const& entry : getRow(row)) {
1298 builder.
addNextValue(row, entry.getColumn(), entry.getValue());
1304 if (!hasTrivialRowGrouping()) {
1310template<
typename ValueType>
1312 updateNonzeroEntryCount();
1313 if (getNonzeroEntryCount() != getEntryCount()) {
1315 for (
index_type row = 0; row < getRowCount(); ++row) {
1316 for (
auto const& entry : getRow(row)) {
1318 builder.
addNextValue(row, entry.getColumn(), entry.getValue());
1324 if (!hasTrivialRowGrouping()) {
1327 *
this = std::move(result);
1331template<
typename ValueType>
1333 bool insertDiagonalEntries)
const {
1337 for (
index_type rowGroupIndex = 0, rowGroupIndexEnd = rowGroupToRowIndexMapping.size(); rowGroupIndex < rowGroupIndexEnd; ++rowGroupIndex) {
1339 STORM_LOG_ASSERT(rowGroupToRowIndexMapping[rowGroupIndex] < this->getRowGroupSize(rowGroupIndex),
1340 "Cannot point to row offset " << rowGroupToRowIndexMapping[rowGroupIndex] <<
" for rowGroup " << rowGroupIndex <<
" which starts at "
1341 << this->getRowGroupIndices()[rowGroupIndex] <<
" and ends at "
1342 << this->getRowGroupIndices()[rowGroupIndex + 1] <<
".");
1343 index_type rowToCopy = this->getRowGroupIndices()[rowGroupIndex] + rowGroupToRowIndexMapping[rowGroupIndex];
1346 bool foundDiagonalElement =
false;
1347 for (
const_iterator it = this->begin(rowToCopy), ite = this->end(rowToCopy); it != ite; ++it) {
1348 if (it->getColumn() == rowGroupIndex) {
1349 foundDiagonalElement =
true;
1353 if (insertDiagonalEntries && !foundDiagonalElement) {
1362 for (
index_type rowGroupIndex = 0, rowGroupIndexEnd = rowGroupToRowIndexMapping.size(); rowGroupIndex < rowGroupIndexEnd; ++rowGroupIndex) {
1364 index_type rowToCopy = this->getRowGroupIndices()[rowGroupIndex] + rowGroupToRowIndexMapping[rowGroupIndex];
1368 bool insertedDiagonalElement =
false;
1369 for (
const_iterator it = this->begin(rowToCopy), ite = this->end(rowToCopy); it != ite; ++it) {
1370 if (it->getColumn() == rowGroupIndex) {
1371 insertedDiagonalElement =
true;
1372 }
else if (insertDiagonalEntries && !insertedDiagonalElement && it->getColumn() > rowGroupIndex) {
1373 matrixBuilder.
addNextValue(rowGroupIndex, rowGroupIndex, storm::utility::zero<ValueType>());
1374 insertedDiagonalElement =
true;
1376 matrixBuilder.
addNextValue(rowGroupIndex, it->getColumn(), it->getValue());
1378 if (insertDiagonalEntries && !insertedDiagonalElement) {
1379 matrixBuilder.
addNextValue(rowGroupIndex, rowGroupIndex, storm::utility::zero<ValueType>());
1384 return matrixBuilder.
build();
1387template<
typename ValueType>
1389 bool insertDiagonalEntries)
const {
1393 for (
index_type row = 0, rowEnd = rowIndexSequence.size(); row < rowEnd; ++row) {
1394 bool foundDiagonalElement =
false;
1395 for (
const_iterator it = this->begin(rowIndexSequence[row]), ite = this->end(rowIndexSequence[row]); it != ite; ++it) {
1396 if (it->getColumn() == row) {
1397 foundDiagonalElement =
true;
1401 if (insertDiagonalEntries && !foundDiagonalElement) {
1410 for (
index_type row = 0, rowEnd = rowIndexSequence.size(); row < rowEnd; ++row) {
1411 bool insertedDiagonalElement =
false;
1412 for (
const_iterator it = this->begin(rowIndexSequence[row]), ite = this->end(rowIndexSequence[row]); it != ite; ++it) {
1413 if (it->getColumn() == row) {
1414 insertedDiagonalElement =
true;
1415 }
else if (insertDiagonalEntries && !insertedDiagonalElement && it->getColumn() > row) {
1416 matrixBuilder.
addNextValue(row, row, storm::utility::zero<ValueType>());
1417 insertedDiagonalElement =
true;
1419 matrixBuilder.
addNextValue(row, it->getColumn(), it->getValue());
1421 if (insertDiagonalEntries && !insertedDiagonalElement) {
1422 matrixBuilder.
addNextValue(row, row, storm::utility::zero<ValueType>());
1427 return matrixBuilder.
build();
1430template<
typename ValueType>
1438 for (
index_type writeTo = 0; writeTo < inversePermutation.size(); ++writeTo) {
1439 index_type const& readFrom = inversePermutation[writeTo];
1440 auto row = this->getRow(readFrom);
1441 for (
auto const& entry : row) {
1442 matrixBuilder.
addNextValue(writeTo, entry.getColumn(), entry.getValue());
1446 auto result = matrixBuilder.
build();
1447 if (this->rowGroupIndices) {
1448 result.setRowGroupIndices(this->rowGroupIndices.get());
1453template<
typename ValueType>
1455 std::vector<index_type>
const& columnPermutation)
const {
1460 auto oldGroupIt = inverseRowGroupPermutation.cbegin();
1462 while (newRowIndex < rowCount) {
1463 if (!hasTrivialRowGrouping()) {
1466 for (
auto oldRowIndex : getRowGroupIndices(*oldGroupIt)) {
1467 for (
auto const& oldEntry : getRow(oldRowIndex)) {
1468 matrixBuilder.
addNextValue(newRowIndex, columnPermutation[oldEntry.getColumn()], oldEntry.getValue());
1474 return matrixBuilder.
build();
1477template<
typename ValueType>
1479 index_type rowCount = this->getColumnCount();
1480 index_type columnCount = joinGroups ? this->getRowGroupCount() : this->getRowCount();
1483 entryCount = this->getEntryCount();
1485 this->updateNonzeroEntryCount();
1486 entryCount = this->getNonzeroEntryCount();
1489 std::vector<index_type> rowIndications(rowCount + 1);
1490 std::vector<MatrixEntry<index_type, ValueType>> columnsAndValues(entryCount);
1493 for (
index_type group = 0; group < columnCount; ++group) {
1494 for (
auto const& transition : joinGroups ? this->getRowGroup(group) : this->getRow(group)) {
1495 if (transition.getValue() != storm::utility::zero<ValueType>() || keepZeros) {
1496 ++rowIndications[transition.getColumn() + 1];
1503 rowIndications[
i] = rowIndications[
i - 1] + rowIndications[
i];
1509 std::vector<index_type> nextIndices = rowIndications;
1512 for (
index_type group = 0; group < columnCount; ++group) {
1513 for (
auto const& transition : joinGroups ? this->getRowGroup(group) : this->getRow(group)) {
1514 if (transition.getValue() != storm::utility::zero<ValueType>() || keepZeros) {
1515 columnsAndValues[nextIndices[transition.getColumn()]] = std::make_pair(group, transition.getValue());
1516 nextIndices[transition.getColumn()]++;
1523 return transposedMatrix;
1526template<
typename ValueType>
1528 index_type rowCount = this->getColumnCount();
1529 index_type columnCount = this->getRowGroupCount();
1533 std::vector<index_type> rowIndications(columnCount + 1);
1534 auto rowGroupChoiceIt = rowGroupChoices.begin();
1535 for (
index_type rowGroup = 0; rowGroup < columnCount; ++rowGroup, ++rowGroupChoiceIt) {
1536 for (
auto const& entry : this->getRow(rowGroup, *rowGroupChoiceIt)) {
1539 ++rowIndications[entry.getColumn() + 1];
1546 rowIndications[
i] = rowIndications[
i - 1] + rowIndications[
i];
1549 std::vector<MatrixEntry<index_type, ValueType>> columnsAndValues(entryCount);
1554 std::vector<index_type> nextIndices = rowIndications;
1557 rowGroupChoiceIt = rowGroupChoices.begin();
1558 for (
index_type rowGroup = 0; rowGroup < columnCount; ++rowGroup, ++rowGroupChoiceIt) {
1559 for (
auto const& entry : this->getRow(rowGroup, *rowGroupChoiceIt)) {
1561 columnsAndValues[nextIndices[entry.getColumn()]] = std::make_pair(rowGroup, entry.getValue());
1562 ++nextIndices[entry.getColumn()];
1570template<
typename ValueType>
1573 negateAllNonDiagonalEntries();
1576template<
typename ValueType>
1580 ValueType one = storm::utility::one<ValueType>();
1581 ValueType zero = storm::utility::zero<ValueType>();
1582 bool foundDiagonalElement =
false;
1583 for (
index_type group = 0; group < this->getRowGroupCount(); ++group) {
1584 for (
auto& entry : this->getRowGroup(group)) {
1585 if (entry.getColumn() == group) {
1586 if (entry.getValue() == one) {
1587 --this->nonzeroEntryCount;
1588 entry.setValue(zero);
1589 }
else if (entry.getValue() == zero) {
1590 ++this->nonzeroEntryCount;
1591 entry.setValue(one);
1593 entry.setValue(one - entry.getValue());
1595 foundDiagonalElement =
true;
1600 if (!foundDiagonalElement) {
1601 throw storm::exceptions::InvalidArgumentException() <<
"Illegal call to SparseMatrix::invertDiagonal: matrix is missing diagonal entries.";
1606template<
typename ValueType>
1609 for (
index_type group = 0; group < this->getRowGroupCount(); ++group) {
1610 for (
auto& entry : this->getRowGroup(group)) {
1611 if (entry.getColumn() != group) {
1612 entry.setValue(-entry.getValue());
1618template<
typename ValueType>
1621 for (
index_type group = 0; group < this->getRowGroupCount(); ++group) {
1622 for (
auto& entry : this->getRowGroup(group)) {
1623 if (entry.getColumn() == group) {
1624 --this->nonzeroEntryCount;
1625 entry.setValue(storm::utility::zero<ValueType>());
1629 if (dropZeroEntries) {
1630 this->dropZeroEntries();
1634template<
typename ValueType>
1636 STORM_LOG_THROW(this->getRowCount() == this->getColumnCount(), storm::exceptions::InvalidArgumentException,
1637 "Canno compute Jacobi decomposition of non-square matrix.");
1641 std::vector<ValueType> invertedDiagonal(rowCount);
1644 for (
index_type rowNumber = 0; rowNumber < rowCount; ++rowNumber) {
1645 for (
const_iterator it = this->begin(rowNumber), ite = this->end(rowNumber); it != ite; ++it) {
1646 if (it->getColumn() == rowNumber) {
1647 invertedDiagonal[rowNumber] = storm::utility::one<ValueType>() / it->getValue();
1649 luBuilder.
addNextValue(rowNumber, it->getColumn(), it->getValue());
1654 return std::make_pair(luBuilder.
build(), std::move(invertedDiagonal));
1657#ifdef STORM_HAVE_CARL
1660 STORM_LOG_THROW(
false, storm::exceptions::NotImplementedException,
"This operation is not supported.");
1666 STORM_LOG_THROW(
false, storm::exceptions::NotImplementedException,
"This operation is not supported.");
1670template<
typename ValueType>
1671template<
typename OtherValueType,
typename ResultValueType>
1679 ResultValueType result = storm::utility::zero<ResultValueType>();
1680 for (; it1 != ite1 && it2 != ite2; ++it1) {
1681 if (it1->getColumn() < it2->getColumn()) {
1687 STORM_LOG_ASSERT(it1->getColumn() == it2->getColumn(),
"The given matrix is not a submatrix of this one.");
1688 result += it2->getValue() * OtherValueType(it1->getValue());
1695template<
typename ValueType>
1696template<
typename OtherValueType,
typename ResultValueType>
1698 std::vector<ResultValueType> result;
1699 result.reserve(rowCount);
1701 result.push_back(getPointwiseProductRowSum<OtherValueType, ResultValueType>(otherMatrix, row));
1706template<
typename ValueType>
1708 std::vector<value_type>
const* summand)
const {
1710 std::vector<ValueType>* target;
1711 std::vector<ValueType> temporary;
1712 if (&vector == &result) {
1713 STORM_LOG_WARN(
"Vectors are aliased. Using temporary, which is potentially slow.");
1714 temporary = std::vector<ValueType>(vector.size());
1715 target = &temporary;
1720 this->multiplyWithVectorForward(vector, *target, summand);
1722 if (target == &temporary) {
1723 std::swap(result, *target);
1727template<
typename ValueType>
1729 std::vector<value_type>
const* summand)
const {
1732 std::vector<index_type>::const_iterator rowIterator = rowIndications.begin();
1733 typename std::vector<ValueType>::iterator resultIterator = result.begin();
1734 typename std::vector<ValueType>::iterator resultIteratorEnd = result.end();
1735 typename std::vector<ValueType>::const_iterator summandIterator;
1737 summandIterator = summand->begin();
1740 for (; resultIterator != resultIteratorEnd; ++rowIterator, ++resultIterator, ++summandIterator) {
1743 newValue = *summandIterator;
1745 newValue = storm::utility::zero<ValueType>();
1748 for (ite = this->begin() + *(rowIterator + 1); it != ite; ++it) {
1749 newValue += it->getValue() * vector[it->getColumn()];
1752 *resultIterator = newValue;
1756template<
typename ValueType>
1758 std::vector<value_type>
const* summand)
const {
1761 std::vector<index_type>::const_iterator rowIterator = rowIndications.end() - 2;
1762 typename std::vector<ValueType>::iterator resultIterator = result.end() - 1;
1763 typename std::vector<ValueType>::iterator resultIteratorEnd = result.begin() - 1;
1764 typename std::vector<ValueType>::const_iterator summandIterator;
1766 summandIterator = summand->end() - 1;
1769 for (; resultIterator != resultIteratorEnd; --rowIterator, --resultIterator, --summandIterator) {
1772 newValue = *summandIterator;
1774 newValue = storm::utility::zero<ValueType>();
1777 for (ite = this->begin() + *rowIterator - 1; it != ite; --it) {
1778 newValue += (it->getValue() * vector[it->getColumn()]);
1781 *resultIterator = newValue;
1785template<
typename ValueType>
1787 ValueType result = storm::utility::zero<ValueType>();
1789 for (
auto const& entry : this->getRow(row)) {
1790 result += entry.getValue() * vector[entry.getColumn()];
1795template<
typename ValueType>
1799 std::vector<index_type>::const_iterator rowIterator = rowIndications.end() - 2;
1800 typename std::vector<ValueType>::const_iterator bIt = b.end() - 1;
1801 typename std::vector<ValueType>::iterator resultIterator = x.end() - 1;
1802 typename std::vector<ValueType>::iterator resultIteratorEnd = x.begin() - 1;
1805 for (; resultIterator != resultIteratorEnd; --rowIterator, --resultIterator, --bIt) {
1807 ValueType tmpValue = storm::utility::zero<ValueType>();
1808 ValueType diagonalElement = storm::utility::zero<ValueType>();
1810 for (ite = this->begin() + *rowIterator - 1; it != ite; --it) {
1811 if (it->getColumn() != currentRow) {
1812 tmpValue += it->getValue() * x[it->getColumn()];
1814 diagonalElement += it->getValue();
1818 *resultIterator = ((storm::utility::one<ValueType>() - omega) * *resultIterator) + (omega / diagonalElement) * (*bIt - tmpValue);
1822#ifdef STORM_HAVE_CARL
1825 STORM_LOG_THROW(
false, storm::exceptions::NotSupportedException,
"This operation is not supported.");
1829template<
typename ValueType>
1831 std::vector<ValueType>
const& ax, std::vector<ValueType>& result)
const {
1834 std::vector<index_type>::const_iterator rowIterator = rowIndications.begin();
1837 ValueType zero = storm::utility::zero<ValueType>();
1838 for (
auto& entry : result) {
1842 for (
index_type row = 0; row < rowCount; ++row, ++rowIterator) {
1843 for (ite = this->begin() + *(rowIterator + 1); it != ite; ++it) {
1844 result[it->getColumn()] += it->getValue() * (b[row] / ax[row]);
1848 auto xIterator = x.begin();
1849 auto sumsIterator = columnSums.begin();
1850 for (
auto& entry : result) {
1851 entry *= *xIterator / *sumsIterator;
1859 std::vector<Interval>
const& ax, std::vector<Interval>& result)
const {
1860 STORM_LOG_THROW(
false, storm::exceptions::NotSupportedException,
"This operation is not supported.");
1863template<
typename ValueType>
1865 std::vector<ValueType>
const& vector, std::vector<ValueType>
const* summand,
1866 std::vector<ValueType>& result, std::vector<uint64_t>* choices)
const {
1867 if (dir == OptimizationDirection::Minimize) {
1868 multiplyAndReduceForward<storm::utility::ElementLess<ValueType>>(rowGroupIndices, vector, summand, result, choices);
1870 multiplyAndReduceForward<storm::utility::ElementGreater<ValueType>>(rowGroupIndices, vector, summand, result, choices);
1874template<
typename ValueType>
1875template<
typename Compare>
1877 std::vector<ValueType>
const* summand, std::vector<ValueType>& result,
1878 std::vector<uint64_t>* choices)
const {
1880 auto elementIt = this->begin();
1881 auto rowGroupIt = rowGroupIndices.begin();
1882 auto rowIt = rowIndications.begin();
1883 typename std::vector<ValueType>::const_iterator summandIt;
1885 summandIt = summand->begin();
1887 typename std::vector<uint64_t>::iterator choiceIt;
1889 choiceIt = choices->begin();
1893 ValueType oldSelectedChoiceValue;
1894 uint64_t selectedChoice;
1896 uint64_t currentRow = 0;
1897 for (
auto resultIt = result.begin(), resultIte = result.end(); resultIt != resultIte; ++resultIt, ++choiceIt, ++rowGroupIt) {
1898 ValueType currentValue = storm::utility::zero<ValueType>();
1901 if (*rowGroupIt < *(rowGroupIt + 1)) {
1903 currentValue = *summandIt;
1907 for (
auto elementIte = this->begin() + *(rowIt + 1); elementIt != elementIte; ++elementIt) {
1908 currentValue += elementIt->getValue() * vector[elementIt->getColumn()];
1913 if (*choiceIt == 0) {
1914 oldSelectedChoiceValue = currentValue;
1921 for (; currentRow < *(rowGroupIt + 1); ++rowIt, ++currentRow) {
1922 ValueType newValue = summand ? *summandIt : storm::utility::zero<ValueType>();
1923 for (
auto elementIte = this->begin() + *(rowIt + 1); elementIt != elementIte; ++elementIt) {
1924 newValue += elementIt->getValue() * vector[elementIt->getColumn()];
1927 if (choices && currentRow == *choiceIt + *rowGroupIt) {
1928 oldSelectedChoiceValue = newValue;
1931 if (compare(newValue, currentValue)) {
1932 currentValue = newValue;
1934 selectedChoice = currentRow - *rowGroupIt;
1943 *resultIt = currentValue;
1944 if (choices && compare(currentValue, oldSelectedChoiceValue)) {
1945 *choiceIt = selectedChoice;
1953 std::vector<storm::RationalFunction>
const& vector,
1954 std::vector<storm::RationalFunction>
const* b,
1955 std::vector<storm::RationalFunction>& result, std::vector<uint64_t>* choices)
const {
1956 STORM_LOG_THROW(
false, storm::exceptions::NotSupportedException,
"This operation is not supported.");
1959template<
typename ValueType>
1961 std::vector<ValueType>
const& vector, std::vector<ValueType>
const* summand,
1962 std::vector<ValueType>& result, std::vector<uint64_t>* choices)
const {
1963 if (dir == storm::OptimizationDirection::Minimize) {
1964 multiplyAndReduceBackward<storm::utility::ElementLess<ValueType>>(rowGroupIndices, vector, summand, result, choices);
1966 multiplyAndReduceBackward<storm::utility::ElementGreater<ValueType>>(rowGroupIndices, vector, summand, result, choices);
1970template<
typename ValueType>
1971template<
typename Compare>
1973 std::vector<ValueType>
const* summand, std::vector<ValueType>& result,
1974 std::vector<uint64_t>* choices)
const {
1976 auto elementIt = this->end() - 1;
1977 auto rowGroupIt = rowGroupIndices.end() - 2;
1978 auto rowIt = rowIndications.end() - 2;
1979 typename std::vector<ValueType>::const_iterator summandIt;
1981 summandIt = summand->end() - 1;
1983 typename std::vector<uint64_t>::iterator choiceIt;
1985 choiceIt = choices->end() - 1;
1989 ValueType oldSelectedChoiceValue;
1990 uint64_t selectedChoice;
1992 uint64_t currentRow = this->getRowCount() - 1;
1993 for (
auto resultIt = result.end() - 1, resultIte = result.begin() - 1; resultIt != resultIte; --resultIt, --choiceIt, --rowGroupIt) {
1994 ValueType currentValue = storm::utility::zero<ValueType>();
1997 if (*rowGroupIt < *(rowGroupIt + 1)) {
1999 currentValue = *summandIt;
2003 for (
auto elementIte = this->begin() + *rowIt - 1; elementIt != elementIte; --elementIt) {
2004 currentValue += elementIt->getValue() * vector[elementIt->getColumn()];
2007 selectedChoice = currentRow - *rowGroupIt;
2008 if (*choiceIt == selectedChoice) {
2009 oldSelectedChoiceValue = currentValue;
2015 for (uint64_t
i = *rowGroupIt + 1, end = *(rowGroupIt + 1);
i < end; --rowIt, --currentRow, ++
i, --summandIt) {
2016 ValueType newValue = summand ? *summandIt : storm::utility::zero<ValueType>();
2017 for (
auto elementIte = this->begin() + *rowIt - 1; elementIt != elementIte; --elementIt) {
2018 newValue += elementIt->getValue() * vector[elementIt->getColumn()];
2021 if (choices && currentRow == *choiceIt + *rowGroupIt) {
2022 oldSelectedChoiceValue = newValue;
2025 if (compare(newValue, currentValue)) {
2026 currentValue = newValue;
2028 selectedChoice = currentRow - *rowGroupIt;
2034 *resultIt = currentValue;
2035 if (choices && compare(currentValue, oldSelectedChoiceValue)) {
2036 *choiceIt = selectedChoice;
2044 std::vector<storm::RationalFunction>
const& vector,
2045 std::vector<storm::RationalFunction>
const* b,
2046 std::vector<storm::RationalFunction>& result, std::vector<uint64_t>* choices)
const {
2047 STORM_LOG_THROW(
false, storm::exceptions::NotSupportedException,
"This operation is not supported.");
2050template<
typename ValueType>
2052 std::vector<ValueType>
const& vector, std::vector<ValueType>
const* summand, std::vector<ValueType>& result,
2053 std::vector<uint64_t>* choices)
const {
2055 std::vector<ValueType>* target;
2056 std::vector<ValueType> temporary;
2057 if (&vector == &result) {
2058 STORM_LOG_WARN(
"Vectors are aliased but are not allowed to be. Using temporary, which is potentially slow.");
2059 temporary = std::vector<ValueType>(vector.size());
2060 target = &temporary;
2065 this->multiplyAndReduceForward(dir, rowGroupIndices, vector, summand, *target, choices);
2067 if (target == &temporary) {
2068 std::swap(temporary, result);
2072template<
typename ValueType>
2076 std::vector<index_type>::const_iterator rowIterator = rowIndications.begin();
2077 std::vector<index_type>::const_iterator rowIteratorEnd = rowIndications.end();
2080 for (; rowIterator != rowIteratorEnd - 1; ++rowIterator) {
2081 for (ite = this->begin() + *(rowIterator + 1); it != ite; ++it) {
2082 result[it->getColumn()] += it->getValue() * vector[currentRow];
2088template<
typename ValueType>
2090 STORM_LOG_ASSERT(factors.size() == this->getRowCount(),
"Can not scale rows: Number of rows and number of scaling factors do not match.");
2092 for (
auto const& factor : factors) {
2093 for (
auto& entry : getRow(row)) {
2094 entry.setValue(entry.getValue() * factor);
2100template<
typename ValueType>
2102 STORM_LOG_ASSERT(divisors.size() == this->getRowCount(),
"Can not divide rows: Number of rows and number of divisors do not match.");
2104 for (
auto const& divisor : divisors) {
2106 for (
auto& entry : getRow(row)) {
2107 entry.setValue(entry.getValue() / divisor);
2113#ifdef STORM_HAVE_CARL
2116 STORM_LOG_THROW(
false, storm::exceptions::NotImplementedException,
"This operation is not supported.");
2120template<
typename ValueType>
2122 return const_rows(this->columnsAndValues.begin() + this->rowIndications[startRow], this->rowIndications[endRow] - this->rowIndications[startRow]);
2125template<
typename ValueType>
2127 return rows(this->columnsAndValues.begin() + this->rowIndications[startRow], this->rowIndications[endRow] - this->rowIndications[startRow]);
2130template<
typename ValueType>
2132 return getRows(row, row + 1);
2135template<
typename ValueType>
2137 return getRows(row, row + 1);
2140template<
typename ValueType>
2142 STORM_LOG_ASSERT(rowGroup < this->getRowGroupCount(),
"Row group is out-of-bounds.");
2143 STORM_LOG_ASSERT(offset < this->getRowGroupSize(rowGroup),
"Row offset in row-group is out-of-bounds.");
2144 if (!this->hasTrivialRowGrouping()) {
2145 return getRow(this->getRowGroupIndices()[rowGroup] + offset);
2147 return getRow(this->getRowGroupIndices()[rowGroup] + offset);
2151template<
typename ValueType>
2153 STORM_LOG_ASSERT(rowGroup < this->getRowGroupCount(),
"Row group is out-of-bounds.");
2154 STORM_LOG_ASSERT(offset < this->getRowGroupSize(rowGroup),
"Row offset in row-group is out-of-bounds.");
2155 if (!this->hasTrivialRowGrouping()) {
2156 return getRow(this->getRowGroupIndices()[rowGroup] + offset);
2159 return getRow(rowGroup + offset);
2163template<
typename ValueType>
2165 STORM_LOG_ASSERT(rowGroup < this->getRowGroupCount(),
"Row group is out-of-bounds.");
2166 if (!this->hasTrivialRowGrouping()) {
2167 return getRows(this->getRowGroupIndices()[rowGroup], this->getRowGroupIndices()[rowGroup + 1]);
2169 return getRows(rowGroup, rowGroup + 1);
2173template<
typename ValueType>
2175 STORM_LOG_ASSERT(rowGroup < this->getRowGroupCount(),
"Row group is out-of-bounds.");
2176 if (!this->hasTrivialRowGrouping()) {
2177 return getRows(this->getRowGroupIndices()[rowGroup], this->getRowGroupIndices()[rowGroup + 1]);
2179 return getRows(rowGroup, rowGroup + 1);
2183template<
typename ValueType>
2185 STORM_LOG_ASSERT(row < this->getRowCount(),
"Row " << row <<
" exceeds row count " << this->getRowCount() <<
".");
2186 return this->columnsAndValues.begin() + this->rowIndications[row];
2189template<
typename ValueType>
2191 STORM_LOG_ASSERT(row < this->getRowCount(),
"Row " << row <<
" exceeds row count " << this->getRowCount() <<
".");
2192 return this->columnsAndValues.begin() + this->rowIndications[row];
2195template<
typename ValueType>
2197 return this->columnsAndValues.begin();
2200template<
typename ValueType>
2202 return this->columnsAndValues.begin();
2205template<
typename ValueType>
2207 STORM_LOG_ASSERT(row < this->getRowCount(),
"Row " << row <<
" exceeds row count " << this->getRowCount() <<
".");
2208 return this->columnsAndValues.begin() + this->rowIndications[row + 1];
2211template<
typename ValueType>
2213 STORM_LOG_ASSERT(row < this->getRowCount(),
"Row " << row <<
" exceeds row count " << this->getRowCount() <<
".");
2214 return this->columnsAndValues.begin() + this->rowIndications[row + 1];
2217template<
typename ValueType>
2219 return this->columnsAndValues.begin() + this->rowIndications[rowCount];
2222template<
typename ValueType>
2224 return this->columnsAndValues.begin() + this->rowIndications[rowCount];
2227template<
typename ValueType>
2229 ValueType sum = storm::utility::zero<ValueType>();
2230 for (
const_iterator it = this->begin(row), ite = this->end(row); it != ite; ++it) {
2231 sum += it->getValue();
2236template<
typename ValueType>
2239 for (
auto const& entry : *
this) {
2244 return nonConstEntries;
2247template<
typename ValueType>
2250 for (
index_type rowGroup = 0; rowGroup < this->getRowGroupCount(); ++rowGroup) {
2251 for (
auto const& entry : this->getRowGroup(rowGroup)) {
2253 ++nonConstRowGroups;
2258 return nonConstRowGroups;
2261template<
typename ValueType>
2264 for (
index_type row = 0; row < this->rowCount; ++row) {
2265 auto rowSum = getRowSum(row);
2266 if (!comparator.
isOne(rowSum)) {
2270 for (
auto const& entry : *
this) {
2271 if (comparator.
isConstant(entry.getValue())) {
2272 if (comparator.
isLess(entry.getValue(), storm::utility::zero<ValueType>())) {
2280template<
typename ValueType>
2283 for (
auto const& entry : *
this) {
2284 if (!comparator.
isLess(storm::utility::zero<ValueType>(), entry.getValue())) {
2291template<
typename ValueType>
2292template<
typename OtherValueType>
2309 for (
index_type row = 0; row < this->getRowCount(); ++row) {
2310 auto it2 = matrix.
begin(row);
2311 auto ite2 = matrix.
end(row);
2312 for (
const_iterator it1 = this->begin(row), ite1 = this->end(row); it1 != ite1; ++it1) {
2314 while (it2 != ite2 && it2->getColumn() < it1->getColumn()) {
2317 if (it2 == ite2 || it1->getColumn() != it2->getColumn()) {
2325template<
typename ValueType>
2327 if (this->getRowCount() != this->getColumnCount()) {
2330 if (this->getNonzeroEntryCount() != this->getRowCount()) {
2333 for (uint64_t row = 0; row < this->getRowCount(); ++row) {
2334 bool rowHasEntry =
false;
2335 for (
auto const& entry : this->getRow(row)) {
2336 if (entry.getColumn() == row) {
2354template<
typename ValueType>
2356 std::string result =
2357 std::to_string(getRowCount()) +
"x" + std::to_string(getColumnCount()) +
" matrix (" + std::to_string(getNonzeroEntryCount()) +
" non-zeroes";
2358 if (!hasTrivialRowGrouping()) {
2359 result +=
", " + std::to_string(getRowGroupCount()) +
" groups";
2365template<
typename ValueType>
2376 out <<
"\t---- group " << group <<
"/" << (matrix.
getRowGroupCount() - 1) <<
" ---- \n";
2384 out <<
i <<
"\t(\t";
2386 while (currentRealIndex < matrix.columnCount) {
2387 if (nextIndex < matrix.rowIndications[
i + 1] && currentRealIndex == matrix.columnsAndValues[nextIndex].getColumn()) {
2388 out << matrix.columnsAndValues[nextIndex].getValue() <<
"\t";
2395 out <<
"\t)\t" <<
i <<
'\n';
2409template<
typename ValueType>
2413 STORM_LOG_ASSERT(this->getRowGroupSize(group) == 1,
"Incorrect row group size.");
2420 while (currentRealIndex < this->columnCount) {
2421 if (nextIndex < this->rowIndications[
i + 1] && currentRealIndex == this->columnsAndValues[nextIndex].getColumn()) {
2422 out << this->columnsAndValues[nextIndex].getValue() <<
" ";
2434template<
typename ValueType>
2436 std::size_t result = 0;
2438 boost::hash_combine(result, this->getRowCount());
2439 boost::hash_combine(result, this->getColumnCount());
2440 boost::hash_combine(result, this->getEntryCount());
2441 boost::hash_combine(result, boost::hash_range(columnsAndValues.begin(), columnsAndValues.end()));
2442 boost::hash_combine(result, boost::hash_range(rowIndications.begin(), rowIndications.end()));
2443 if (!this->hasTrivialRowGrouping()) {
2444 boost::hash_combine(result, boost::hash_range(rowGroupIndices.get().begin(), rowGroupIndices.get().end()));
2475template std::ostream& operator<<(
2482#ifdef STORM_HAVE_CARL
2485#if defined(STORM_HAVE_CLN)
2498#if defined(STORM_HAVE_GMP)
A bit vector that is internally represented as a vector of 64-bit values.
uint64_t getNextSetIndex(uint64_t startingIndex) const
Retrieves the index of the bit that is the next bit set to true in the bit vector.
std::vector< uint64_t > getNumberOfSetBitsBeforeIndices() const
Retrieves a vector that holds at position i the number of bits set before index i.
bool empty() const
Retrieves whether no bits are set to true in this bit vector.
uint64_t getNumberOfSetBits() const
Returns the number of bits that are set to true in this bit vector.
uint64_t getNextUnsetIndex(uint64_t startingIndex) const
Retrieves the index of the bit that is the next bit set to false in the bit vector.
void set(uint64_t index, bool value=true)
Sets the given truth value at the given index.
const_iterator begin() const
Returns an iterator to the indices of the set bits in the bit vector.
size_t size() const
Retrieves the number of bits this bit vector can store.
bool get(uint64_t index) const
Retrieves the truth value of the bit at the given index and performs a bound check.
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.
void setColumn(index_type const &column)
Sets the column of the current entry.
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.
bool operator==(MatrixEntry const &other) const
This class represents a number of consecutive rows of the matrix.
const_rows(const_iterator begin, index_type entryCount)
Constructs an object that represents the rows defined by the value of the first entry,...
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.
rows(iterator begin, index_type entryCount)
Constructs an object that represents the rows defined by the value of the first entry,...
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.
SparseMatrixIndexType index_type
SparseMatrixBuilder(index_type rows=0, index_type columns=0, index_type entries=0, bool forceDimensions=true, bool hasCustomRowGrouping=false, index_type rowGroups=0)
Constructs a sparse matrix builder producing a matrix with the given number of rows,...
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.
const_iterator begin(index_type row) const
Retrieves an iterator that points to the beginning of the given row.
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.
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.
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.
const_iterator end(index_type row) const
Retrieves an iterator that points past the end of the 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
bool isIdentityMatrix() const
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).
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.
bool isOne(ValueType const &value) const
bool isConstant(ValueType const &value) const
bool isLess(ValueType const &value1, ValueType const &value2) const
#define STORM_LOG_WARN(message)
#define STORM_LOG_TRACE(message)
#define STORM_LOG_ASSERT(cond, message)
#define STORM_LOG_THROW(cond, exception, message)
Expression ite(Expression const &condition, Expression const &thenExpression, Expression const &elseExpression)
void print(std::vector< typename SparseMatrix< ValueType >::index_type > const &rowGroupIndices, std::vector< MatrixEntry< typename SparseMatrix< ValueType >::index_type, typename SparseMatrix< ValueType >::value_type > > const &columnsAndValues, std::vector< typename SparseMatrix< ValueType >::index_type > const &rowIndications)
bool isValidPermutation(std::vector< index_type > const &permutation)
Returns true if the given vector is a permutation of the numbers 0, 1, ..., n-1 for n = permutation....
std::vector< T > buildVectorForRange(T min, T max)
Constructs a vector [min, min+1, ...., max-1].
bool isOne(ValueType const &a)
bool isConstant(ValueType const &)
bool isZero(ValueType const &a)