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