178 for (
auto read_pos = 0*i_.size(); read_pos < i_.size(); ++read_pos) {
179 if (i_[read_pos] != j_[read_pos]) {
180 if (write_pos != read_pos) {
181 i_[write_pos] = i_[read_pos];
182 j_[write_pos] = j_[read_pos];
187 i_.resize(write_pos);
188 j_.resize(write_pos);
192 std::set<VertexID> sorted_unique_vertices;
193 sorted_unique_vertices.insert(i_.begin(), i_.end());
194 sorted_unique_vertices.insert(j_.begin(), j_.end());
197 std::unordered_map<VertexID, VertexID> vertex_map;
198 vertex_map.reserve(sorted_unique_vertices.size());
200 for (
auto& v : sorted_unique_vertices) {
201 vertex_map.emplace(v, new_id++);
205 this->max_i_ = this->max_j_ = new_id - 1;
208 auto remap = [&vertex_map](
auto v) {
210 return vertex_map.at(v);
213 std::transform(i_.begin(), i_.end(), i_.begin(), remap);
214 std::transform(j_.begin(), j_.end(), j_.begin(), remap);
217 std::unordered_map<VertexID, VertexID> final_mapping;
218 final_mapping.reserve(max_original_vertex_id + 1);
220 for (VertexID vertex = 0; vertex <= max_original_vertex_id; ++vertex) {
221 auto merged_id = findMergedVertexID(vertex, vertex_merges);
222 final_mapping.emplace(vertex, vertex_map.at(merged_id));
224 return final_mapping;
233template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
237 const Offset maxNumVertices,
238 const bool expandExistingIdxMap)
240 const auto maxRow = conns.maxRow();
242 if (maxRow.has_value() &&
243 (
static_cast<Offset
>(*maxRow) >= maxNumVertices))
245 throw std::invalid_argument {
246 "Number of vertices in input graph (" +
247 std::to_string(*maxRow) +
") "
248 "exceeds maximum graph size implied by explicit size of "
249 "adjacency matrix (" + std::to_string(maxNumVertices) +
')'
253 this->assemble(conns.rowIndices(), conns.columnIndices(),
254 maxRow.value_or(BaseVertexID{0}),
255 conns.maxCol().value_or(BaseVertexID{0}),
256 expandExistingIdxMap);
258 this->compress(maxNumVertices);
261template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
266 return this->startPointers().empty()
267 ? 0 : this->startPointers().size() - 1;
270template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
271typename Opm::utility::CSRGraphFromCoordinates<VertexID, TrackCompressedIdx, PermitSelfConnections>::BaseVertexID
275 return this->numRows_ - 1;
278template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
279typename Opm::utility::CSRGraphFromCoordinates<VertexID, TrackCompressedIdx, PermitSelfConnections>::BaseVertexID
283 return this->numCols_ - 1;
286template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
294template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
302template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
307 auto rowIdx = Neighbours{};
309 if (this->ia_.empty()) {
313 rowIdx.reserve(this->ia_.back());
315 auto row = BaseVertexID{};
317 const auto m = this->ia_.size() - 1;
318 for (
auto i = 0*m; i < m; ++i, ++row) {
319 const auto n = this->ia_[i + 1] - this->ia_[i + 0];
321 rowIdx.insert(rowIdx.end(), n, row);
327template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
335 if constexpr (TrackCompressedIdx) {
336 this->compressedIdx_.clear();
343template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
347 const Neighbours& cols,
348 const BaseVertexID maxRowIdx,
349 const BaseVertexID maxColIdx,
350 [[maybe_unused]]
const bool expandExistingIdxMap)
352 [[maybe_unused]]
auto compressedIdx = this->compressedIdx_;
353 [[maybe_unused]]
const auto numOrigNNZ = this->ja_.size();
355 auto i = this->coordinateFormatRowIndices();
356 i.insert(i.end(), rows.begin(), rows.end());
359 j.insert(j.end(), cols.begin(), cols.end());
362 const auto thisNumRows = std::max(this->numRows_, maxRowIdx + 1);
363 const auto thisNumCols = std::max(this->numCols_, maxColIdx + 1);
365 this->preparePushbackRowGrouping(thisNumRows, i);
367 this->groupAndTrackColumnIndicesByRow(i, j);
369 if constexpr (TrackCompressedIdx) {
370 if (expandExistingIdxMap) {
371 this->remapCompressedIndex(std::move(compressedIdx), numOrigNNZ);
375 this->numRows_ = thisNumRows;
376 this->numCols_ = thisNumCols;
379template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
384 if (this->numRows() > maxNumVertices) {
385 throw std::invalid_argument {
386 "Number of vertices in input graph (" +
387 std::to_string(this->numRows()) +
") "
388 "exceeds maximum graph size implied by explicit size of "
389 "adjacency matrix (" + std::to_string(maxNumVertices) +
')'
393 this->sortColumnIndicesPerRow();
396 this->condenseDuplicates();
398 const auto nRows = this->startPointers().size() - 1;
399 if (nRows < maxNumVertices) {
400 this->ia_.insert(this->ia_.end(),
401 maxNumVertices - nRows,
402 this->startPointers().back());
406template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
420template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
427 const auto colIdx = this->ja_;
428 auto end = colIdx.begin();
432 [[maybe_unused]]
auto compressedIdx = this->compressedIdx_;
433 if constexpr (TrackCompressedIdx) {
434 this->compressedIdx_.clear();
437 const auto numRows = this->ia_.size() - 1;
438 for (
auto row = 0*numRows; row < numRows; ++row) {
441 std::advance(end, this->ia_[row + 1] - this->ia_[row + 0]);
443 const auto q = this->ja_.size();
445 this->condenseAndTrackUniqueColumnsForSingleRow(begin, end);
447 this->ia_[row + 0] = q;
450 if constexpr (TrackCompressedIdx) {
451 this->remapCompressedIndex(std::move(compressedIdx));
455 this->ia_.back() = this->ja_.size();
458template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
462 const Neighbours& rowIdx)
464 assert (numRows >= 0);
466 this->ia_.assign(numRows + 1, 0);
470 for (
const auto& row : rowIdx) {
471 this->ia_[row + 1] += 1;
485 for (
typename Start::size_type i = 1, n = numRows; i <= n; ++i) {
486 this->ia_[0] += this->ia_[i];
487 this->ia_[i] = this->ia_[0] - this->ia_[i];
490 assert (this->ia_[0] == rowIdx.size());
493template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
497 const Neighbours& colIdx)
499 assert (this->ia_[0] == rowIdx.size());
501 const auto nnz = rowIdx.size();
503 this->ja_.resize(nnz);
505 if constexpr (TrackCompressedIdx) {
506 this->compressedIdx_.clear();
507 this->compressedIdx_.reserve(nnz);
527 for (
auto nz = 0*nnz; nz < nnz; ++nz) {
528 const auto k = this->ia_[rowIdx[nz] + 1] ++;
530 this->ja_[k] = colIdx[nz];
532 if constexpr (TrackCompressedIdx) {
533 this->compressedIdx_.push_back(k);
540template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
545 [[maybe_unused]]
auto compressedIdx = this->compressedIdx_;
548 const auto rowIdx = this->coordinateFormatRowIndices();
549 const auto colIdx = this->ja_;
551 this->preparePushbackRowGrouping(this->numCols_, colIdx);
555 this->groupAndTrackColumnIndicesByRow(colIdx, rowIdx);
558 if constexpr (TrackCompressedIdx) {
559 this->remapCompressedIndex(std::move(compressedIdx));
562 std::swap(this->numRows_, this->numCols_);
565template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
569 typename Neighbours::const_iterator end)
579 while (begin != end) {
582 if constexpr (TrackCompressedIdx) {
583 this->compressedIdx_.push_back(this->ja_.size());
586 this->ja_.push_back(*begin);
589 std::find_if(begin, end, [last = this->ja_.back()]
590 (
const auto j) { return j != last; });
592 if constexpr (TrackCompressedIdx) {
594 const auto ndup = std::distance(begin, next_unique);
600 this->compressedIdx_.insert(this->compressedIdx_.end(),
602 this->compressedIdx_.back());
610template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
614 [[maybe_unused]] std::optional<typename Start::size_type> numOrig)
616 if constexpr (TrackCompressedIdx) {
617 std::transform(compressedIdx.begin(), compressedIdx.end(),
618 compressedIdx.begin(),
619 [
this](
const auto& i)
621 return this->compressedIdx_[i];
624 if (numOrig.has_value() && (*numOrig < this->compressedIdx_.size())) {
628 .insert(compressedIdx.end(),
629 this->compressedIdx_.begin() + *numOrig,
630 this->compressedIdx_.end());
633 this->compressedIdx_.swap(compressedIdx);
643template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
646 this->uncompressed_.clear();
650template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
655 if ((v1 < 0) || (v2 < 0)) {
656 throw std::invalid_argument {
657 "Vertex IDs must be non-negative. Got (v1,v2) = ("
658 + std::to_string(v1) +
", " + std::to_string(v2)
663 if constexpr (! PermitSelfConnections) {
670 this->uncompressed_.add(v1, v2);
673template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
678 if (vertices.empty()) {
682 for (
const auto& v : vertices) {
683 if (parent_.find(v) == parent_.end()) {
684 parent_.emplace(v, v);
689 if (vertices.size() > 1) {
690 for (
size_t i = 1; i < vertices.size(); ++i) {
691 unionSets(vertices[0], vertices[i]);
696template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
702 auto it = parent_.find(v);
703 if (it == parent_.end()) {
704 parent_.emplace(v, v);
709 if (it->second != v) {
710 it->second = find(it->second);
715template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
721 VertexID rootA = find(a);
722 VertexID rootB = find(b);
725 if (rootA == rootB) {
732 parent_.at(rootB) = rootA;
734 parent_.at(rootA) = rootB;
738template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
744 if (parent_.empty()) {
745 return this->uncompressed_.maxRow().value_or(0) + 1;
749 std::unordered_map<VertexID, VertexID> vertex_merges;
750 for (
auto& [vertex, parent] : parent_) {
752 VertexID root = find(vertex);
755 if (vertex != root) {
756 vertex_merges.emplace(vertex, root);
760 if (!vertex_merges.empty()) {
761 vertex_mapping_ = this->uncompressed_.applyVertexMerges(vertex_merges);
764 return this->uncompressed_.maxRow().value_or(0) + 1;
767template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
773 if (!parent_.empty() && vertex_mapping_.empty()) {
777 if (! this->uncompressed_.isValid()) {
778 throw std::logic_error {
779 "Cannot compress invalid connection list"
783 this->csr_.merge(this->uncompressed_, maxNumVertices, expandExistingIdxMap);
785 this->uncompressed_.clear();
788template <
typename VertexID,
bool TrackCompressedIdx,
bool PermitSelfConnections>
793 if (vertex_mapping_.empty()) {
797 return vertex_mapping_.at(v);