Tpetra_CrsGraph_decl.hpp

Go to the documentation of this file.

// @HEADER
// ***********************************************************************
//
//          Tpetra: Templated Linear Algebra Services Package
//                 Copyright (2008) Sandia Corporation
//
// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
// the U.S. Government retains certain rights in this software.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// ************************************************************************
// @HEADER

// clang-format off
#ifndef TPETRA_CRSGRAPH_DECL_HPP
#define TPETRA_CRSGRAPH_DECL_HPP


#include "Tpetra_CrsGraph_fwd.hpp"
#include "Tpetra_CrsMatrix_fwd.hpp"
#include "Tpetra_BlockCrsMatrix_fwd.hpp"
#include "Tpetra_DistObject.hpp"
#include "Tpetra_Exceptions.hpp"
#include "Tpetra_RowGraph.hpp"
#include "Tpetra_Util.hpp" // need this here for sort2
#include "Tpetra_Details_WrappedDualView.hpp"

#include "KokkosSparse_findRelOffset.hpp"
#include "Kokkos_DualView.hpp"
#include "Kokkos_StaticCrsGraph.hpp"

#include "Teuchos_CommHelpers.hpp"
#include "Teuchos_Describable.hpp"
#include "Teuchos_OrdinalTraits.hpp"
#include "Teuchos_ParameterListAcceptorDefaultBase.hpp"

#include <functional> // std::function
#include <memory>

namespace Tpetra {


  // Forward declaration for CrsGraph::swap() test
  template<class LocalOrdinal, class GlobalOrdinal, class Node> class crsGraph_Swap_Tester;

#ifndef DOXYGEN_SHOULD_SKIP_THIS
  namespace Details {
    template<class LocalOrdinal,
             class GlobalOrdinal>
    class CrsPadding;
  } // namespace Details

  namespace { // (anonymous)

    template<class ViewType>
    struct UnmanagedView {
      static_assert (Kokkos::is_view<ViewType>::value,
                     "ViewType must be a Kokkos::View specialization.");
      // FIXME (mfh 02 Dec 2015) Right now, this strips away other
      // memory traits.  Christian will add an "AllTraits" enum which is
      // the enum value of MemoryTraits<T>, that will help us fix this.
      typedef Kokkos::View<typename ViewType::data_type,
                           typename ViewType::array_layout,
                           typename ViewType::device_type,
                           Kokkos::MemoryUnmanaged> type;
    };

  } // namespace (anonymous)
#endif // DOXYGEN_SHOULD_SKIP_THIS

  struct RowInfo {
    size_t localRow;
    size_t allocSize;
    size_t numEntries;
    size_t offset1D;
  };

  enum ELocalGlobal {
    LocalIndices,
    GlobalIndices
  };

  namespace Details {
    enum EStorageStatus {
      STORAGE_1D_UNPACKED, //<! 1-D "unpacked" storage
      STORAGE_1D_PACKED, //<! 1-D "packed" storage
      STORAGE_UB //<! Invalid value; upper bound on enum values
    };

  } // namespace Details

  template <class LocalOrdinal,
            class GlobalOrdinal,
            class Node>
  class CrsGraph :
    public RowGraph<LocalOrdinal, GlobalOrdinal, Node>,
    public DistObject<GlobalOrdinal,
                      LocalOrdinal,
                      GlobalOrdinal,
                      Node>,
    public Teuchos::ParameterListAcceptorDefaultBase
  {
    template <class S, class LO, class GO, class N>
    friend class CrsMatrix;
    template <class LO2, class GO2, class N2>
    friend class CrsGraph;
    template <class LO, class GO, class N>
    friend class FECrsGraph;

    using dist_object_type = DistObject<GlobalOrdinal, LocalOrdinal, GlobalOrdinal, Node>;

  public:
    using local_ordinal_type = LocalOrdinal;
    using global_ordinal_type = GlobalOrdinal;
    using device_type = typename Node::device_type;
    using execution_space = typename device_type::execution_space;

    using node_type = Node;

    using local_graph_device_type =
           Kokkos::StaticCrsGraph<local_ordinal_type, Kokkos::LayoutLeft,
                                  device_type, void, size_t>;

    using local_graph_host_type = typename local_graph_device_type::HostMirror;

    using map_type = ::Tpetra::Map<LocalOrdinal, GlobalOrdinal, Node>;
    using import_type = ::Tpetra::Import<LocalOrdinal, GlobalOrdinal, Node>;
    using export_type = ::Tpetra::Export<LocalOrdinal, GlobalOrdinal, Node>;

protected:
    // Types used for CrsGraph's storage of local column indices
    using local_inds_dualv_type =
          Kokkos::DualView<local_ordinal_type*, device_type>;
    using local_inds_wdv_type = 
          Details::WrappedDualView<local_inds_dualv_type>;

    // Types used for CrsGraph's storage of global column indices
    using global_inds_dualv_type =
          Kokkos::DualView<global_ordinal_type*, device_type>;
    using global_inds_wdv_type =
          Details::WrappedDualView<global_inds_dualv_type>;

public:
    using row_graph_type = RowGraph<LocalOrdinal, GlobalOrdinal, Node>;
    using row_ptrs_device_view_type =
          typename row_graph_type::row_ptrs_device_view_type;
    using row_ptrs_host_view_type =
          typename row_graph_type::row_ptrs_host_view_type;

    using local_inds_device_view_type =
          typename row_graph_type::local_inds_device_view_type;
    using local_inds_host_view_type =
          typename row_graph_type::local_inds_host_view_type;
    using nonconst_local_inds_host_view_type =
          typename row_graph_type::nonconst_local_inds_host_view_type;

    using global_inds_device_view_type =
          typename row_graph_type::global_inds_device_view_type;
    using global_inds_host_view_type =
          typename row_graph_type::global_inds_host_view_type;
    using nonconst_global_inds_host_view_type =
          typename row_graph_type::nonconst_global_inds_host_view_type;

    using offset_device_view_type =
          typename row_ptrs_device_view_type::non_const_type;



    CrsGraph (const Teuchos::RCP<const map_type>& rowMap,
              const size_t maxNumEntriesPerRow,
              const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);

    CrsGraph (const Teuchos::RCP<const map_type>& rowMap,
              const Kokkos::DualView<const size_t*, device_type>& numEntPerRow,
              const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);

    CrsGraph (const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::ArrayView<const size_t>& numEntPerRow,
              const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);



    CrsGraph (const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::RCP<const map_type>& colMap,
              const size_t maxNumEntriesPerRow,
              const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);

    CrsGraph (const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::RCP<const map_type>& colMap,
              const Kokkos::DualView<const size_t*, device_type>& numEntPerRow,
              const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);

    CrsGraph (const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::RCP<const map_type>& colMap,
              const Teuchos::ArrayView<const size_t>& numEntPerRow,
              const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);


    CrsGraph (CrsGraph<local_ordinal_type, global_ordinal_type, node_type>& originalGraph,
              const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);

    CrsGraph (const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::RCP<const map_type>& colMap,
              const typename local_graph_device_type::row_map_type& rowPointers,
              const typename local_graph_device_type::entries_type::non_const_type& columnIndices,
              const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);

    CrsGraph (const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::RCP<const map_type>& colMap,
              const Teuchos::ArrayRCP<size_t>& rowPointers,
              const Teuchos::ArrayRCP<local_ordinal_type>& columnIndices,
              const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);

    CrsGraph (const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::RCP<const map_type>& colMap,
              const local_graph_device_type& lclGraph,
              const Teuchos::RCP<Teuchos::ParameterList>& params);

    CrsGraph (const local_graph_device_type& lclGraph,
              const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::RCP<const map_type>& colMap,
              const Teuchos::RCP<const map_type>& domainMap = Teuchos::null,
              const Teuchos::RCP<const map_type>& rangeMap = Teuchos::null,
              const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);

    CrsGraph (const local_graph_device_type& lclGraph,
              const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::RCP<const map_type>& colMap,
              const Teuchos::RCP<const map_type>& domainMap,
              const Teuchos::RCP<const map_type>& rangeMap,
              const Teuchos::RCP<const import_type>& importer,
              const Teuchos::RCP<const export_type>& exporter,
              const Teuchos::RCP<Teuchos::ParameterList>& params =
                Teuchos::null);

    CrsGraph (const CrsGraph<local_ordinal_type, global_ordinal_type, node_type>&) = default;

    CrsGraph& operator= (const CrsGraph<local_ordinal_type, global_ordinal_type, node_type>&) = default;

    CrsGraph (CrsGraph<local_ordinal_type, global_ordinal_type, node_type>&&) = default;

    CrsGraph& operator= (CrsGraph<local_ordinal_type, global_ordinal_type, node_type>&&) = default;

    virtual ~CrsGraph () = default;


    bool isIdenticalTo(const CrsGraph<LocalOrdinal, GlobalOrdinal, Node> &graph) const;



    void
    setParameterList (const Teuchos::RCP<Teuchos::ParameterList>& params) override;

    Teuchos::RCP<const Teuchos::ParameterList>
    getValidParameters () const override;



    void
    insertGlobalIndices (const global_ordinal_type globalRow,
                         const Teuchos::ArrayView<const global_ordinal_type>& indices);

    void
    insertGlobalIndices (const global_ordinal_type globalRow,
                         const local_ordinal_type numEnt,
                         const global_ordinal_type inds[]);


    void
    insertLocalIndices (const local_ordinal_type localRow,
                        const Teuchos::ArrayView<const local_ordinal_type>& indices);

    void
    insertLocalIndices (const local_ordinal_type localRow,
                        const local_ordinal_type numEnt,
                        const local_ordinal_type inds[]);


    void removeLocalIndices (local_ordinal_type localRow);



    void globalAssemble ();

    void
    resumeFill (const Teuchos::RCP<Teuchos::ParameterList>& params =
                  Teuchos::null);

    void
    fillComplete (const Teuchos::RCP<const map_type>& domainMap,
                  const Teuchos::RCP<const map_type>& rangeMap,
                  const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);

    void
    fillComplete (const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null);

    void
    expertStaticFillComplete (const Teuchos::RCP<const map_type>& domainMap,
                              const Teuchos::RCP<const map_type>& rangeMap,
                              const Teuchos::RCP<const import_type>& importer =
                                Teuchos::null,
                              const Teuchos::RCP<const export_type>& exporter =
                                Teuchos::null,
                              const Teuchos::RCP<Teuchos::ParameterList>& params =
                                Teuchos::null);


    Teuchos::RCP<const Teuchos::Comm<int> > getComm() const override;


    Teuchos::RCP<const map_type> getRowMap () const override;

    Teuchos::RCP<const map_type> getColMap () const override;

    Teuchos::RCP<const map_type> getDomainMap () const override;

    Teuchos::RCP<const map_type> getRangeMap () const override;

    Teuchos::RCP<const import_type> getImporter () const override;

    Teuchos::RCP<const export_type> getExporter () const override;


    global_size_t getGlobalNumRows() const override;


    global_size_t getGlobalNumCols () const override;

    size_t getLocalNumRows () const override;


    size_t getLocalNumCols () const override;

    global_ordinal_type getIndexBase () const override;


    global_size_t getGlobalNumEntries () const override;

    size_t getLocalNumEntries() const override;


    size_t
    getNumEntriesInGlobalRow (global_ordinal_type globalRow) const override;

    size_t
    getNumEntriesInLocalRow (local_ordinal_type localRow) const override;

    size_t getLocalAllocationSize () const;

    size_t getNumAllocatedEntriesInGlobalRow (global_ordinal_type globalRow) const;

    size_t getNumAllocatedEntriesInLocalRow (local_ordinal_type localRow) const;

    size_t getGlobalMaxNumRowEntries () const override;

    size_t getLocalMaxNumRowEntries () const override;

    bool hasColMap () const override;


    bool isLocallyIndexed () const override;

    bool isGloballyIndexed () const override;

    bool isFillComplete () const override;

    bool isFillActive () const;

    bool isSorted () const;


    bool isStorageOptimized () const;


    void
    getGlobalRowCopy (global_ordinal_type gblRow,
                      nonconst_global_inds_host_view_type &gblColInds,
                      size_t& numColInds) const override;

    void
    getLocalRowCopy (local_ordinal_type gblRow,
                     nonconst_local_inds_host_view_type &gblColInds,
                     size_t& numColInds) const override;

    void
    getGlobalRowView (
      const global_ordinal_type gblRow,
      global_inds_host_view_type &gblColInds) const override;


    bool supportsRowViews () const override;


    void
    getLocalRowView (
      const LocalOrdinal lclRow,
      local_inds_host_view_type &lclColInds) const override;




    std::string description () const override;

    void
    describe (Teuchos::FancyOStream& out,
              const Teuchos::EVerbosityLevel verbLevel =
              Teuchos::Describable::verbLevel_default) const override;



    using buffer_device_type = typename dist_object_type::buffer_device_type;
    using packet_type = global_ordinal_type;

    virtual bool
    checkSizes (const SrcDistObject& source) override;

  // clang-format on
  using dist_object_type::
      copyAndPermute; 
  // clang-format off

    virtual void
    copyAndPermute
    (const SrcDistObject& source,
     const size_t numSameIDs,
     const Kokkos::DualView<const local_ordinal_type*,
       buffer_device_type>& permuteToLIDs,
     const Kokkos::DualView<const local_ordinal_type*,
       buffer_device_type>& permuteFromLIDs,
     const CombineMode CM) override;

    using padding_type = Details::CrsPadding<
      local_ordinal_type, global_ordinal_type>;

    void
    applyCrsPadding(const padding_type& padding,
                    const bool verbose);

    std::unique_ptr<padding_type>
    computeCrsPadding(
      const RowGraph<local_ordinal_type, global_ordinal_type,
        node_type>& source,
      const size_t numSameIDs,
      const Kokkos::DualView<const local_ordinal_type*,
        buffer_device_type>& permuteToLIDs,
      const Kokkos::DualView<const local_ordinal_type*,
        buffer_device_type>& permuteFromLIDs,
      const bool verbose) const;

    // This actually modifies imports by sorting it.
    std::unique_ptr<padding_type>
    computeCrsPaddingForImports(
      const Kokkos::DualView<const local_ordinal_type*,
        buffer_device_type>& importLIDs,
      Kokkos::DualView<packet_type*, buffer_device_type> imports,
      Kokkos::DualView<size_t*, buffer_device_type> numPacketsPerLID,
      const bool verbose) const;

    std::unique_ptr<padding_type>
    computePaddingForCrsMatrixUnpack(
      const Kokkos::DualView<const local_ordinal_type*,
        buffer_device_type>& importLIDs,
      Kokkos::DualView<char*, buffer_device_type> imports,
      Kokkos::DualView<size_t*, buffer_device_type> numPacketsPerLID,
      const bool verbose) const;

    void
    computeCrsPaddingForSameIDs(
      padding_type& padding,
      const RowGraph<local_ordinal_type, global_ordinal_type,
        node_type>& source,
      const local_ordinal_type numSameIDs) const;

    void
    computeCrsPaddingForPermutedIDs(
      padding_type& padding,
      const RowGraph<local_ordinal_type, global_ordinal_type,
        node_type>& source,
      const Kokkos::DualView<const local_ordinal_type*,
        buffer_device_type>& permuteToLIDs,
      const Kokkos::DualView<const local_ordinal_type*,
      buffer_device_type>& permuteFromLIDs) const;

    virtual void
    packAndPrepare(
      const SrcDistObject& source,
      const Kokkos::DualView<const local_ordinal_type*, buffer_device_type>& exportLIDs,
      Kokkos::DualView<packet_type*, buffer_device_type>& exports,
      Kokkos::DualView<size_t*, buffer_device_type> numPacketsPerLID,
      size_t& constantNumPackets) override;

  // clang-format on
  using dist_object_type::packAndPrepare; 
  // clang-format off

    virtual void
    pack (const Teuchos::ArrayView<const local_ordinal_type>& exportLIDs,
          Teuchos::Array<global_ordinal_type>& exports,
          const Teuchos::ArrayView<size_t>& numPacketsPerLID,
          size_t& constantNumPackets) const override;

    void
    packFillActive (const Teuchos::ArrayView<const local_ordinal_type>& exportLIDs,
                    Teuchos::Array<global_ordinal_type>& exports,
                    const Teuchos::ArrayView<size_t>& numPacketsPerLID,
                    size_t& constantNumPackets) const;

    void
    packFillActiveNew (const Kokkos::DualView<const local_ordinal_type*,
                         buffer_device_type>& exportLIDs,
                       Kokkos::DualView<packet_type*,
                         buffer_device_type>& exports,
                       Kokkos::DualView<size_t*,
                         buffer_device_type> numPacketsPerLID,
                       size_t& constantNumPackets) const;

  // clang-format on
  using dist_object_type::unpackAndCombine; 
  // clang-format off

    virtual void
    unpackAndCombine
    (const Kokkos::DualView<const local_ordinal_type*,
       buffer_device_type>& importLIDs,
     Kokkos::DualView<packet_type*,
       buffer_device_type> imports,
     Kokkos::DualView<size_t*,
       buffer_device_type> numPacketsPerLID,
     const size_t constantNumPackets,
     const CombineMode combineMode) override;



    void
    getLocalDiagOffsets (const Kokkos::View<size_t*, device_type, Kokkos::MemoryUnmanaged>& offsets) const;

    void
    getLocalOffRankOffsets (offset_device_view_type& offsets) const;

    void
    getLocalDiagOffsets (Teuchos::ArrayRCP<size_t>& offsets) const;

    void
    setAllIndices (const typename local_graph_device_type::row_map_type& rowPointers,
                   const typename local_graph_device_type::entries_type::non_const_type& columnIndices);

    void
    setAllIndices (const Teuchos::ArrayRCP<size_t> & rowPointers,
                   const Teuchos::ArrayRCP<local_ordinal_type> & columnIndices);

    row_ptrs_host_view_type getLocalRowPtrsHost () const;

    row_ptrs_device_view_type getLocalRowPtrsDevice () const;

    local_inds_host_view_type getLocalIndicesHost () const;

    local_inds_device_view_type getLocalIndicesDevice () const;

    void replaceColMap (const Teuchos::RCP<const map_type>& newColMap);

    void
    reindexColumns (const Teuchos::RCP<const map_type>& newColMap,
                    const Teuchos::RCP<const import_type>& newImport = Teuchos::null,
                    const bool sortIndicesInEachRow = true);

    void
    replaceDomainMap (const Teuchos::RCP<const map_type>& newDomainMap);

    void
    replaceDomainMapAndImporter (const Teuchos::RCP<const map_type>& newDomainMap,
                                 const Teuchos::RCP<const import_type>& newImporter);

    void
    replaceRangeMap (const Teuchos::RCP<const map_type>& newRangeMap);

    void
    replaceRangeMapAndExporter (const Teuchos::RCP<const map_type>& newRangeMap,
                                const Teuchos::RCP<const export_type>& newExporter);

    virtual void
    removeEmptyProcessesInPlace (const Teuchos::RCP<const map_type>& newMap) override;

    template<class DestViewType, class SrcViewType, 
             class DestOffsetViewType, class SrcOffsetViewType >
    struct pack_functor {
      typedef typename DestViewType::execution_space execution_space;
      SrcViewType src;
      DestViewType dest;
      SrcOffsetViewType src_offset;
      DestOffsetViewType dest_offset;
      typedef typename DestOffsetViewType::non_const_value_type ScalarIndx;

      pack_functor(DestViewType dest_, 
                   const SrcViewType src_,
                   DestOffsetViewType dest_offset_, 
                   const SrcOffsetViewType src_offset_):
        src(src_),dest(dest_),
        src_offset(src_offset_),dest_offset(dest_offset_) {};

      KOKKOS_INLINE_FUNCTION
      void operator() (size_t row) const {
        ScalarIndx i = src_offset(row);
        ScalarIndx j = dest_offset(row);
        const ScalarIndx k = dest_offset(row+1);
        for(;j<k;j++,i++) {
          dest(j) = src(i);
        }
      }
    };

  private:
    // Friend declaration for nonmember function.
    template<class CrsGraphType>
    friend Teuchos::RCP<CrsGraphType>
    importAndFillCompleteCrsGraph (const Teuchos::RCP<const CrsGraphType>& sourceGraph,
                                    const Import<typename CrsGraphType::local_ordinal_type,
                                                 typename CrsGraphType::global_ordinal_type,
                                                 typename CrsGraphType::node_type>& importer,
                                    const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                                 typename CrsGraphType::global_ordinal_type,
                                                                 typename CrsGraphType::node_type> >& domainMap,
                                    const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                                 typename CrsGraphType::global_ordinal_type,
                                                                 typename CrsGraphType::node_type> >& rangeMap,
                                    const Teuchos::RCP<Teuchos::ParameterList>& params);

    // Friend declaration for nonmember function.
    template<class CrsGraphType>
    friend Teuchos::RCP<CrsGraphType>
    importAndFillCompleteCrsGraph (const Teuchos::RCP<const CrsGraphType>& sourceGraph,
                                    const Import<typename CrsGraphType::local_ordinal_type,
                                                 typename CrsGraphType::global_ordinal_type,
                                                 typename CrsGraphType::node_type>& rowImporter,
                                   const Import<typename CrsGraphType::local_ordinal_type,
                                                typename CrsGraphType::global_ordinal_type,
                                                typename CrsGraphType::node_type>& domainImporter,
                                    const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                                 typename CrsGraphType::global_ordinal_type,
                                                                 typename CrsGraphType::node_type> >& domainMap,
                                    const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                                 typename CrsGraphType::global_ordinal_type,
                                                                 typename CrsGraphType::node_type> >& rangeMap,
                                    const Teuchos::RCP<Teuchos::ParameterList>& params);


    // Friend declaration for nonmember function.
    template<class CrsGraphType>
    friend Teuchos::RCP<CrsGraphType>
    exportAndFillCompleteCrsGraph (const Teuchos::RCP<const CrsGraphType>& sourceGraph,
                                    const Export<typename CrsGraphType::local_ordinal_type,
                                                 typename CrsGraphType::global_ordinal_type,
                                                 typename CrsGraphType::node_type>& exporter,
                                    const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                                 typename CrsGraphType::global_ordinal_type,
                                                                 typename CrsGraphType::node_type> >& domainMap,
                                    const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                                 typename CrsGraphType::global_ordinal_type,
                                                                 typename CrsGraphType::node_type> >& rangeMap,
                                    const Teuchos::RCP<Teuchos::ParameterList>& params);

    // Friend declaration for nonmember function.
    template<class CrsGraphType>
    friend Teuchos::RCP<CrsGraphType>
    exportAndFillCompleteCrsGraph (const Teuchos::RCP<const CrsGraphType>& sourceGraph,
                                    const Export<typename CrsGraphType::local_ordinal_type,
                                                 typename CrsGraphType::global_ordinal_type,
                                                 typename CrsGraphType::node_type>& rowExporter,
                                    const Export<typename CrsGraphType::local_ordinal_type,
                                                 typename CrsGraphType::global_ordinal_type,
                                                 typename CrsGraphType::node_type>& domainExporter,
                                    const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                                 typename CrsGraphType::global_ordinal_type,
                                                                 typename CrsGraphType::node_type> >& domainMap,
                                    const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                                 typename CrsGraphType::global_ordinal_type,
                                                                 typename CrsGraphType::node_type> >& rangeMap,
                                    const Teuchos::RCP<Teuchos::ParameterList>& params);

  public:
    void
    importAndFillComplete (Teuchos::RCP<CrsGraph<local_ordinal_type, global_ordinal_type, Node> >& destGraph,
                           const import_type& importer,
                           const Teuchos::RCP<const map_type>& domainMap,
                           const Teuchos::RCP<const map_type>& rangeMap,
                           const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null) const;

    void
    importAndFillComplete (Teuchos::RCP<CrsGraph<local_ordinal_type, global_ordinal_type, Node> >& destGraph,
                           const import_type& rowImporter,
                           const import_type& domainImporter,
                           const Teuchos::RCP<const map_type>& domainMap,
                           const Teuchos::RCP<const map_type>& rangeMap,
                           const Teuchos::RCP<Teuchos::ParameterList>& params) const;


    void
    exportAndFillComplete (Teuchos::RCP<CrsGraph<local_ordinal_type, global_ordinal_type, Node> >& destGraph,
                           const export_type& exporter,
                           const Teuchos::RCP<const map_type>& domainMap = Teuchos::null,
                           const Teuchos::RCP<const map_type>& rangeMap = Teuchos::null,
                           const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null) const;

    void
    exportAndFillComplete (Teuchos::RCP<CrsGraph<local_ordinal_type, global_ordinal_type, Node> >& destGraph,
                           const export_type& rowExporter,
                           const export_type& domainExporter,
                           const Teuchos::RCP<const map_type>& domainMap,
                           const Teuchos::RCP<const map_type>& rangeMap,
                           const Teuchos::RCP<Teuchos::ParameterList>& params) const;


  private:
    void
    transferAndFillComplete (Teuchos::RCP<CrsGraph<local_ordinal_type, global_ordinal_type, Node> >& destGraph,
                             const ::Tpetra::Details::Transfer<local_ordinal_type, global_ordinal_type, Node>& rowTransfer,
                             const Teuchos::RCP<const ::Tpetra::Details::Transfer<local_ordinal_type, global_ordinal_type, Node> > & domainTransfer,
                             const Teuchos::RCP<const map_type>& domainMap = Teuchos::null,
                             const Teuchos::RCP<const map_type>& rangeMap = Teuchos::null,
                             const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null) const;

  protected:
    // these structs are conveniences, to cut down on the number of
    // arguments to some of the methods below.
    struct SLocalGlobalViews {
      Teuchos::ArrayView<const global_ordinal_type> ginds;
      Teuchos::ArrayView<const local_ordinal_type>  linds;
    };
    struct SLocalGlobalNCViews {
      Teuchos::ArrayView<global_ordinal_type>       ginds;
      Teuchos::ArrayView<local_ordinal_type>        linds;
    };

    bool indicesAreAllocated () const;

    void
    allocateIndices(const ELocalGlobal lg, const bool verbose=false);



    void makeColMap (Teuchos::Array<int>& remotePIDs);

    std::pair<size_t, std::string>
    makeIndicesLocal(const bool verbose=false);

    void
    makeImportExport (Teuchos::Array<int>& remotePIDs,
                      const bool useRemotePIDs);



    size_t
    insertIndices (RowInfo& rowInfo,
                   const SLocalGlobalViews& newInds,
                   const ELocalGlobal lg,
                   const ELocalGlobal I);

    size_t
    insertGlobalIndicesImpl (const local_ordinal_type lclRow,
                             const global_ordinal_type inputGblColInds[],
                             const size_t numInputInds);

    size_t
    insertGlobalIndicesImpl (const RowInfo& rowInfo,
                             const global_ordinal_type inputGblColInds[],
                             const size_t numInputInds,
                             std::function<void(const size_t, const size_t, const size_t)> fun =
                                 std::function<void(const size_t, const size_t, const size_t)>());

    void
    insertLocalIndicesImpl (const local_ordinal_type lclRow,
                            const Teuchos::ArrayView<const local_ordinal_type>& gblColInds,
                            std::function<void(const size_t, const size_t, const size_t)> fun =
                                std::function<void(const size_t, const size_t, const size_t)>());

    size_t
    findGlobalIndices(const RowInfo& rowInfo,
                      const Teuchos::ArrayView<const global_ordinal_type>& indices,
                      std::function<void(const size_t, const size_t, const size_t)> fun) const;

    void
    insertGlobalIndicesFiltered (const local_ordinal_type lclRow,
                                 const global_ordinal_type gblColInds[],
                                 const local_ordinal_type numGblColInds);

    void
    insertGlobalIndicesIntoNonownedRows (const global_ordinal_type gblRow,
                                         const global_ordinal_type gblColInds[],
                                         const local_ordinal_type numGblColInds);

    static const bool useAtomicUpdatesByDefault =
#ifdef KOKKOS_ENABLE_SERIAL
      ! std::is_same<execution_space, Kokkos::Serial>::value;
#else
      true;
#endif // KOKKOS_ENABLE_SERIAL



    bool isMerged () const;

    void setLocallyModified ();

  private:
    void
    sortAndMergeAllIndices (const bool sorted, const bool merged);

    // mfh 08 May 2017: I only restore "protected" here for backwards
    // compatibility.
  protected:
    size_t sortAndMergeRowIndices (const RowInfo& rowInfo,
                                   const bool sorted,
                                   const bool merged);

    void
    setDomainRangeMaps (const Teuchos::RCP<const map_type>& domainMap,
                        const Teuchos::RCP<const map_type>& rangeMap);

    void staticAssertions() const;
    void clearGlobalConstants();

  public:
    bool haveGlobalConstants() const { return haveGlobalConstants_;}

    void computeGlobalConstants ();

    bool haveLocalOffRankOffsets() const { return haveLocalOffRankOffsets_;}

  protected:
    void computeLocalConstants ();

    RowInfo getRowInfo (const local_ordinal_type myRow) const;

    RowInfo getRowInfoFromGlobalRowIndex (const global_ordinal_type gblRow) const;

  public:

    local_graph_device_type getLocalGraphDevice () const;
    local_graph_host_type getLocalGraphHost () const;

  protected:

    void fillLocalGraph (const Teuchos::RCP<Teuchos::ParameterList>& params);

    void checkInternalState () const;

    void swap(CrsGraph<local_ordinal_type, global_ordinal_type, Node> & graph);

    // Friend the tester for CrsGraph::swap
    friend class Tpetra::crsGraph_Swap_Tester<local_ordinal_type, global_ordinal_type, Node>;


    Teuchos::RCP<const map_type> rowMap_;
    Teuchos::RCP<const map_type> colMap_;
    Teuchos::RCP<const map_type> rangeMap_;
    Teuchos::RCP<const map_type> domainMap_;

    Teuchos::RCP<const import_type> importer_;

    Teuchos::RCP<const export_type> exporter_;

    size_t nodeMaxNumRowEntries_ =
      Teuchos::OrdinalTraits<size_t>::invalid();

    global_size_t globalNumEntries_ =
      Teuchos::OrdinalTraits<global_size_t>::invalid();

    global_size_t globalMaxNumRowEntries_ =
      Teuchos::OrdinalTraits<global_size_t>::invalid();

  private:
    // Replacement for device view k_rowPtrs_
    // Device view rowPtrsUnpacked_dev_ takes place of k_rowPtrs_ 
    // Host view rowPtrsUnpacked_host_ takes place of copies and use of getEntryOnHost
    // Wish this could be a WrappedDualView, but deep_copies in DualView
    // don't work with const data views (e.g., StaticCrsGraph::row_map)
    // k_rowPtrs_ is offsets wrt the ALLOCATED indices array, not necessarily
    // the ACTUAL compressed indices array.
    // When !OptimizedStorage, k_rowPtrs_ may differ from ACTUAL compressed
    // indices array.  (Karen is skeptical that !OptimizedStorage works)
    // When OptimizedStorage, rowPtrsUnpacked_ = k_rowPtrsPacked_

    row_ptrs_device_view_type rowPtrsUnpacked_dev_;
    mutable row_ptrs_host_view_type rowPtrsUnpacked_host_;

    // Row offsets into the actual graph local indices
    // Device view rowPtrsUnpacked_dev_ takes place of lclGraph_.row_map

    row_ptrs_device_view_type rowPtrsPacked_dev_;
    mutable row_ptrs_host_view_type rowPtrsPacked_host_;

    bool packedUnpackedRowPtrsMatch_ = false;

  protected:
    void setRowPtrsUnpacked(const row_ptrs_device_view_type &dview) {
      packedUnpackedRowPtrsMatch_ = false;
      rowPtrsUnpacked_dev_ = dview;
      //Make sure stale host rowptrs are not kept
      rowPtrsUnpacked_host_ = row_ptrs_host_view_type();
    }

    const row_ptrs_device_view_type& getRowPtrsUnpackedDevice() const
    {
      return rowPtrsUnpacked_dev_;
    }

    const row_ptrs_host_view_type& getRowPtrsUnpackedHost() const
    {
      if(rowPtrsUnpacked_host_.extent(0) != rowPtrsUnpacked_dev_.extent(0))
      {
        //NOTE: not just using create_mirror_view here, because
        //we do want host/device to be in different memory, even if we're using a SharedSpace.
        //This is so that reads will never trigger a host-device transfer.
        //The exception is when 'device' views are HostSpace, then don't make another copy.
        if constexpr(std::is_same_v<typename Node::memory_space, Kokkos::HostSpace>)
        {
          rowPtrsUnpacked_host_ = rowPtrsUnpacked_dev_;
        }
        else
        {
          //Have to make this temporary because rowptrs are const-valued
          typename row_ptrs_host_view_type::non_const_type rowPtrsTemp(
              Kokkos::view_alloc(Kokkos::WithoutInitializing, "rowPtrsUnpacked_host_"), rowPtrsUnpacked_dev_.extent(0));
          Kokkos::deep_copy(rowPtrsTemp, rowPtrsUnpacked_dev_);
          rowPtrsUnpacked_host_= rowPtrsTemp;
        }
        //Also keep packed/unpacked views in sync, if they are known to have the same contents
        if(packedUnpackedRowPtrsMatch_)
        {
          rowPtrsPacked_host_ = rowPtrsUnpacked_host_;
        }
      }
      return rowPtrsUnpacked_host_;
    }

    void setRowPtrsPacked(const row_ptrs_device_view_type &dview) {
      packedUnpackedRowPtrsMatch_ = false;
      rowPtrsPacked_dev_ = dview;
      //Make sure stale host rowptrs are not kept
      rowPtrsPacked_host_ = row_ptrs_host_view_type();
    }

    const row_ptrs_device_view_type& getRowPtrsPackedDevice() const
    {
      return rowPtrsPacked_dev_;
    }

    const row_ptrs_host_view_type& getRowPtrsPackedHost() const
    {
      if(rowPtrsPacked_host_.extent(0) != rowPtrsPacked_dev_.extent(0))
      {
        //NOTE: not just using create_mirror_view here, because
        //we do want host/device to be in different memory, even if we're using a SharedSpace.
        //This is so that reads will never trigger a host-device transfer.
        //The exception is when 'device' views are HostSpace, then don't make another copy.
        if constexpr(std::is_same_v<typename Node::memory_space, Kokkos::HostSpace>)
        {
          rowPtrsPacked_host_ = rowPtrsPacked_dev_;
        }
        else
        {
          //Have to make this temporary because rowptrs are const-valued
          typename row_ptrs_host_view_type::non_const_type rowPtrsTemp(
              Kokkos::view_alloc(Kokkos::WithoutInitializing, "rowPtrsPacked_host_"), rowPtrsPacked_dev_.extent(0));
          Kokkos::deep_copy(rowPtrsTemp, rowPtrsPacked_dev_);
          rowPtrsPacked_host_= rowPtrsTemp;
        }
        //Also keep packed/unpacked views in sync, if they are known to have the same contents
        if(packedUnpackedRowPtrsMatch_)
        {
          rowPtrsUnpacked_host_ = rowPtrsPacked_host_;
        }
      }
      return rowPtrsPacked_host_;
    }

    // There are common cases where both packed and unpacked views are set to the same array.
    // Doing this in a single call can reduce dataspace on host, and reduce runtime by
    // removing a deep_copy from device to host.

    void setRowPtrs(const row_ptrs_device_view_type &dview) {
      packedUnpackedRowPtrsMatch_ = true;
      rowPtrsUnpacked_dev_ = dview;
      rowPtrsPacked_dev_ = dview;
      //Make sure stale host rowptrs are not kept
      rowPtrsUnpacked_host_ = row_ptrs_host_view_type();
      rowPtrsPacked_host_ = row_ptrs_host_view_type();
    }
    
    //TODO:  Make private -- matrix shouldn't access directly the guts of graph
  
    local_inds_wdv_type lclIndsUnpacked_wdv;

    mutable local_inds_wdv_type lclIndsPacked_wdv;

    //TODO:  Make private -- matrix shouldn't access directly the guts of graph


    // TODO: Make private -- matrix shouldn't access directly
    global_inds_wdv_type gblInds_wdv;

    typename local_inds_dualv_type::t_host::const_type
    getLocalIndsViewHost (const RowInfo& rowinfo) const;

    typename local_inds_dualv_type::t_dev::const_type
    getLocalIndsViewDevice (const RowInfo& rowinfo) const;

    typename global_inds_dualv_type::t_host::const_type
    getGlobalIndsViewHost (const RowInfo& rowinfo) const;

    typename global_inds_dualv_type::t_dev::const_type
    getGlobalIndsViewDevice (const RowInfo& rowinfo) const;

    typename local_inds_dualv_type::t_host
    getLocalIndsViewHostNonConst (const RowInfo& rowinfo);

    // FOR NOW...
    // KEEP k_numRowEntries_ (though switch from HostMirror to Host)
    // KEEP k_numAllocPerRow_ (though perhaps switch from HostMirror to Host)

    typename Kokkos::View<const size_t*, device_type>::HostMirror
    k_numAllocPerRow_;

    size_t numAllocForAllRows_;




    typedef typename Kokkos::View<size_t*, Kokkos::LayoutLeft, device_type>::HostMirror num_row_entries_type;

    // typedef Kokkos::View<
    //   size_t*,
    //   Kokkos::LayoutLeft,
    //   Kokkos::Device<
    //     typename Kokkos::View<
    //       size_t*,
    //       Kokkos::LayoutLeft,
    //       device_type>::HostMirror::execution_space,
    //     Kokkos::HostSpace> > num_row_entries_type;

    num_row_entries_type k_numRowEntries_;

    mutable offset_device_view_type k_offRankOffsets_;


    Details::EStorageStatus storageStatus_ =
      Details::STORAGE_1D_UNPACKED;

    bool indicesAreAllocated_ = false;
    bool indicesAreLocal_ = false;
    bool indicesAreGlobal_ = false;
    bool fillComplete_ = false;

    bool indicesAreSorted_ = true;
    bool noRedundancies_ = true;
    bool haveLocalConstants_ = false;
    bool haveGlobalConstants_ = false;
    mutable bool haveLocalOffRankOffsets_ = false;

    typedef typename std::map<global_ordinal_type, std::vector<global_ordinal_type> > nonlocals_type;

    nonlocals_type nonlocals_;

    bool sortGhostsAssociatedWithEachProcessor_ = true;

  private:
    static bool getDebug();

    bool debug_ = getDebug();

    static bool getVerbose();

    bool verbose_ = getVerbose();

  private:
    mutable bool need_sync_host_uvm_access = false;

    void set_need_sync_host_uvm_access() {
      need_sync_host_uvm_access = true;
    }

    void execute_sync_host_uvm_access() const {
      if(need_sync_host_uvm_access) {
        Kokkos::fence("CrsGraph::execute_sync_host_uvm_access");
        need_sync_host_uvm_access = false;
      }
    }
  }; // class CrsGraph

  template <class LocalOrdinal, class GlobalOrdinal, class Node>
  Teuchos::RCP<CrsGraph<LocalOrdinal, GlobalOrdinal, Node> >
  createCrsGraph(
    const Teuchos::RCP<
      const Map<LocalOrdinal, GlobalOrdinal, Node>>& map,
    size_t maxNumEntriesPerRow = 0,
    const Teuchos::RCP<Teuchos::ParameterList>& params =
      Teuchos::null)
  {
    using Teuchos::rcp;
    using graph_type = CrsGraph<LocalOrdinal, GlobalOrdinal, Node>;
    return rcp(new graph_type(map, maxNumEntriesPerRow,
                              params));
  }

  template<class CrsGraphType>
  Teuchos::RCP<CrsGraphType>
  importAndFillCompleteCrsGraph (const Teuchos::RCP<const CrsGraphType>& sourceGraph,
                                  const Import<typename CrsGraphType::local_ordinal_type,
                                               typename CrsGraphType::global_ordinal_type,
                                               typename CrsGraphType::node_type>& importer,
                                  const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                               typename CrsGraphType::global_ordinal_type,
                                                               typename CrsGraphType::node_type> >& domainMap = Teuchos::null,
                                  const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                               typename CrsGraphType::global_ordinal_type,
                                                               typename CrsGraphType::node_type> >& rangeMap = Teuchos::null,
                                  const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null)
  {
    Teuchos::RCP<CrsGraphType> destGraph;
    sourceGraph->importAndFillComplete (destGraph,importer,domainMap, rangeMap, params);
    return destGraph;
  }

  template<class CrsGraphType>
  Teuchos::RCP<CrsGraphType>
  importAndFillCompleteCrsGraph (const Teuchos::RCP<const CrsGraphType>& sourceGraph,
                                  const Import<typename CrsGraphType::local_ordinal_type,
                                               typename CrsGraphType::global_ordinal_type,
                                               typename CrsGraphType::node_type>& rowImporter,
                                  const Import<typename CrsGraphType::local_ordinal_type,
                                              typename CrsGraphType::global_ordinal_type,
                                              typename CrsGraphType::node_type>& domainImporter,
                                  const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                               typename CrsGraphType::global_ordinal_type,
                                                               typename CrsGraphType::node_type> >& domainMap,
                                  const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                               typename CrsGraphType::global_ordinal_type,
                                                               typename CrsGraphType::node_type> >& rangeMap,
                                  const Teuchos::RCP<Teuchos::ParameterList>& params)
  {
    Teuchos::RCP<CrsGraphType> destGraph;
    sourceGraph->importAndFillComplete (destGraph,rowImporter,domainImporter, domainMap, rangeMap, params);
    return destGraph;
  }

  template<class CrsGraphType>
  Teuchos::RCP<CrsGraphType>
  exportAndFillCompleteCrsGraph (const Teuchos::RCP<const CrsGraphType>& sourceGraph,
                                  const Export<typename CrsGraphType::local_ordinal_type,
                                               typename CrsGraphType::global_ordinal_type,
                                               typename CrsGraphType::node_type>& exporter,
                                  const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                               typename CrsGraphType::global_ordinal_type,
                                                               typename CrsGraphType::node_type> >& domainMap = Teuchos::null,
                                  const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                               typename CrsGraphType::global_ordinal_type,
                                                               typename CrsGraphType::node_type> >& rangeMap = Teuchos::null,
                                  const Teuchos::RCP<Teuchos::ParameterList>& params = Teuchos::null)
  {
    Teuchos::RCP<CrsGraphType> destGraph;
    sourceGraph->exportAndFillComplete (destGraph,exporter,domainMap, rangeMap, params);
    return destGraph;
  }

  template<class CrsGraphType>
  Teuchos::RCP<CrsGraphType>
  exportAndFillCompleteCrsGraph (const Teuchos::RCP<const CrsGraphType>& sourceGraph,
                                  const Export<typename CrsGraphType::local_ordinal_type,
                                               typename CrsGraphType::global_ordinal_type,
                                               typename CrsGraphType::node_type>& rowExporter,
                                  const Export<typename CrsGraphType::local_ordinal_type,
                                               typename CrsGraphType::global_ordinal_type,
                                               typename CrsGraphType::node_type>& domainExporter,
                                  const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                               typename CrsGraphType::global_ordinal_type,
                                                               typename CrsGraphType::node_type> >& domainMap,
                                  const Teuchos::RCP<const Map<typename CrsGraphType::local_ordinal_type,
                                                               typename CrsGraphType::global_ordinal_type,
                                                               typename CrsGraphType::node_type> >& rangeMap,
                                  const Teuchos::RCP<Teuchos::ParameterList>& params)
  {
    Teuchos::RCP<CrsGraphType> destGraph;
    sourceGraph->exportAndFillComplete (destGraph,rowExporter,domainExporter,domainMap, rangeMap, params);
    return destGraph;
  }


} // namespace Tpetra

#endif // TPETRA_CRSGRAPH_DECL_HPP