Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Zoltan2_AlgMetis.hpp
Go to the documentation of this file.
1 // @HEADER
2 // *****************************************************************************
3 // Zoltan2: A package of combinatorial algorithms for scientific computing
4 //
5 // Copyright 2012 NTESS and the Zoltan2 contributors.
6 // SPDX-License-Identifier: BSD-3-Clause
7 // *****************************************************************************
8 // @HEADER
9 
14 #ifndef _ZOLTAN2_ALGMETIS_HPP_
15 #define _ZOLTAN2_ALGMETIS_HPP_
16 
17 #include <Zoltan2_Algorithm.hpp>
18 #include <Zoltan2_GraphModel.hpp>
20 #include <Zoltan2_TPLTraits.hpp>
21 #ifdef HAVE_ZOLTAN2_METIS
22 #include "metis.h"
23 #endif
24 
25 namespace Zoltan2{
26 
27 template <typename Adapter>
28 class AlgMetis : public Algorithm<Adapter>
29 {
30  private:
31 
32  const RCP<const typename Adapter::base_adapter_t> adapter;
33  const RCP<Teuchos::ParameterList> pl;
34  const RCP<const Teuchos::Comm<int> > comm;
35  RCP<const Environment> env;
36  modelFlag_t graphFlags;
37 
38  public:
39 
41  const RCP<const typename Adapter::base_adapter_t> &adapter__,
42  const RCP<Teuchos::ParameterList> &pl__,
43  const RCP<const Teuchos::Comm<int> > &comm__,
44  RCP<const Environment> &env__,
45  const modelFlag_t &graphFlags__
46  ) : adapter(adapter__), pl(pl__), comm(comm__), env(env__), graphFlags(graphFlags__)
47  { }
48 
50  const RCP<GlobalOrderingSolution<typename Adapter::gno_t> > &/* solution */) {
51  throw std::logic_error("AlgMetis does not yet support global ordering.");
52  }
53 
56  {
57 #ifndef HAVE_ZOLTAN2_METIS
58  (void)solution; // remove unused parameter warning
59  throw std::runtime_error(
60  "BUILD ERROR: Metis requested but not compiled into Zoltan2.\n"
61  "Please set CMake flag Zoltan2_ENABLE_METIS:BOOL=ON.");
62 #else
63  typedef typename Adapter::gno_t gno_t;
64  typedef typename Adapter::lno_t lno_t;
65  typedef typename Adapter::offset_t offset_t;
66  typedef typename Adapter::scalar_t scalar_t;
67 
68  int ierr= 0;
69 
70  // Get EdgeList
71  const auto model = rcp(new GraphModel<Adapter>(adapter, env, comm, graphFlags));
72  const size_t nVtx = model->getLocalNumVertices();
73  const size_t nNnz = model->getLocalNumEdges();
74  lno_t *perm = (lno_t *) (solution->getPermutationRCP().getRawPtr());
75 
76  if (nVtx > 0 && nNnz > 0) {
77  ArrayView<const gno_t> edgeIds;
78  ArrayView<const offset_t> offsets;
79  ArrayView<StridedData<lno_t, scalar_t> > wgts; // wgts are ignored in NodeND
80  model->getEdgeList(edgeIds, offsets, wgts);
81 
82  // Prepare for calling metis
83  using Zoltan2OffsetView = typename Kokkos::View<offset_t*, Kokkos::HostSpace>;
84  using Zoltan2EdgeView = typename Kokkos::View<gno_t*, Kokkos::HostSpace>;
85  Zoltan2OffsetView zoltan2_rowptr (const_cast<offset_t*>(offsets.data()), nVtx+1);
86  Zoltan2EdgeView zoltan2_colidx (const_cast<gno_t*>(edgeIds.data()), nNnz);
87 
88  using MetisIdxView = typename Kokkos::View<idx_t*, Kokkos::HostSpace>;
89  MetisIdxView metis_rowptr;
90  MetisIdxView metis_colidx;
91 
92  // Symmetrize (always for now)
93  KokkosKernels::Impl::symmetrize_graph_symbolic_hashmap<
94  Zoltan2OffsetView, Zoltan2EdgeView, MetisIdxView, MetisIdxView, Kokkos::HostSpace::execution_space>
95  (nVtx, zoltan2_rowptr, zoltan2_colidx, metis_rowptr, metis_colidx);
96 
97  // Remove diagonals
98  idx_t metis_nVtx=0;
99  TPL_Traits<idx_t, size_t>::ASSIGN(metis_nVtx, nVtx);
100 
101  idx_t nnz = metis_rowptr(0);
102  idx_t old_nnz = nnz;
103  for (idx_t i = 0; i < metis_nVtx; i++) {
104  for (idx_t k = old_nnz; k < metis_rowptr(i+1); k++) {
105  if (metis_colidx(k) != i) {
106  metis_colidx(nnz) = metis_colidx(k);
107  nnz++;
108  }
109  }
110  old_nnz = metis_rowptr(i+1);
111  metis_rowptr(i+1) = nnz;
112  }
113 
114  // Allocate Metis perm/iperm
115  idx_t *metis_perm = new idx_t[nVtx];
116  idx_t *metis_iperm = new idx_t[nVtx];
117 
118  // Call metis
119  int info = METIS_NodeND(&metis_nVtx, metis_rowptr.data(), metis_colidx.data(),
120  NULL, NULL, metis_perm, metis_iperm);
121  if (METIS_OK != info) {
122  throw std::runtime_error(std::string("METIS_NodeND returned info = " + info));
123  }
124 
125  // Copy result back
126  for (size_t i = 0; i < nVtx; i++)
127  TPL_Traits<lno_t, idx_t>::ASSIGN(perm[i], metis_perm[i]);
128 
129  delete [] metis_iperm;
130  delete [] metis_perm;
131  } else {
132  for (size_t i = 0; i < nVtx; i++)
133  perm[i] = i;
134  }
135 
136  solution->setHavePerm(true);
137  return ierr;
138 #endif
139  }
140 };
141 
142 }
143 
144 
145 
146 #endif
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
map_t::global_ordinal_type gno_t
Definition: mapRemotes.cpp:27
Defines the OrderingSolution class.
AlgMetis(const RCP< const typename Adapter::base_adapter_t > &adapter__, const RCP< Teuchos::ParameterList > &pl__, const RCP< const Teuchos::Comm< int > > &comm__, RCP< const Environment > &env__, const modelFlag_t &graphFlags__)
Adapter::scalar_t scalar_t
Algorithm defines the base class for all algorithms.
map_t::local_ordinal_type lno_t
Definition: mapRemotes.cpp:26
static void ASSIGN(first_t &a, second_t b)
Traits class to handle conversions between gno_t/lno_t and TPL data types (e.g., ParMETIS&#39;s idx_t...
int globalOrder(const RCP< GlobalOrderingSolution< typename Adapter::gno_t > > &)
Ordering method.
GraphModel defines the interface required for graph models.
int localOrder(const RCP< LocalOrderingSolution< typename Adapter::lno_t > > &solution)
Ordering method.
Defines the GraphModel interface.