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;
98  typedef typename Adapter::base_adapter_t base_adapter_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 
129  //
130  // \param updateInputData If true this indicates that either
131  // this is the first attempt at solution, or that we
132  // are computing a new solution and the input data has
133  // changed since the previous solution was computed.
134  // If false, this indicates that we are computing a
135  // new solution using the same input data was used for
136  // the previous solution, even though the parameters
137  // may have been changed.
138  //
139  // For the sake of performance, we ask the caller to set \c updateInputData
140  // to false if he/she is computing a new solution using the same input data,
141  // but different problem parameters, than that which was used to compute
142  // the most recent solution.
143 
144  void solve(bool updateInputData=true);
145 
147  //
148  // \return a reference to the solution to the most recent solve().
149 
151  // std::cout << "havePerm= " << solution_->havePerm() << " haveInverse= " << solution_->haveInverse() << std::endl;
152  // Compute Perm or InvPerm, if one is missing.
153  if (!(solution_->havePerm()))
154  solution_->computePerm();
155  if (!(solution_->haveInverse()))
156  solution_->computeInverse();
157  return solution_.getRawPtr();
158  };
159 
160 private:
161  void createOrderingProblem();
162 
163  RCP<OrderingSolution<lno_t, gno_t> > solution_;
164 
165  RCP<Comm<int> > problemComm_;
166  RCP<const Comm<int> > problemCommConst_;
167 
168 };
169 
171 template <typename Adapter>
173 {
174  HELLO;
175 
176  size_t nVtx = this->baseModel_->getLocalNumObjects();
177 
178  // TODO: Assuming one MPI process now. nVtx = ngids = nlids
179  try
180  {
181  this->solution_ = rcp(new OrderingSolution<lno_t, gno_t>(nVtx));
182  }
184 
185  // Reset status for perm and InvPerm.
186  this->solution_->setHavePerm(false);
187  this->solution_->setHaveInverse(false);
188 
189  // Determine which algorithm to use based on defaults and parameters.
190  // TODO: Use rcm if graph model is defined, otherwise use natural.
191  // Need some exception handling here, too.
192 
193  std::string method = this->params_->template get<std::string>("order_method", "rcm");
194 
195  // TODO: Ignore case
196  try
197  {
198  if (method.compare("rcm") == 0)
199  {
201  this->params_, problemComm_);
202  alg.order(this->solution_);
203  }
204  else if (method.compare("natural") == 0)
205  {
207  this->params_, problemComm_);
208  alg.order(this->solution_);
209  }
210  else if (method.compare("random") == 0)
211  {
213  this->params_, problemComm_);
214  alg.order(this->solution_);
215  }
216  else if (method.compare("sorted_degree") == 0)
217  {
219  this->params_, problemComm_);
220  alg.order(this->solution_);
221  }
222  else if (method.compare("minimum_degree") == 0)
223  {
224  std::string pkg = this->params_->template get<std::string>("order_package", "amd");
225  if (pkg.compare("amd") == 0)
226  {
228  this->params_, problemComm_);
229  alg.order(this->solution_);
230  }
231  }
232 
233 #ifdef INCLUDE_ZOLTAN2_EXPERIMENTAL_WOLF
234  else if (method == std::string("nd"))
235  {
236  AlgND<base_adapter_t> alg(this->envConst_,problemComm_,this->graphModel_,
237  this->coordinateModel_,this->baseInputAdapter_);
238  alg.order(this->solution_);
239  }
240 #endif
241 
242  }
244 }
245 
247 //template <typename Adapter>
248 //void OrderingProblem<Adapter>::redistribute()
249 //{
250 // HELLO;
251 //}
252 
255 // Method with common functionality for creating a OrderingProblem.
256 // Individual constructors do appropriate conversions of input, etc.
257 // This method does everything that all constructors must do.
258 
259 template <typename Adapter>
261 {
262  HELLO;
263  using Teuchos::ParameterList;
264 
265 // std::cout << __func__zoltan2__ << " input adapter type "
266 // << this->inputAdapter_->inputAdapterType() << " "
267 // << this->inputAdapter_->inputAdapterName() << std::endl;
268 
269 #ifdef HAVE_ZOLTAN2_OVIS
270  ovis_enabled(this->comm_->getRank());
271 #endif
272 
273  // Create a copy of the user's communicator.
274 
275  problemComm_ = this->comm_->duplicate();
276  problemCommConst_ = rcp_const_cast<const Comm<int> > (problemComm_);
277 
278  // Determine which parameters are relevant here.
279  // For now, assume parameters similar to Zoltan:
280  // MODEL = graph, hypergraph, geometric, ids
281  // ALGORITHM = rcm, random, amd
282 
283  ModelType modelType = IdentifierModelType; //default, change later
284  std::string method = this->params_->template get<std::string>("order_method", "rcm");
285 
286  if ((method == std::string("rcm")) ||
287  (method == std::string("sorted_degree")) ||
288  (method == std::string("minimum_degree"))) {
289  modelType = GraphModelType;
290  }
291 
292  // Select Model based on parameters and InputAdapter type
293 
294  std::bitset<NUM_MODEL_FLAGS> graphFlags;
295  std::bitset<NUM_MODEL_FLAGS> idFlags;
296 
297 
298  //MMW: need to change this to allow multiple models
299  // as I did with partitioning, use modelAvail_
300 
301  switch (modelType) {
302 
303  case GraphModelType:
304  graphFlags.set(REMOVE_SELF_EDGES);
305  graphFlags.set(BUILD_LOCAL_GRAPH);
306  this->graphModel_ = rcp(new GraphModel<base_adapter_t>(
307  this->baseInputAdapter_, this->envConst_, problemCommConst_, graphFlags));
308 
309  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
310  this->graphModel_);
311 
312  break;
313 
314 
315 
316  case IdentifierModelType:
318  this->baseInputAdapter_, this->envConst_, problemCommConst_, idFlags));
319 
320  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
321  this->identifierModel_);
322 
323  break;
324 
325  case HypergraphModelType:
326  case CoordinateModelType:
327  std::cout << __func__zoltan2__
328  << " Model type " << modelType << " not yet supported."
329  << std::endl;
330  break;
331 
332  default:
333  std::cout << __func__zoltan2__ << " Invalid model" << modelType
334  << std::endl;
335  break;
336  }
337 }
338 } //namespace Zoltan2
339 #endif
RCP< GraphModel< base_adapter_t > > graphModel_
OrderingSolution< lno_t, gno_t > * getSolution()
Get the solution to the problem.
#define HELLO
RCP< const base_adapter_t > baseInputAdapter_
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.
RCP< const Comm< int > > comm_
RCP< IdentifierModel< base_adapter_t > > identifierModel_
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
RCP< CoordinateModel< base_adapter_t > > coordinateModel_
int order(const RCP< OrderingSolution< typename Adapter::lno_t, typename Adapter::gno_t > > &solution)
Ordering method.
GraphModel defines the interface required for graph models.
The base class for all model classes.
RCP< ParameterList > params_
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
IdentifierModel defines the interface for all identifier models.
Defines the GraphModel interface.
The class containing ordering solutions.
RCP< const Model< base_adapter_t > > baseModel_
model represents graph within only one rank
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution)
Ordering method.
RCP< const Environment > envConst_
#define __func__zoltan2__
int order(const RCP< OrderingSolution< lno_t, gno_t > > &solution_)
Ordering method.