Zoltan2
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>
56 
57 #include <Zoltan2_GraphModel.hpp>
58 #include <string>
59 #ifdef HAVE_ZOLTAN2_OVIS
60 #include <ovis.h>
61 #endif
62 
63 #include <bitset>
64 
65 using Teuchos::rcp_dynamic_cast;
66 
67 namespace Zoltan2{
68 
70 
89 template<typename Adapter>
90 class OrderingProblem : public Problem<Adapter>
91 {
92 public:
93 
94  typedef typename Adapter::scalar_t scalar_t;
95  typedef typename Adapter::gno_t gno_t;
96  typedef typename Adapter::lno_t lno_t;
97  typedef typename Adapter::user_t user_t;
99 
100 #ifdef HAVE_ZOLTAN2_MPI
101  typedef Teuchos::OpaqueWrapper<MPI_Comm> mpiWrapper_t;
102 #endif
103 
106  virtual ~OrderingProblem() {};
107 
108 
109 #ifdef HAVE_ZOLTAN2_MPI
110 
112  OrderingProblem(Adapter *A, ParameterList *p, MPI_Comm comm)
113  : Problem<Adapter>(A, p, comm)
114  {
115  HELLO;
116  createOrderingProblem();
117  };
118 #endif
119 
122  OrderingProblem(Adapter *A, ParameterList *p) : Problem<Adapter>(A, p)
123  {
124  HELLO;
125  createOrderingProblem();
126  };
127 
130  static void getValidParameters(ParameterList & pl)
131  {
132  RCP<Teuchos::StringValidator> order_method_Validator =
133  Teuchos::rcp( new Teuchos::StringValidator(
134  Teuchos::tuple<std::string>( "rcm", "minimum_degree", "natural",
135  "random", "sorted_degree", "scotch", "nd" )));
136  pl.set("order_method", "rcm", "order algorithm",
137  order_method_Validator);
138 
139  RCP<Teuchos::StringValidator> order_package_Validator = Teuchos::rcp(
140  new Teuchos::StringValidator(
141  Teuchos::tuple<std::string>( "amd", "package2", "package3" )));
142  pl.set("order_package", "amd", "package to use in ordering",
143  order_package_Validator);
144  }
145 
147  //
148  // \param updateInputData If true this indicates that either
149  // this is the first attempt at solution, or that we
150  // are computing a new solution and the input data has
151  // changed since the previous solution was computed.
152  // If false, this indicates that we are computing a
153  // new solution using the same input data was used for
154  // the previous solution, even though the parameters
155  // may have been changed.
156  //
157  // For the sake of performance, we ask the caller to set \c updateInputData
158  // to false if he/she is computing a new solution using the same input data,
159  // but different problem parameters, than that which was used to compute
160  // the most recent solution.
161 
162  void solve(bool updateInputData=true);
163 
165  //
166  // \return a reference to the solution to the most recent solve().
167 
169  // std::cout << "havePerm= " << solution_->havePerm() << " haveInverse= " << solution_->haveInverse() << std::endl;
170  // Compute Perm or InvPerm, if one is missing.
171  if (!(solution_->havePerm()))
172  solution_->computePerm();
173  if (!(solution_->haveInverse()))
174  solution_->computeInverse();
175  return solution_.getRawPtr();
176  };
177 
178 private:
179  void createOrderingProblem();
180 
181  RCP<OrderingSolution<lno_t, gno_t> > solution_;
182 
183 };
184 
186 template <typename Adapter>
188 {
189  HELLO;
190 
191  size_t nVtx = this->baseModel_->getLocalNumObjects();
192 
193  // TODO: Assuming one MPI process now. nVtx = ngids = nlids
194  try
195  {
196  this->solution_ = rcp(new OrderingSolution<lno_t, gno_t>(nVtx));
197  }
199 
200  // Reset status for perm and InvPerm.
201  this->solution_->setHavePerm(false);
202  this->solution_->setHaveInverse(false);
203 
204  // Determine which algorithm to use based on defaults and parameters.
205  // TODO: Use rcm if graph model is defined, otherwise use natural.
206  // Need some exception handling here, too.
207 
208  std::string method = this->params_->template get<std::string>("order_method", "rcm");
209 
210  // TODO: Ignore case
211  try
212  {
213  if (method.compare("rcm") == 0)
214  {
215  AlgRCM<base_adapter_t> alg(this->graphModel_,
216  this->params_, this->comm_);
217  alg.order(this->solution_);
218  }
219  else if (method.compare("natural") == 0)
220  {
221  AlgNatural<base_adapter_t> alg(this->identifierModel_,
222  this->params_, this->comm_);
223  alg.order(this->solution_);
224  }
225  else if (method.compare("random") == 0)
226  {
227  AlgRandom<base_adapter_t> alg(this->identifierModel_,
228  this->params_, this->comm_);
229  alg.order(this->solution_);
230  }
231  else if (method.compare("sorted_degree") == 0)
232  {
233  AlgSortedDegree<base_adapter_t> alg(this->graphModel_,
234  this->params_, this->comm_);
235  alg.order(this->solution_);
236  }
237  else if (method.compare("minimum_degree") == 0)
238  {
239  std::string pkg = this->params_->template get<std::string>("order_package", "amd");
240  if (pkg.compare("amd") == 0)
241  {
242  AlgAMD<base_adapter_t> alg(this->graphModel_,
243  this->params_, this->comm_);
244  alg.order(this->solution_);
245  }
246  }
247  else if (method.compare("scotch") == 0) // BDD Adding scotch ordering
248  {
249  AlgPTScotch<Adapter> alg(this->envConst_,
250  this->comm_,
251  this->baseInputAdapter_);
252  alg.order(this->solution_);
253  }
254 
255 #ifdef INCLUDE_ZOLTAN2_EXPERIMENTAL_WOLF
256  else if (method == std::string("nd"))
257  {
258  AlgND<Adapter> alg(this->envConst_,this->comm_,this->graphModel_,
259  this->coordinateModel_,this->baseInputAdapter_);
260 
261  alg.order(this->solution_);
262  }
263 #endif
264 
265  }
267 }
268 
270 //template <typename Adapter>
271 //void OrderingProblem<Adapter>::redistribute()
272 //{
273 // HELLO;
274 //}
275 
278 // Method with common functionality for creating a OrderingProblem.
279 // Individual constructors do appropriate conversions of input, etc.
280 // This method does everything that all constructors must do.
281 
282 template <typename Adapter>
284 {
285  HELLO;
286  using Teuchos::ParameterList;
287 
288 // std::cout << __func__zoltan2__ << " input adapter type "
289 // << this->inputAdapter_->inputAdapterType() << " "
290 // << this->inputAdapter_->inputAdapterName() << std::endl;
291 
292 #ifdef HAVE_ZOLTAN2_OVIS
293  ovis_enabled(this->comm_->getRank());
294 #endif
295 
296  // Determine which parameters are relevant here.
297  // For now, assume parameters similar to Zoltan:
298  // MODEL = graph, hypergraph, geometric, ids
299  // ALGORITHM = rcm, random, amd
300 
301  ModelType modelType = IdentifierModelType; //default, change later
302  std::string method = this->params_->template get<std::string>("order_method", "rcm");
303 
304  if ((method == std::string("rcm")) ||
305  (method == std::string("sorted_degree")) ||
306  (method == std::string("minimum_degree"))) {
307  modelType = GraphModelType;
308  }
309 
310 #ifdef INCLUDE_ZOLTAN2_EXPERIMENTAL_WOLF
311  if ((method == std::string("nd")))
312  {
313  modelType = GraphModelType;
314  }
315 
316 #endif
317 
318  // Select Model based on parameters and InputAdapter type
319 
320  std::bitset<NUM_MODEL_FLAGS> graphFlags;
321  std::bitset<NUM_MODEL_FLAGS> idFlags;
322 
323 
324  //MMW: need to change this to allow multiple models
325  // as I did with partitioning, use modelAvail_
326 
327  switch (modelType) {
328 
329  case GraphModelType:
330  graphFlags.set(REMOVE_SELF_EDGES);
331  graphFlags.set(BUILD_LOCAL_GRAPH);
332  this->graphModel_ = rcp(new GraphModel<base_adapter_t>(
333  this->baseInputAdapter_, this->envConst_, this->comm_, graphFlags));
334 
335  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
336  this->graphModel_);
337 
338  break;
339 
340 
341 
342  case IdentifierModelType:
343  this->identifierModel_ = rcp(new IdentifierModel<base_adapter_t>(
344  this->baseInputAdapter_, this->envConst_, this->comm_, idFlags));
345 
346  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
347  this->identifierModel_);
348 
349  break;
350 
351  case HypergraphModelType:
352  case CoordinateModelType:
353  std::cout << __func__zoltan2__
354  << " Model type " << modelType << " not yet supported."
355  << std::endl;
356  break;
357 
358  default:
359  std::cout << __func__zoltan2__ << " Invalid model" << modelType
360  << std::endl;
361  break;
362  }
363 }
364 } //namespace Zoltan2
365 #endif
OrderingSolution< lno_t, gno_t > * getSolution()
Get the solution to the problem.
#define HELLO
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
ModelType
An identifier for the general type of model.
virtual ~OrderingProblem()
Destructor.
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
Defines the OrderingSolution class.
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
OrderingProblem sets up ordering problems for the user.
algorithm requires no self edges
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
OrderingProblem(Adapter *A, ParameterList *p)
Constructor that uses a default communicator.
Problem base class from which other classes (PartitioningProblem, ColoringProblem, OrderingProblem, MatchingProblem, etc.) derive.
void solve(bool updateInputData=true)
Direct the problem to create a solution.
Defines the Problem base class.
Adapter::base_adapter_t base_adapter_t
virtual int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
int order(const RCP< OrderingSolution< typename Adapter::lno_t, typename Adapter::gno_t > > &solution)
Ordering method.
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
Defines the GraphModel interface.
The class containing ordering solutions.
static void getValidParameters(ParameterList &pl)
Set up validators specific to this Problem.
model represents graph within only one rank
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
#define __func__zoltan2__
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution_)
Ordering method.