Tpetra_CrsGraph_decl.hpp

Go to the documentation of this file.

// @HEADER
// *****************************************************************************
//          Tpetra: Templated Linear Algebra Services Package
//
// Copyright 2008 NTESS and the Tpetra contributors.
// SPDX-License-Identifier: BSD-3-Clause
// *****************************************************************************
// @HEADER

#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 "Teuchos_CommHelpers.hpp"
#include "Teuchos_Describable.hpp"
#include "Teuchos_OrdinalTraits.hpp"
#include "Teuchos_ParameterListAcceptorDefaultBase.hpp"

#include "KokkosSparse_StaticCrsGraph.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
#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 =
      KokkosSparse::StaticCrsGraph<local_ordinal_type, Kokkos::LayoutLeft,
                                   device_type, void, size_t>;

#if KOKKOS_VERSION >= 40799
  using local_graph_host_type = typename local_graph_device_type::host_mirror_type;
#else
  using local_graph_host_type = typename local_graph_device_type::HostMirror;
#endif

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

 public:
  // 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 = 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      = 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 row_ptrs_device_view_type& rowPointers,
           const local_inds_wdv_type& columnIndices,
           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;

  using dist_object_type::
      copyAndPermute;  

  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;

  using dist_object_type::packAndPrepare;  

  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;

  using dist_object_type::unpackAndCombine;  

  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 host_mirror_type to Host)
  // KEEP k_numAllocPerRow_ (though perhaps switch from host_mirror_type to Host)

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

  size_t numAllocForAllRows_;




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

  // typedef Kokkos::View<
  //   size_t*,
  //   Kokkos::LayoutLeft,
  //   Kokkos::Device<
  //     typename Kokkos::View<
  //       size_t*,
  //       Kokkos::LayoutLeft,
  //       device_type>::host_mirror_type::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