Loading...
Searching...
No Matches
CSRGraphFromCoordinates.hpp
Go to the documentation of this file.
/*
Copyright 2016 SINTEF ICT, Applied Mathematics.
Copyright 2016 Statoil ASA.
Copyright 2022 Equinor ASA
This file is part of the Open Porous Media Project (OPM).
OPM is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
OPM is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with OPM. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef OPM_UTILITY_CSRGRAPHFROMCOORDINATES_HPP
#define OPM_UTILITY_CSRGRAPHFROMCOORDINATES_HPP
#include <cstddef>
#include <optional>
#include <type_traits>
#include <unordered_map>
#include <utility>
#include <vector>
namespace Opm { namespace utility {
template <typename VertexID = int, bool TrackCompressedIdx = false, bool PermitSelfConnections = false>
class CSRGraphFromCoordinates
{
private:
using BaseVertexID = std::remove_cv_t<VertexID>;
static_assert(std::is_integral_v<BaseVertexID>,
"The VertexID must be an integral type");
public:
using Neighbours = std::vector<BaseVertexID>;
using Offset = typename Neighbours::size_type;
using Start = std::vector<Offset>;
void clear();
void addConnection(VertexID v1, VertexID v2);
Offset applyVertexMerges();
void compress(Offset maxNumVertices,
bool expandExistingIdxMap = false);
Offset numVertices() const;
Offset numEdges() const;
const Start& startPointers() const
{
return this->csr_.startPointers();
}
const Neighbours& columnIndices() const
{
return this->csr_.columnIndices();
}
template <typename Ret = const Start&>
std::enable_if_t<TrackCompressedIdx, Ret> compressedIndexMap() const
{
return this->csr_.compressedIndexMap();
}
// MessageBufferType API should be similar to Dune::MessageBufferIF
template <class MessageBufferType>
void write(MessageBufferType& buffer) const
{
this->csr_.write(buffer);
}
// MessageBufferType API should be similar to Dune::MessageBufferIF
template <class MessageBufferType>
void read(MessageBufferType& buffer)
{
auto other = CSR{};
other.read(buffer);
this->uncompressed_
.add(other.maxRowID(),
other.maxColID(),
other.coordinateFormatRowIndices(),
other.columnIndices());
}
void addVertexGroup(const std::vector<VertexID>& vertices);
VertexID getFinalVertexID(VertexID originalVertexID) const;
private:
class Connections
{
public:
void add(VertexID v1, VertexID v2);
void add(VertexID maxRowIdx,
VertexID maxColIdx,
const Neighbours& rows,
const Neighbours& cols);
void clear();
bool empty() const;
bool isValid() const;
std::optional<BaseVertexID> maxRow() const;
std::optional<BaseVertexID> maxCol() const;
typename Neighbours::size_type numContributions() const;
const Neighbours& rowIndices() const;
const Neighbours& columnIndices() const;
VertexID findMergedVertexID(VertexID v, const std::unordered_map<VertexID, VertexID>& vertex_merges) const;
std::unordered_map<VertexID, VertexID> applyVertexMerges(const std::unordered_map<VertexID, VertexID>& vertex_merges);
private:
Neighbours i_{};
Neighbours j_{};
std::optional<VertexID> max_i_{};
std::optional<VertexID> max_j_{};
};
class CSR
{
public:
void merge(const Connections& conns,
const Offset maxNumVertices,
const bool expandExistingIdxMap);
Offset numRows() const;
BaseVertexID maxRowID() const;
BaseVertexID maxColID() const;
const Start& startPointers() const;
const Neighbours& columnIndices() const;
Neighbours coordinateFormatRowIndices() const;
template <typename Ret = const Start&>
std::enable_if_t<TrackCompressedIdx, Ret> compressedIndexMap() const
{
return this->compressedIdx_;
}
// MessageBufferType API should be similar to Dune::MessageBufferIF
template <class MessageBufferType>
void write(MessageBufferType& buffer) const
{
this->writeVector(this->ia_, buffer);
this->writeVector(this->ja_, buffer);
if constexpr (TrackCompressedIdx) {
this->writeVector(this->compressedIdx_, buffer);
}
buffer.write(this->numRows_);
buffer.write(this->numCols_);
}
// MessageBufferType API should be similar to Dune::MessageBufferIF
template <class MessageBufferType>
void read(MessageBufferType& buffer)
{
this->readVector(buffer, this->ia_);
this->readVector(buffer, this->ja_);
if constexpr (TrackCompressedIdx) {
this->readVector(buffer, this->compressedIdx_);
}
buffer.read(this->numRows_);
buffer.read(this->numCols_);
}
void clear();
private:
struct EmptyPlaceHolder {};
Start ia_{};
Neighbours ja_{};
std::conditional_t<TrackCompressedIdx, Start, EmptyPlaceHolder> compressedIdx_{};
BaseVertexID numRows_{};
BaseVertexID numCols_{};
// ---------------------------------------------------------
// Implementation of read()/write()
// ---------------------------------------------------------
template <typename T, class A, class MessageBufferType>
void writeVector(const std::vector<T,A>& vec,
MessageBufferType& buffer) const
{
const auto n = vec.size();
buffer.write(n);
for (const auto& x : vec) {
buffer.write(x);
}
}
template <class MessageBufferType, typename T, class A>
void readVector(MessageBufferType& buffer,
std::vector<T,A>& vec)
{
auto n = 0 * vec.size();
buffer.read(n);
vec.resize(n);
for (auto& x : vec) {
buffer.read(x);
}
}
// ---------------------------------------------------------
// Implementation of merge()
// ---------------------------------------------------------
void assemble(const Neighbours& rows,
const Neighbours& cols,
BaseVertexID maxRowID,
BaseVertexID maxColID,
bool expandExistingIdxMap);
void compress(const Offset maxNumVertices);
void sortColumnIndicesPerRow();
void condenseDuplicates();
// ---------------------------------------------------------
// Implementation of assemble()
// ---------------------------------------------------------
void preparePushbackRowGrouping(const int numRows,
const Neighbours& rowIdx);
void groupAndTrackColumnIndicesByRow(const Neighbours& rowIdx,
const Neighbours& colIdx);
// ---------------------------------------------------------
// General utilities
// ---------------------------------------------------------
void transpose();
void condenseAndTrackUniqueColumnsForSingleRow(typename Neighbours::const_iterator begin,
typename Neighbours::const_iterator end);
void remapCompressedIndex(Start&& compressedIdx,
std::optional<typename Start::size_type> numOrigNNZ = std::nullopt);
};
Connections uncompressed_;
CSR csr_;
std::unordered_map<VertexID, VertexID> parent_{};
std::unordered_map<VertexID, VertexID> vertex_mapping_{};
VertexID find(VertexID v);
void unionSets(VertexID a, VertexID b);
};
}} // namespace Opm::utility
// Actual implementation of member functions in _impl.hpp file.
#include <opm/common/utility/CSRGraphFromCoordinates_impl.hpp>
#endif // OPM_UTILITY_CSRGRAPHFROMCOORDINATES_HPP
Opm::utility::CSRGraphFromCoordinates
Form CSR adjacency matrix representation of unstructured graphs.
Definition CSRGraphFromCoordinates.hpp:56
Opm::utility::CSRGraphFromCoordinates::startPointers
const Start & startPointers() const
Read-only access to compressed structure's start pointers.
Definition CSRGraphFromCoordinates.hpp:121
Opm::utility::CSRGraphFromCoordinates::numEdges
Offset numEdges() const
Retrieve number of edges (non-zero matrix elements) in input graph.
Definition CSRGraphFromCoordinates_impl.hpp:810
Opm::utility::CSRGraphFromCoordinates::compressedIndexMap
std::enable_if_t< TrackCompressedIdx, Ret > compressedIndexMap() const
Read-only access to mapping from input order vertex pairs to compressed structure's edge index (locat...
Definition CSRGraphFromCoordinates.hpp:141
Opm::utility::CSRGraphFromCoordinates::clear
void clear()
Clear all internal buffers, but preserve allocated capacity.
Definition CSRGraphFromCoordinates_impl.hpp:644
Opm::utility::CSRGraphFromCoordinates::addConnection
void addConnection(VertexID v1, VertexID v2)
Add flow rate connection between regions.
Definition CSRGraphFromCoordinates_impl.hpp:653
Opm::utility::CSRGraphFromCoordinates::columnIndices
const Neighbours & columnIndices() const
Read-only access to compressed structure's column indices, ascendingly sorted per row.
Definition CSRGraphFromCoordinates.hpp:128
Opm::utility::CSRGraphFromCoordinates::getFinalVertexID
VertexID getFinalVertexID(VertexID originalVertexID) const
Get the final vertex ID after all merges and renumbering for a given original vertex ID.
Definition CSRGraphFromCoordinates_impl.hpp:791
Opm::utility::CSRGraphFromCoordinates::Offset
typename Neighbours::size_type Offset
Offset into neighbour array.
Definition CSRGraphFromCoordinates.hpp:68
Opm::utility::CSRGraphFromCoordinates::numVertices
Offset numVertices() const
Retrieve number of rows (source entities) in input graph.
Definition CSRGraphFromCoordinates_impl.hpp:803
Opm::utility::CSRGraphFromCoordinates::addVertexGroup
void addVertexGroup(const std::vector< VertexID > &vertices)
Add a group of vertices that should be merged together.
Definition CSRGraphFromCoordinates_impl.hpp:676
Opm::utility::CSRGraphFromCoordinates::applyVertexMerges
Offset applyVertexMerges()
Apply vertex merges to all vertex groups.
Definition CSRGraphFromCoordinates_impl.hpp:741
Opm::utility::CSRGraphFromCoordinates::compress
void compress(Offset maxNumVertices, bool expandExistingIdxMap=false)
Form CSR adjacency matrix representation of input graph from connections established in previous call...
Definition CSRGraphFromCoordinates_impl.hpp:770
Opm::utility::CSRGraphFromCoordinates::Neighbours
std::vector< BaseVertexID > Neighbours
Representation of neighbouring regions.
Definition CSRGraphFromCoordinates.hpp:65
Opm::utility::CSRGraphFromCoordinates::Start
std::vector< Offset > Start
CSR start pointers.
Definition CSRGraphFromCoordinates.hpp:71
Opm
This class implements a small container which holds the transmissibility mulitpliers for all the face...
Definition Exceptions.hpp:30