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

#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 "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_type = Kokkos::StaticCrsGraph<local_ordinal_type,
                                                    Kokkos::LayoutLeft,
                                                    device_type>;

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



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

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

    CrsGraph (const Teuchos::RCP<const map_type>& rowMap,
              const Teuchos::ArrayView<const size_t>& numEntPerRow,
              const ProfileType pftype = TPETRA_DEFAULT_PROFILE_TYPE,
              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 ProfileType pftype = TPETRA_DEFAULT_PROFILE_TYPE,
              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*, execution_space>& numEntPerRow,
              const ProfileType pftype = TPETRA_DEFAULT_PROFILE_TYPE,
              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 ProfileType pftype = TPETRA_DEFAULT_PROFILE_TYPE,
              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_type::row_map_type& rowPointers,
              const typename local_graph_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_type& lclGraph,
              const Teuchos::RCP<Teuchos::ParameterList>& params);

    CrsGraph (const local_graph_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_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 getNodeNumRows () const override;


    size_t getNodeNumCols () const override;

    global_ordinal_type getIndexBase () const override;


    global_size_t getGlobalNumEntries () const override;

    size_t getNodeNumEntries() const override;


    size_t
    getNumEntriesInGlobalRow (global_ordinal_type globalRow) const override;

    size_t
    getNumEntriesInLocalRow (local_ordinal_type localRow) const override;

    size_t getNodeAllocationSize () const;

    size_t getNumAllocatedEntriesInGlobalRow (global_ordinal_type globalRow) const;

    size_t getNumAllocatedEntriesInLocalRow (local_ordinal_type localRow) const;

    size_t getGlobalMaxNumRowEntries () const override;

    size_t getNodeMaxNumRowEntries () 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;

    ProfileType getProfileType () const;

    void
    getGlobalRowCopy (global_ordinal_type gblRow,
                      const Teuchos::ArrayView<global_ordinal_type>& gblColInds,
                      size_t& numColInds) const override;

    void
    getLocalRowCopy (local_ordinal_type lclRow,
                     const Teuchos::ArrayView<local_ordinal_type>& lclColInds,
                     size_t& numColInds) const override;

    void
    getGlobalRowView (const global_ordinal_type gblRow,
                      Teuchos::ArrayView<const global_ordinal_type>& gblColInds) const override;

    bool supportsRowViews () const override;

    void
    getLocalRowView (const local_ordinal_type lclRow,
                     Teuchos::ArrayView<const local_ordinal_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;

    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) 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,
      Distributor& distor) override;

    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,
          Distributor& distor) 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,
                    Distributor& distor) 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,
                       Distributor& distor) const;

    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,
     Distributor& distor,
     const CombineMode combineMode) override;



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

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

    void
    getNumEntriesPerLocalRowUpperBound (Teuchos::ArrayRCP<const size_t>& boundPerLocalRow,
                                        size_t& boundForAllLocalRows,
                                        bool& boundSameForAllLocalRows) const;

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

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

    Teuchos::ArrayRCP<const size_t> getNodeRowPtrs () const;


    Teuchos::ArrayRCP<const local_ordinal_type> getNodePackedIndices () 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
    replaceDomainMapAndImporter (const Teuchos::RCP<const map_type>& newDomainMap,
                                 const Teuchos::RCP<const import_type>& newImporter);

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

    template<class ViewType, class OffsetViewType >
    struct pack_functor {
      typedef typename ViewType::execution_space execution_space;
      ViewType src;
      ViewType dest;
      OffsetViewType src_offset;
      OffsetViewType dest_offset;
      typedef typename OffsetViewType::non_const_value_type ScalarIndx;

      pack_functor(ViewType dest_, ViewType src_, OffsetViewType dest_offset_, OffsetViewType 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
    findLocalIndices(const RowInfo& rowInfo,
                     const Teuchos::ArrayView<const local_ordinal_type>& indices,
                     std::function<void(const size_t, const size_t, const size_t)> fun) const;

    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 ();

  protected:
    void computeLocalConstants ();

    RowInfo getRowInfo (const local_ordinal_type myRow) const;

    RowInfo getRowInfoFromGlobalRowIndex (const global_ordinal_type gblRow) const;

    Teuchos::ArrayView<const local_ordinal_type>
    getLocalView (const RowInfo& rowinfo) const;

    Teuchos::ArrayView<local_ordinal_type>
    getLocalViewNonConst (const RowInfo& rowinfo);

    local_ordinal_type
    getLocalViewRawConst (const local_ordinal_type*& lclInds,
                          local_ordinal_type& capacity,
                          const RowInfo& rowInfo) const;

  private:

    Kokkos::View<const local_ordinal_type*, execution_space, Kokkos::MemoryUnmanaged>
    getLocalKokkosRowView (const RowInfo& rowInfo) const;

    Kokkos::View<local_ordinal_type*, execution_space, Kokkos::MemoryUnmanaged>
    getLocalKokkosRowViewNonConst (const RowInfo& rowInfo);

    Kokkos::View<const global_ordinal_type*, execution_space, Kokkos::MemoryUnmanaged>
    getGlobalKokkosRowView (const RowInfo& rowInfo) const;

  protected:

    Teuchos::ArrayView<const global_ordinal_type>
    getGlobalView (const RowInfo& rowinfo) const;

    Teuchos::ArrayView<global_ordinal_type>
    getGlobalViewNonConst (const RowInfo& rowinfo);

    local_ordinal_type
    getGlobalViewRawConst (const global_ordinal_type*& gblInds,
                           local_ordinal_type& capacity,
                           const RowInfo& rowInfo) const;


  public:


    local_graph_type getLocalGraph () 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_;

    local_graph_type lclGraph_;

    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();

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

    size_t numAllocForAllRows_;



    typename local_graph_type::entries_type::non_const_type k_lclInds1D_;

    typedef Kokkos::View<global_ordinal_type*, execution_space> t_GlobalOrdinal_1D;

    t_GlobalOrdinal_1D k_gblInds1D_;

    typename local_graph_type::row_map_type::const_type k_rowPtrs_;

    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_;


    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;

    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();

  }; // 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>;
    const ProfileType pftype = TPETRA_DEFAULT_PROFILE_TYPE;
    return rcp(new graph_type(map, maxNumEntriesPerRow,
                              pftype, 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