Zoltan2
Loading...
Searching...
No Matches
Zoltan2_OrderingProblem.hpp
Go to the documentation of this file.
1// @HEADER
2//
3// ***********************************************************************
4//
5// Zoltan2: A package of combinatorial algorithms for scientific computing
6// Copyright 2012 Sandia Corporation
7//
8// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9// the U.S. Government retains certain rights in this software.
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//
18// 2. Redistributions in binary form must reproduce the above copyright
19// notice, this list of conditions and the following disclaimer in the
20// documentation and/or other materials provided with the distribution.
21//
22// 3. Neither the name of the Corporation nor the names of the
23// contributors may be used to endorse or promote products derived from
24// this software without specific prior written permission.
25//
26// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37//
38// Questions? Contact Karen Devine (kddevin@sandia.gov)
39// Erik Boman (egboman@sandia.gov)
40// Siva Rajamanickam (srajama@sandia.gov)
41//
42// ***********************************************************************
43//
44// @HEADER
45
50#ifndef _ZOLTAN2_ORDERINGPROBLEM_HPP_
51#define _ZOLTAN2_ORDERINGPROBLEM_HPP_
52
53#include <Zoltan2_Problem.hpp>
57
59#include <string>
60#ifdef HAVE_ZOLTAN2_OVIS
61#include <ovis.h>
62#endif
63
64
65
66
67
68#include <bitset>
69
70using Teuchos::rcp_dynamic_cast;
71
72namespace Zoltan2{
73
75
94template<typename Adapter>
95class OrderingProblem : public Problem<Adapter>
96{
97public:
98
99 typedef typename Adapter::scalar_t scalar_t;
100 typedef typename Adapter::gno_t gno_t;
101 typedef typename Adapter::lno_t lno_t;
102 typedef typename Adapter::user_t user_t;
103 typedef typename Adapter::base_adapter_t base_adapter_t;
104
105#ifdef HAVE_ZOLTAN2_MPI
106 typedef Teuchos::OpaqueWrapper<MPI_Comm> mpiWrapper_t;
107#endif
108
111 virtual ~OrderingProblem() {}
112
113 OrderingProblem(Adapter *A, ParameterList *p,
114 const RCP<const Teuchos::Comm<int> > &comm) :
115 Problem<Adapter>(A, p, comm)
116 {
117 HELLO;
118 createOrderingProblem();
119 }
120
121#ifdef HAVE_ZOLTAN2_MPI
124 OrderingProblem(Adapter *A, ParameterList *p, MPI_Comm mpicomm) :
125 OrderingProblem(A, p,
126 rcp<const Comm<int> >(new Teuchos::MpiComm<int>(
127 Teuchos::opaqueWrapper(mpicomm))))
128 {}
129#endif
130
133 OrderingProblem(Adapter *A, ParameterList *p) :
134 OrderingProblem(A, p, Tpetra::getDefaultComm())
135 {}
136
139 static void getValidParameters(ParameterList & pl)
140 {
141
142#ifdef INCLUDE_ZOLTAN2_EXPERIMENTAL
144#endif
145
146 RCP<Teuchos::StringValidator> order_method_Validator =
147 Teuchos::rcp( new Teuchos::StringValidator(
148 Teuchos::tuple<std::string>( "rcm", "metis", "minimum_degree", "natural",
149 "random", "sorted_degree", "scotch", "nd" )));
150 pl.set("order_method", "rcm", "order algorithm",
151 order_method_Validator);
152
153 RCP<Teuchos::StringValidator> order_method_type_Validator =
154 Teuchos::rcp( new Teuchos::StringValidator(
155 Teuchos::tuple<std::string>( "local", "global", "both" )));
156 pl.set("order_method_type", "local", "local or global or both",
157 order_method_type_Validator);
158
159 RCP<Teuchos::StringValidator> order_package_Validator = Teuchos::rcp(
160 new Teuchos::StringValidator(
161 Teuchos::tuple<std::string>( "amd", "package2", "package3" )));
162 pl.set("order_package", "amd", "package to use in ordering",
163 order_package_Validator);
164
165 RCP<Teuchos::StringValidator> rcm_root_selection_Validator = Teuchos::rcp(
166 new Teuchos::StringValidator(
167 Teuchos::tuple<std::string>( "pseudoperipheral", "first", "smallest_degree" )));
168 pl.set("root_method", "pseudoperipheral", "method for selecting RCM root",
169 rcm_root_selection_Validator);
170 }
171
173 //
174 // \param updateInputData If true this indicates that either
175 // this is the first attempt at solution, or that we
176 // are computing a new solution and the input data has
177 // changed since the previous solution was computed.
178 // If false, this indicates that we are computing a
179 // new solution using the same input data was used for
180 // the previous solution, even though the parameters
181 // may have been changed.
182 //
183 // For the sake of performance, we ask the caller to set \c updateInputData
184 // to false if he/she is computing a new solution using the same input data,
185 // but different problem parameters, than that which was used to compute
186 // the most recent solution.
187
188 void solve(bool updateInputData=true);
189
191 //
192 // \return a reference to the solution to the most recent solve().
193
195 if(localOrderingSolution_ == Teuchos::null) {
196 throw std::logic_error( "OrderingProblem was not created with local"
197 " ordering. Set parameter order_method_type to local or both."
198 " Or use getGlobalOrderingSolution()." );
199 }
200 return setupSolution(localOrderingSolution_);
201 }
202
204 //
205 // \return a reference to the solution to the most recent solve().
206
208 if(globalOrderingSolution_ == Teuchos::null) {
209 throw std::logic_error( "OrderingProblem was not created with global"
210 " ordering. Set parameter order_method_type to global or both."
211 " Or use getLocalOrderingSolution()." );
212 }
213 return setupSolution(globalOrderingSolution_);
214 }
215
216private:
217 template<typename ordering_solution_t>
218 ordering_solution_t *setupSolution(RCP<ordering_solution_t> solution) {
219 // std::cout << "havePerm= " << solution->havePerm() << " haveInverse= "
220 // << solution->haveInverse() << std::endl;
221 // Compute Perm or InvPerm, if one is missing.
222 if (!(solution->havePerm()))
223 solution->computePerm();
224 if (!(solution->haveInverse()))
225 solution->computeInverse();
226 return solution.getRawPtr();
227 }
228
229 void createOrderingProblem();
230
231 // local or global ordering is determined by which RCP is NULL
232 RCP<LocalOrderingSolution<lno_t> > localOrderingSolution_;
233 RCP<GlobalOrderingSolution<gno_t> > globalOrderingSolution_;
234
235 size_t localNumObjects_;
236};
237
239template <typename Adapter>
240void OrderingProblem<Adapter>::solve(bool /* updateInputData */)
241{
242 HELLO;
243
244 // TODO: Assuming one MPI process now. nVtx = ngids = nlids
245 try
246 {
247 std::string method_type = this->params_->template
248 get<std::string>("order_method_type", "local");
249
250 if(method_type == "local" || method_type == "both") {
251 localOrderingSolution_ = rcp(new LocalOrderingSolution<lno_t>(localNumObjects_));
252 }
253 if(method_type == "global" || method_type == "both") {
254 globalOrderingSolution_ = rcp(new GlobalOrderingSolution<gno_t>(localNumObjects_));
255 }
256 }
258
259 // Determine which algorithm to use based on defaults and parameters.
260 // TODO: Use rcm if graph model is defined, otherwise use natural.
261 // Need some exception handling here, too.
262
263 std::string method = this->params_->template
264 get<std::string>("order_method", "rcm");
265
266 // TODO: Ignore case
267 try
268 {
269
270 // could be a template... seems maybe more awkward
271 // added this to avoid duplicating local/global below
272 // so many times.
273 #define ZOLTAN2_COMPUTE_ORDERING \
274 if(localOrderingSolution_ != Teuchos::null) { \
275 alg.localOrder(localOrderingSolution_); \
276 } \
277 if(globalOrderingSolution_ != Teuchos::null) { \
278 alg.globalOrder(globalOrderingSolution_); \
279 }
280
281 modelFlag_t graphFlags;
282 graphFlags.set(REMOVE_SELF_EDGES);
283 graphFlags.set(BUILD_LOCAL_GRAPH);
284
285 if (method.compare("rcm") == 0) {
286 AlgRCM<base_adapter_t> alg(this->baseInputAdapter_, this->params_,
287 this->comm_, this->envConst_, graphFlags);
289 }
290 else if (method.compare("natural") == 0) {
291 AlgNatural<base_adapter_t> alg(this->baseInputAdapter_, this->params_,
292 this->comm_, this->envConst_);
294 }
295 else if (method.compare("random") == 0) {
296 AlgRandom<base_adapter_t> alg(this->baseInputAdapter_, this->params_,
297 this->comm_, this->envConst_);
299 }
300 else if (method.compare("sorted_degree") == 0) {
301 AlgSortedDegree<base_adapter_t> alg(this->baseInputAdapter_, this->params_,
302 this->comm_, this->envConst_,
303 graphFlags);
305 }
306 else if (method.compare("metis") == 0) {
307 AlgMetis<base_adapter_t> alg(this->baseInputAdapter_, this->params_,
308 this->comm_, this->envConst_, graphFlags);
310 }
311 else if (method.compare("minimum_degree") == 0) {
312 std::string pkg = this->params_->template get<std::string>(
313 "order_package", "amd");
314 if (pkg.compare("amd") == 0)
315 {
316 AlgAMD<base_adapter_t> alg(this->baseInputAdapter_,
317 this->params_, this->comm_, this->envConst_, graphFlags);
319 }
320 }
321 else if (method.compare("scotch") == 0) { // BDD Adding scotch ordering
322 AlgPTScotch<Adapter> alg(this->envConst_, this->comm_,
323 this->baseInputAdapter_);
325 }
326
327#ifdef INCLUDE_ZOLTAN2_EXPERIMENTAL
328 else if (method.compare("nd") == 0) {
329 AlgND<base_adapter_t> alg(this->envConst_, this->comm_, this->baseInputAdapter_, graphFlags);
331 }
332#endif
333
334 }
336}
337
339//template <typename Adapter>
340//void OrderingProblem<Adapter>::redistribute()
341//{
342// HELLO;
343//}
344
347// Method with common functionality for creating a OrderingProblem.
348// Individual constructors do appropriate conversions of input, etc.
349// This method does everything that all constructors must do.
350
351template <typename Adapter>
353{
354 HELLO;
355 using Teuchos::ParameterList;
356
357 // Determine which parameters are relevant here.
358 // For now, assume parameters similar to Zoltan:
359 // MODEL = graph, hypergraph, geometric, ids
360 // ALGORITHM = rcm, random, amd
361
362 ModelType modelType = IdentifierModelType; //default, change later
363 std::string method = this->params_->template
364 get<std::string>("order_method", "rcm");
365
366 if ((method == std::string("rcm")) ||
367 (method == std::string("sorted_degree")) ||
368 (method == std::string("metis")) ||
369 (method == std::string("minimum_degree"))) {
370 modelType = GraphModelType;
371 }
372
373#ifdef INCLUDE_ZOLTAN2_EXPERIMENTAL
374 if ((method == std::string("nd")))
375 {
376 modelType = GraphModelType;
377 }
378
379#endif
380
381 // Select Model based on parameters and InputAdapter type
382
383 // std::bitset<NUM_MODEL_FLAGS> graphFlags;
384 // std::bitset<NUM_MODEL_FLAGS> idFlags;
385
386
387 //MMW: need to change this to allow multiple models
388 // as I did with partitioning, use modelAvail_
389
390 const auto adapterType = this->baseInputAdapter_->adapterType();
391 switch (modelType)
392 {
393
394 case GraphModelType:
395 {
396 switch (adapterType)
397 {
399 {
400 localNumObjects_ = this->baseInputAdapter_->getLocalNumIDs();
401 }
402 break;
403
404 case GraphAdapterType:
405 {
406 const auto ia = dynamic_cast<const GraphAdapter<user_t> *>(&(*(this->baseInputAdapter_)));
407 localNumObjects_ = ia->getLocalNumVertices();
408 }
409 break;
410
411 case MeshAdapterType:
412 {
413 const auto ia = dynamic_cast<const MeshAdapter<user_t> *>(&(*(this->baseInputAdapter_)));
414 localNumObjects_ = ia->getLocalNumOf(ia->getPrimaryEntityType());
415 }
416 break;
417
418 default:{
419 // Avoid warning
420 }
421 }
422 }
423 break;
424
426 {
427 localNumObjects_ = this->baseInputAdapter_->getLocalNumIDs();
428 }
429 break;
430
433 {
434 std::cout << __func__zoltan2__
435 << " Model type " << modelType << " not yet supported."
436 << std::endl;
437 }
438 break;
439
440 default:
441 {
442 std::cout << __func__zoltan2__ << " Invalid model" << modelType
443 << std::endl;
444 }
445 break;
446 }
447}
448} //namespace Zoltan2
449#endif
Defines the Zoltan2_EvaluateOrdering.hpp class.
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
#define __func__zoltan2__
Defines the GraphModel interface.
#define ZOLTAN2_COMPUTE_ORDERING
Defines the OrderingSolution class.
Defines the Problem base class.
#define HELLO
static void getValidParameters(ParameterList &pl)
Set up validators specific to this algorithm.
OrderingProblem sets up ordering problems for the user.
virtual ~OrderingProblem()
Destructor.
Adapter::base_adapter_t base_adapter_t
void solve(bool updateInputData=true)
Direct the problem to create a solution.
LocalOrderingSolution< lno_t > * getLocalOrderingSolution()
Get the local ordering solution to the problem.
OrderingProblem(Adapter *A, ParameterList *p, const RCP< const Teuchos::Comm< int > > &comm)
static void getValidParameters(ParameterList &pl)
Set up validators specific to this Problem.
OrderingProblem(Adapter *A, ParameterList *p)
Constructor that uses a default communicator.
GlobalOrderingSolution< gno_t > * getGlobalOrderingSolution()
Get the global ordering solution to the problem.
Problem base class from which other classes (PartitioningProblem, ColoringProblem,...
Created by mbenlioglu on Aug 31, 2020.
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
ModelType
An identifier for the general type of model.
@ IdentifierModelType
@ HypergraphModelType
@ CoordinateModelType
@ GraphAdapterType
graph data
@ MatrixAdapterType
matrix data
@ MeshAdapterType
mesh data
@ REMOVE_SELF_EDGES
algorithm requires no self edges
@ BUILD_LOCAL_GRAPH
model represents graph within only one rank