Zoltan2
Zoltan2_PartitioningProblem.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_PARTITIONINGPROBLEM_HPP_
51 #define _ZOLTAN2_PARTITIONINGPROBLEM_HPP_
52 
53 #include <Zoltan2_Problem.hpp>
57 #include <Zoltan2_GraphModel.hpp>
61 #include <Zoltan2_TaskMapping.hpp>
62 
63 #ifndef _WIN32
64 #include <unistd.h>
65 #else
66 #include <process.h>
67 #define NOMINMAX
68 #include <windows.h>
69 #endif
70 
71 #ifdef HAVE_ZOLTAN2_OVIS
72 #include <ovis.h>
73 #endif
74 
75 namespace Zoltan2{
76 
100 template<typename Adapter>
101 class PartitioningProblem : public Problem<Adapter>
102 {
103 public:
104 
105  typedef typename Adapter::scalar_t scalar_t;
106  typedef typename Adapter::gno_t gno_t;
107  typedef typename Adapter::lno_t lno_t;
108  typedef typename Adapter::part_t part_t;
109  typedef typename Adapter::user_t user_t;
110  typedef typename Adapter::base_adapter_t base_adapter_t;
111 
112 #ifdef HAVE_ZOLTAN2_MPI
113  typedef Teuchos::OpaqueWrapper<MPI_Comm> mpiWrapper_t;
116  PartitioningProblem(Adapter *A, ParameterList *p, MPI_Comm comm):
117  Problem<Adapter>(A,p,comm), solution_(),
118  problemComm_(), problemCommConst_(),
119  inputType_(InvalidAdapterType),
120  graphFlags_(), idFlags_(), coordFlags_(), algName_(),
121  numberOfWeights_(), partIds_(), partSizes_(),
122  numberOfCriteria_(), levelNumberParts_(), hierarchical_(false),
123  metricsRequested_(false), metrics_(), graphMetrics_()
124  {
125  for(int i=0;i<MAX_NUM_MODEL_TYPES;i++) modelAvail_[i]=false;
126  initializeProblem();
127  }
128 #endif
129 
131  PartitioningProblem(Adapter *A, ParameterList *p):
132  Problem<Adapter>(A,p), solution_(),
133  problemComm_(), problemCommConst_(),
134  inputType_(InvalidAdapterType),
135  graphFlags_(), idFlags_(), coordFlags_(), algName_(),
136  numberOfWeights_(),
137  partIds_(), partSizes_(), numberOfCriteria_(),
138  levelNumberParts_(), hierarchical_(false),
139  metricsRequested_(false), metrics_(), graphMetrics_()
140  {
141  for(int i=0;i<MAX_NUM_MODEL_TYPES;i++) modelAvail_[i]=false;
142  initializeProblem();
143  }
144 
146  PartitioningProblem(Adapter *A, ParameterList *p,
147  RCP<const Teuchos::Comm<int> > &comm):
148  Problem<Adapter>(A,p,comm), solution_(),
149  problemComm_(), problemCommConst_(),
150  inputType_(InvalidAdapterType),
151  graphFlags_(), idFlags_(), coordFlags_(), algName_(),
152  numberOfWeights_(),
153  partIds_(), partSizes_(), numberOfCriteria_(),
154  levelNumberParts_(), hierarchical_(false),
155  metricsRequested_(false), metrics_(), graphMetrics_()
156  {
157  for(int i=0;i<MAX_NUM_MODEL_TYPES;i++) modelAvail_[i]=false;
158  initializeProblem();
159  }
160 
164 
166  //
167  // \param updateInputData If true this indicates that either
168  // this is the first attempt at solution, or that we
169  // are computing a new solution and the input data has
170  // changed since the previous solution was computed.
171  // By input data we mean coordinates, topology, or weights.
172  // If false, this indicates that we are computing a
173  // new solution using the same input data was used for
174  // the previous solution, even though the parameters
175  // may have been changed.
176  //
177  // For the sake of performance, we ask the caller to set \c updateInputData
178  // to false if he/she is computing a new solution using the same input data,
179  // but different problem parameters, than that which was used to compute
180  // the most recent solution.
181 
182  void solve(bool updateInputData=true );
183 
185  //
186  // \return a reference to the solution to the most recent solve().
187 
189  return *(solution_.getRawPtr());
190  };
191 
200  const scalar_t getWeightImbalance(int idx=0) const {
201  scalar_t imb = 0;
202  if (!metrics_.is_null())
203  metrics_->getWeightImbalance(imb, idx);
204 
205  return imb;
206  }
207 
212  ArrayRCP<const MetricValues<scalar_t> > getMetrics() const {
213  if (metrics_.is_null()){
214  ArrayRCP<const MetricValues<scalar_t> > emptyMetrics;
215  return emptyMetrics;
216  }
217  else
218  return metrics_->getMetrics();
219  }
220 
225  ArrayRCP<const GraphMetricValues<scalar_t> > getGraphMetrics() const {
226  if (graphMetrics_.is_null()){
227  ArrayRCP<const GraphMetricValues<scalar_t> > emptyMetrics;
228  return emptyMetrics;
229  }
230  else
231  return graphMetrics_->getGraphMetrics();
232  }
233 
239  void printMetrics(std::ostream &os) const {
240  if (metrics_.is_null())
241  os << "No metrics available." << std::endl;
242  else
243  metrics_->printMetrics(os);
244  };
245 
251  void printGraphMetrics(std::ostream &os) const {
252  if (graphMetrics_.is_null())
253  os << "No metrics available." << std::endl;
254  else
255  graphMetrics_->printGraphMetrics(os);
256  };
257 
296  void setPartSizes(int len, part_t *partIds, scalar_t *partSizes,
297  bool makeCopy=true)
298  {
299  setPartSizesForCriteria(0, len, partIds, partSizes, makeCopy);
300  }
301 
336  void setPartSizesForCriteria(int criteria, int len, part_t *partIds,
337  scalar_t *partSizes, bool makeCopy=true) ;
338 /*
339  void setMachine(MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> *machine);
340 */
343  void resetParameters(ParameterList *params)
344  {
345  Problem<Adapter>::resetParameters(params); // creates new environment
346  }
347 
352  const RCP<const Environment> & getEnvironment() const
353  {
354  return this->envConst_;
355  }
356 
357 private:
358  void initializeProblem();
359 
360  void createPartitioningProblem(bool newData);
361 
362  RCP<PartitioningSolution<Adapter> > solution_;
363 
364  RCP<MachineRepresentation <typename Adapter::base_adapter_t::scalar_t> > machine_;
365 
366  RCP<Comm<int> > problemComm_;
367  RCP<const Comm<int> > problemCommConst_;
368 
369  BaseAdapterType inputType_;
370 
371  //ModelType modelType_;
372  bool modelAvail_[MAX_NUM_MODEL_TYPES];
373 
374  modelFlag_t graphFlags_;
375  modelFlag_t idFlags_;
376  modelFlag_t coordFlags_;
377  std::string algName_;
378 
379  int numberOfWeights_;
380 
381  // Suppose Array<part_t> partIds = partIds_[w]. If partIds.size() > 0
382  // then the user supplied part sizes for weight index "w", and the sizes
383  // corresponding to the Ids in partIds are partSizes[w].
384  //
385  // If numberOfWeights_ >= 0, then there is an Id and Sizes array for
386  // for each weight. Otherwise the user did not supply object weights,
387  // but they can still specify part sizes.
388  // So numberOfCriteria_ is numberOfWeights_ or one, whichever is greater.
389 
390  ArrayRCP<ArrayRCP<part_t> > partIds_;
391  ArrayRCP<ArrayRCP<scalar_t> > partSizes_;
392  int numberOfCriteria_;
393 
394  // Number of parts to be computed at each level in hierarchical partitioning.
395 
396  ArrayRCP<int> levelNumberParts_;
397  bool hierarchical_;
398 
399  // Did the user request metrics?
400 
401  bool metricsRequested_;
402  RCP<const EvaluatePartition<Adapter> > metrics_;
403  RCP<const EvaluatePartition<Adapter> > graphMetrics_;
404 };
406 
407 /*
408 template <typename Adapter>
409 void PartitioningProblem<Adapter>::setMachine(MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> *machine){
410  this->machine_ = RCP<MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> > (machine, false);
411 }
412 */
413 
414 
415 template <typename Adapter>
417 {
418  HELLO;
419 
420  this->env_->debug(DETAILED_STATUS, "PartitioningProblem::initializeProblem");
421 
422  if (getenv("DEBUGME")){
423 #ifndef _WIN32
424  std::cout << getpid() << std::endl;
425  sleep(15);
426 #else
427  std::cout << _getpid() << std::endl;
428  Sleep(15000);
429 #endif
430  }
431 
432 #ifdef HAVE_ZOLTAN2_OVIS
433  ovis_enabled(this->comm_->getRank());
434 #endif
435 
436  // Create a copy of the user's communicator.
437 
438  problemComm_ = this->comm_->duplicate();
439  problemCommConst_ = rcp_const_cast<const Comm<int> > (problemComm_);
440 
441  machine_ = RCP <Zoltan2::MachineRepresentation<typename Adapter::scalar_t> >(new Zoltan2::MachineRepresentation<typename Adapter::scalar_t>(problemComm_));
442 
443  // Number of criteria is number of user supplied weights if non-zero.
444  // Otherwise it is 1 and uniform weight is implied.
445 
446  numberOfWeights_ = this->inputAdapter_->getNumWeightsPerID();
447 
448  numberOfCriteria_ = (numberOfWeights_ > 1) ? numberOfWeights_ : 1;
449 
450  inputType_ = this->inputAdapter_->adapterType();
451 
452  // The Caller can specify part sizes in setPartSizes(). If he/she
453  // does not, the part size arrays are empty.
454 
455  ArrayRCP<part_t> *noIds = new ArrayRCP<part_t> [numberOfCriteria_];
456  ArrayRCP<scalar_t> *noSizes = new ArrayRCP<scalar_t> [numberOfCriteria_];
457 
458  partIds_ = arcp(noIds, 0, numberOfCriteria_, true);
459  partSizes_ = arcp(noSizes, 0, numberOfCriteria_, true);
460 
461  if (this->env_->getDebugLevel() >= DETAILED_STATUS){
462  std::ostringstream msg;
463  msg << problemComm_->getSize() << " procs,"
464  << numberOfWeights_ << " user-defined weights\n";
465  this->env_->debug(DETAILED_STATUS, msg.str());
466  }
467 
468  this->env_->memory("After initializeProblem");
469 }
470 
471 template <typename Adapter>
473  int criteria, int len, part_t *partIds, scalar_t *partSizes, bool makeCopy)
474 {
475  this->env_->localInputAssertion(__FILE__, __LINE__, "invalid length",
476  len>= 0, BASIC_ASSERTION);
477 
478  this->env_->localInputAssertion(__FILE__, __LINE__, "invalid criteria",
479  criteria >= 0 && criteria < numberOfCriteria_, BASIC_ASSERTION);
480 
481  if (len == 0){
482  partIds_[criteria] = ArrayRCP<part_t>();
483  partSizes_[criteria] = ArrayRCP<scalar_t>();
484  return;
485  }
486 
487  this->env_->localInputAssertion(__FILE__, __LINE__, "invalid arrays",
488  partIds && partSizes, BASIC_ASSERTION);
489 
490  // The global validity of the partIds and partSizes arrays is performed
491  // by the PartitioningSolution, which computes global part distribution and
492  // part sizes.
493 
494  part_t *z2_partIds = NULL;
495  scalar_t *z2_partSizes = NULL;
496  bool own_memory = false;
497 
498  if (makeCopy){
499  z2_partIds = new part_t [len];
500  z2_partSizes = new scalar_t [len];
501  this->env_->localMemoryAssertion(__FILE__, __LINE__, len, z2_partSizes);
502  memcpy(z2_partIds, partIds, len * sizeof(part_t));
503  memcpy(z2_partSizes, partSizes, len * sizeof(scalar_t));
504  own_memory=true;
505  }
506  else{
507  z2_partIds = partIds;
508  z2_partSizes = partSizes;
509  }
510 
511  partIds_[criteria] = arcp(z2_partIds, 0, len, own_memory);
512  partSizes_[criteria] = arcp(z2_partSizes, 0, len, own_memory);
513 }
514 
515 template <typename Adapter>
516 void PartitioningProblem<Adapter>::solve(bool updateInputData)
517 {
518  this->env_->debug(DETAILED_STATUS, "Entering solve");
519 
520  // Create the computational model.
521 
522  this->env_->timerStart(MACRO_TIMERS, "create problem");
523 
524  createPartitioningProblem(updateInputData);
525 
526  this->env_->timerStop(MACRO_TIMERS, "create problem");
527 
528  // TODO: If hierarchical_
529 
530  // Create the solution. The algorithm will query the Solution
531  // for part and weight information. The algorithm will
532  // update the solution with part assignments and quality metrics.
533 
534  // Create the algorithm
535  try {
536  if (algName_ == std::string("multijagged")) {
537  this->algorithm_ = rcp(new Zoltan2_AlgMJ<Adapter>(this->envConst_,
538  problemComm_,
539  this->coordinateModel_));
540  }
541  else if (algName_ == std::string("zoltan")) {
542  this->algorithm_ = rcp(new AlgZoltan<Adapter>(this->envConst_,
543  problemComm_,
544  this->baseInputAdapter_));
545  }
546  else if (algName_ == std::string("parma")) {
547  this->algorithm_ = rcp(new AlgParMA<Adapter>(this->envConst_,
548  problemComm_,
549  this->baseInputAdapter_));
550  }
551  else if (algName_ == std::string("scotch")) {
552  this->algorithm_ = rcp(new AlgPTScotch<Adapter>(this->envConst_,
553  problemComm_,
554  this->graphModel_));
555  }
556  else if (algName_ == std::string("parmetis")) {
557  this->algorithm_ = rcp(new AlgParMETIS<Adapter>(this->envConst_,
558  problemComm_,
559  this->graphModel_));
560  }
561  else if (algName_ == std::string("pulp")) {
562  this->algorithm_ = rcp(new AlgPuLP<Adapter>(this->envConst_,
563  problemComm_,
564  this->baseInputAdapter_));
565  }
566  else if (algName_ == std::string("block")) {
567  this->algorithm_ = rcp(new AlgBlock<Adapter>(this->envConst_,
568  problemComm_, this->identifierModel_));
569  }
570  else if (algName_ == std::string("forTestingOnly")) {
571  this->algorithm_ = rcp(new AlgForTestingOnly<Adapter>(this->envConst_,
572  problemComm_,
573  this->baseInputAdapter_));
574  }
575  // else if (algName_ == std::string("rcb")) {
576  // this->algorithm_ = rcp(new AlgRCB<Adapter>(this->envConst_,problemComm_,
577  // this->coordinateModel_));
578  // }
579  else {
580  throw std::logic_error("partitioning algorithm not supported");
581  }
582  }
584 
585  // Create the solution
586  this->env_->timerStart(MACRO_TIMERS, "create solution");
587  PartitioningSolution<Adapter> *soln = NULL;
588 
589  try{
590  soln = new PartitioningSolution<Adapter>(
591  this->envConst_, problemCommConst_, numberOfWeights_,
592  partIds_.view(0, numberOfCriteria_),
593  partSizes_.view(0, numberOfCriteria_), this->algorithm_);
594  }
596 
597  solution_ = rcp(soln);
598 
599  this->env_->timerStop(MACRO_TIMERS, "create solution");
600  this->env_->memory("After creating Solution");
601 
602  // Call the algorithm
603 
604  try {
605  this->algorithm_->partition(solution_);
606  }
608 
609  //if mapping is requested
610  const Teuchos::ParameterEntry *pe = this->envConst_->getParameters().getEntryPtr("mapping_type");
611  int mapping_type = -1;
612  if (pe){
613  mapping_type = pe->getValue(&mapping_type);
614  }
615  //if mapping is 0 -- coordinate mapping
616 
617  if (mapping_type == 0){
618 
619  //part_t *task_communication_xadj = NULL, *task_communication_adj = NULL;
620 
623  problemComm_.getRawPtr(),
624  machine_.getRawPtr(),
625  this->coordinateModel_.getRawPtr(),
626  solution_.getRawPtr(),
627  this->envConst_.getRawPtr()
628  //,task_communication_xadj,
629  //task_communication_adj
630  );
631  //for now just delete the object.
632  delete ctm;
633  }
634  else if (mapping_type == 1){
635  //if mapping is 1 -- graph mapping
636  }
637 
638  if (metricsRequested_){
639  typedef PartitioningSolution<Adapter> ps_t;
640  typedef EvaluatePartition<Adapter> psq_t;
641  typedef StridedData<lno_t, scalar_t> input_t;
642 
643  psq_t *quality = NULL;
644  RCP<const ps_t> solutionConst = rcp_const_cast<const ps_t>(solution_);
645 
646  if (inputType_ == GraphAdapterType ||
647  inputType_ == MatrixAdapterType ||
648  inputType_ == MeshAdapterType){
649 
650  try{
651  quality = new psq_t(this->envConst_, problemCommConst_,
652  this->baseInputAdapter_, solutionConst, false);
653  }
654  Z2_FORWARD_EXCEPTIONS
655 
656  psq_t *graphQuality = NULL;
657 
658  try{
659  graphQuality = new psq_t(this->envConst_, problemCommConst_,
660  this->baseInputAdapter_, solutionConst,
661  this->graphModel_);
662  }
663  Z2_FORWARD_EXCEPTIONS
664 
665  graphMetrics_ = rcp(graphQuality);
666  } else {
667 
668  try{
669  quality = new psq_t(this->envConst_, problemCommConst_,
670  this->baseInputAdapter_, solutionConst, false);
671  }
672  Z2_FORWARD_EXCEPTIONS
673  }
674 
675  metrics_ = rcp(quality);
676  }
677 
678  this->env_->debug(DETAILED_STATUS, "Exiting solve");
679 }
680 
681 template <typename Adapter>
683 {
684  this->env_->debug(DETAILED_STATUS,
685  "PartitioningProblem::createPartitioningProblem");
686 
687  using Teuchos::ParameterList;
688 
689  // A Problem object may be reused. The input data may have changed and
690  // new parameters or part sizes may have been set.
691  //
692  // Save these values in order to determine if we need to create a new model.
693 
694  //ModelType previousModel = modelType_;
695  bool prevModelAvail[MAX_NUM_MODEL_TYPES];
696  for(int i=0;i<MAX_NUM_MODEL_TYPES;i++)
697  {
698  prevModelAvail[i] = modelAvail_[i];
699  }
700 
701 
702  modelFlag_t previousGraphModelFlags = graphFlags_;
703  modelFlag_t previousIdentifierModelFlags = idFlags_;
704  modelFlag_t previousCoordinateModelFlags = coordFlags_;
705 
706  //modelType_ = InvalidModel;
707  for(int i=0;i<MAX_NUM_MODEL_TYPES;i++)
708  {
709  modelAvail_[i] = false;
710  }
711 
712  graphFlags_.reset();
713  idFlags_.reset();
714  coordFlags_.reset();
715 
717  // It's possible at this point that the Problem may want to
718  // add problem parameters to the parameter list in the Environment.
719  //
720  // Since the parameters in the Environment have already been
721  // validated in its constructor, a new Environment must be created:
723  // Teuchos::RCP<const Teuchos::Comm<int> > oldComm = this->env_->comm_;
724  // const ParameterList &oldParams = this->env_->getUnvalidatedParameters();
725  //
726  // ParameterList newParams = oldParams;
727  // newParams.set("new_parameter", "new_value");
728  //
729  // ParameterList &newPartParams = newParams.sublist("partitioning");
730  // newPartParams.set("new_partitioning_parameter", "its_value");
731  //
732  // this->env_ = rcp(new Environment(newParams, oldComm));
734 
735  this->env_->debug(DETAILED_STATUS, " parameters");
736  Environment &env = *(this->env_);
737  ParameterList &pl = env.getParametersNonConst();
738 
739  std::string defString("default");
740 
741  // Did the user ask for computation of quality metrics?
742 
743  int yesNo=0;
744  const Teuchos::ParameterEntry *pe = pl.getEntryPtr("compute_metrics");
745  if (pe){
746  yesNo = pe->getValue<int>(&yesNo);
747  metricsRequested_ = true;
748  }
749 
750  // Did the user specify a computational model?
751 
752  std::string model(defString);
753  pe = pl.getEntryPtr("model");
754  if (pe)
755  model = pe->getValue<std::string>(&model);
756 
757  // Did the user specify an algorithm?
758 
759  std::string algorithm(defString);
760  pe = pl.getEntryPtr("algorithm");
761  if (pe)
762  algorithm = pe->getValue<std::string>(&algorithm);
763 
764  // Possible algorithm requirements that must be conveyed to the model:
765 
766  bool needConsecutiveGlobalIds = false;
767  bool removeSelfEdges= false;
768 
770  // Determine algorithm, model, and algorithm requirements. This
771  // is a first pass. Feel free to change this and add to it.
772 
773  if (algorithm != defString)
774  {
775 
776  // Figure out the model required by the algorithm
777  if (algorithm == std::string("block") ||
778  algorithm == std::string("random") ||
779  algorithm == std::string("cyclic") ){
780 
781  //modelType_ = IdentifierModelType;
782  modelAvail_[IdentifierModelType] = true;
783 
784  algName_ = algorithm;
785  }
786  else if (algorithm == std::string("zoltan") ||
787  algorithm == std::string("parma") ||
788  algorithm == std::string("forTestingOnly"))
789  {
790  algName_ = algorithm;
791  }
792  else if (algorithm == std::string("rcb") ||
793  algorithm == std::string("rib") ||
794  algorithm == std::string("hsfc"))
795  {
796  // rcb, rib, hsfc provided through Zoltan
797  Teuchos::ParameterList &zparams = pl.sublist("zoltan_parameters",false);
798  zparams.set("LB_METHOD", algorithm);
799  if (numberOfWeights_ > 0) {
800  char strval[10];
801  sprintf(strval, "%d", numberOfWeights_);
802  zparams.set("OBJ_WEIGHT_DIM", strval);
803  }
804  algName_ = std::string("zoltan");
805  }
806  else if (algorithm == std::string("multijagged"))
807  {
808  //modelType_ = CoordinateModelType;
809  modelAvail_[CoordinateModelType]=true;
810 
811  algName_ = algorithm;
812  }
813  else if (algorithm == std::string("metis") ||
814  algorithm == std::string("parmetis") ||
815  algorithm == std::string("scotch") ||
816  algorithm == std::string("ptscotch"))
817  {
818 
819  //modelType_ = GraphModelType;
820  modelAvail_[GraphModelType]=true;
821 
822  algName_ = algorithm;
823  removeSelfEdges = true;
824  needConsecutiveGlobalIds = true;
825  }
826  else if (algorithm == std::string("pulp"))
827  {
828  algName_ = algorithm;
829  }
830  else if (algorithm == std::string("patoh") ||
831  algorithm == std::string("phg"))
832  {
833  // if ((modelType_ != GraphModelType) &&
834  // (modelType_ != HypergraphModelType) )
835  if ((modelAvail_[GraphModelType]==false) &&
836  (modelAvail_[HypergraphModelType]==false) )
837  {
838  //modelType_ = HypergraphModelType;
839  modelAvail_[HypergraphModelType]=true;
840  }
841  algName_ = algorithm;
842  }
843 #ifdef INCLUDE_ZOLTAN2_EXPERIMENTAL_WOLF
844  else if (algorithm == std::string("nd"))
845  {
846  modelAvail_[GraphModelType]=true;
847  modelAvail_[CoordinateModelType]=true;
848  algName_ = algorithm;
849  }
850 #endif
851  else
852  {
853  // Parameter list should ensure this does not happen.
854  throw std::logic_error("parameter list algorithm is invalid");
855  }
856  }
857  else if (model != defString)
858  {
859  // Figure out the algorithm suggested by the model.
860  if (model == std::string("hypergraph"))
861  {
862  //modelType_ = HypergraphModelType;
863  modelAvail_[HypergraphModelType]=true;
864 
865  if (problemComm_->getSize() > 1)
866  algName_ = std::string("phg");
867  else
868  algName_ = std::string("patoh");
869  }
870  else if (model == std::string("graph"))
871  {
872  //modelType_ = GraphModelType;
873  modelAvail_[GraphModelType]=true;
874 
875 #ifdef HAVE_ZOLTAN2_SCOTCH
876  if (problemComm_->getSize() > 1)
877  algName_ = std::string("ptscotch");
878  else
879  algName_ = std::string("scotch");
880  removeSelfEdges = true;
881  needConsecutiveGlobalIds = true;
882 #else
883 #ifdef HAVE_ZOLTAN2_PARMETIS
884  if (problemComm_->getSize() > 1)
885  algName_ = std::string("parmetis");
886  else
887  algName_ = std::string("metis");
888  removeSelfEdges = true;
889  needConsecutiveGlobalIds = true;
890 #else
891 #ifdef HAVE_ZOLTAN2_PULP
892  // TODO: XtraPuLP
893  //if (problemComm_->getSize() > 1)
894  // algName_ = std::string("xtrapulp");
895  //else
896  algName_ = std::string("pulp");
897 #else
898  if (problemComm_->getSize() > 1)
899  algName_ = std::string("phg");
900  else
901  algName_ = std::string("patoh");
902 #endif
903 #endif
904 #endif
905  }
906  else if (model == std::string("geometry"))
907  {
908  //modelType_ = CoordinateModelType;
909  modelAvail_[CoordinateModelType]=true;
910 
911  algName_ = std::string("multijagged");
912  }
913  else if (model == std::string("ids"))
914  {
915  //modelType_ = IdentifierModelType;
916  modelAvail_[IdentifierModelType]=true;
917 
918  algName_ = std::string("block");
919  }
920  else
921  {
922  // Parameter list should ensure this does not happen.
923  env.localBugAssertion(__FILE__, __LINE__,
924  "parameter list model type is invalid", 1, BASIC_ASSERTION);
925  }
926  }
927  else
928  {
929  // Determine an algorithm and model suggested by the input type.
930  // TODO: this is a good time to use the time vs. quality parameter
931  // in choosing an algorithm, and setting some parameters
932 
933  if (inputType_ == MatrixAdapterType)
934  {
935  //modelType_ = HypergraphModelType;
936  modelAvail_[HypergraphModelType]=true;
937 
938  if (problemComm_->getSize() > 1)
939  algName_ = std::string("phg");
940  else
941  algName_ = std::string("patoh");
942  }
943  else if (inputType_ == GraphAdapterType ||
944  inputType_ == MeshAdapterType)
945  {
946  //modelType_ = GraphModelType;
947  modelAvail_[GraphModelType]=true;
948 
949  if (problemComm_->getSize() > 1)
950  algName_ = std::string("phg");
951  else
952  algName_ = std::string("patoh");
953  }
954  else if (inputType_ == VectorAdapterType)
955  {
956  //modelType_ = CoordinateModelType;
957  modelAvail_[CoordinateModelType]=true;
958 
959  algName_ = std::string("multijagged");
960  }
961  else if (inputType_ == IdentifierAdapterType)
962  {
963  //modelType_ = IdentifierModelType;
964  modelAvail_[IdentifierModelType]=true;
965 
966  algName_ = std::string("block");
967  }
968  else{
969  // This should never happen
970  throw std::logic_error("input type is invalid");
971  }
972  }
973 
974  // Hierarchical partitioning?
975 
976  Array<int> valueList;
977  pe = pl.getEntryPtr("topology");
978 
979  if (pe){
980  valueList = pe->getValue<Array<int> >(&valueList);
981 
982  if (!Zoltan2::noValuesAreInRangeList<int>(valueList)){
983  int *n = new int [valueList.size() + 1];
984  levelNumberParts_ = arcp(n, 0, valueList.size() + 1, true);
985  int procsPerNode = 1;
986  for (int i=0; i < valueList.size(); i++){
987  levelNumberParts_[i+1] = valueList[i];
988  procsPerNode *= valueList[i];
989  }
990  // Number of parts in the first level
991  levelNumberParts_[0] = env.numProcs_ / procsPerNode;
992 
993  if (env.numProcs_ % procsPerNode > 0)
994  levelNumberParts_[0]++;
995  }
996  }
997  else{
998  levelNumberParts_.clear();
999  }
1000 
1001  hierarchical_ = levelNumberParts_.size() > 0;
1002 
1003  // Object to be partitioned? (rows, columns, etc)
1004 
1005  std::string objectOfInterest(defString);
1006  pe = pl.getEntryPtr("objects_to_partition");
1007  if (pe)
1008  objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
1009 
1011  // Set model creation flags, if any.
1012 
1013  this->env_->debug(DETAILED_STATUS, " models");
1014  // if (modelType_ == GraphModelType)
1015  if (modelAvail_[GraphModelType]==true)
1016  {
1017 
1018  // Any parameters in the graph sublist?
1019 
1020  std::string symParameter(defString);
1021  pe = pl.getEntryPtr("symmetrize_graph");
1022  if (pe){
1023  symParameter = pe->getValue<std::string>(&symParameter);
1024  if (symParameter == std::string("transpose"))
1025  graphFlags_.set(SYMMETRIZE_INPUT_TRANSPOSE);
1026  else if (symParameter == std::string("bipartite"))
1027  graphFlags_.set(SYMMETRIZE_INPUT_BIPARTITE);
1028  }
1029 
1030  int sgParameter = 0;
1031  pe = pl.getEntryPtr("subset_graph");
1032  if (pe)
1033  sgParameter = pe->getValue<int>(&sgParameter);
1034 
1035  if (sgParameter == 1)
1036  graphFlags_.set(BUILD_SUBSET_GRAPH);
1037 
1038  // Any special behaviors required by the algorithm?
1039 
1040  if (removeSelfEdges)
1041  graphFlags_.set(REMOVE_SELF_EDGES);
1042 
1043  if (needConsecutiveGlobalIds)
1044  graphFlags_.set(GENERATE_CONSECUTIVE_IDS);
1045 
1046  // How does user input map to vertices and edges?
1047 
1048  if (inputType_ == MatrixAdapterType){
1049  if (objectOfInterest == defString ||
1050  objectOfInterest == std::string("matrix_rows") )
1051  graphFlags_.set(VERTICES_ARE_MATRIX_ROWS);
1052  else if (objectOfInterest == std::string("matrix_columns"))
1053  graphFlags_.set(VERTICES_ARE_MATRIX_COLUMNS);
1054  else if (objectOfInterest == std::string("matrix_nonzeros"))
1055  graphFlags_.set(VERTICES_ARE_MATRIX_NONZEROS);
1056  }
1057 
1058  else if (inputType_ == MeshAdapterType){
1059  if (objectOfInterest == defString ||
1060  objectOfInterest == std::string("mesh_nodes") )
1061  graphFlags_.set(VERTICES_ARE_MESH_NODES);
1062  else if (objectOfInterest == std::string("mesh_elements"))
1063  graphFlags_.set(VERTICES_ARE_MESH_ELEMENTS);
1064  }
1065  }
1066  //MMW is it ok to remove else?
1067  // else if (modelType_ == IdentifierModelType)
1068  if (modelAvail_[IdentifierModelType]==true)
1069  {
1070 
1071  // Any special behaviors required by the algorithm?
1072 
1073  }
1074  // else if (modelType_ == CoordinateModelType)
1075  if (modelAvail_[CoordinateModelType]==true)
1076  {
1077 
1078  // Any special behaviors required by the algorithm?
1079 
1080  }
1081 
1082 
1083  if (newData ||
1084  (modelAvail_[GraphModelType]!=prevModelAvail[GraphModelType]) ||
1085  (modelAvail_[HypergraphModelType]!=prevModelAvail[HypergraphModelType])||
1086  (modelAvail_[CoordinateModelType]!=prevModelAvail[CoordinateModelType])||
1087  (modelAvail_[IdentifierModelType]!=prevModelAvail[IdentifierModelType])||
1088  // (modelType_ != previousModel) ||
1089  (graphFlags_ != previousGraphModelFlags) ||
1090  (coordFlags_ != previousCoordinateModelFlags) ||
1091  (idFlags_ != previousIdentifierModelFlags))
1092  {
1093  // Create the computational model.
1094  // Models are instantiated for base input adapter types (mesh,
1095  // matrix, graph, and so on). We pass a pointer to the input
1096  // adapter, cast as the base input type.
1097 
1098  //KDD Not sure why this shadow declaration is needed
1099  //KDD Comment out for now; revisit later if problems.
1100  //KDD const Teuchos::ParameterList pl = this->envConst_->getParameters();
1101  //bool exceptionThrow = true;
1102 
1103  if(modelAvail_[GraphModelType]==true)
1104  {
1105  this->env_->debug(DETAILED_STATUS, " building graph model");
1106  this->graphModel_ = rcp(new GraphModel<base_adapter_t>(
1107  this->baseInputAdapter_, this->envConst_, problemComm_,
1108  graphFlags_));
1109 
1110  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
1111  this->graphModel_);
1112  }
1113 
1114  if(modelAvail_[HypergraphModelType]==true)
1115  {
1116  std::cout << "Hypergraph model not implemented yet..." << std::endl;
1117  }
1118 
1119  if(modelAvail_[CoordinateModelType]==true)
1120  {
1121  this->env_->debug(DETAILED_STATUS, " building coordinate model");
1123  this->baseInputAdapter_, this->envConst_, problemComm_,
1124  coordFlags_));
1125 
1126  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
1127  this->coordinateModel_);
1128  }
1129 
1130  if(modelAvail_[IdentifierModelType]==true)
1131  {
1132  this->env_->debug(DETAILED_STATUS, " building identifier model");
1134  this->baseInputAdapter_, this->envConst_, problemComm_,
1135  idFlags_));
1136 
1137  this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
1138  this->identifierModel_);
1139  }
1140 
1141  this->env_->memory("After creating Model");
1142  this->env_->debug(DETAILED_STATUS, "createPartitioningProblem done");
1143  }
1144 }
1145 
1146 } // namespace Zoltan2
1147 #endif
use columns as graph vertices
RCP< GraphModel< base_adapter_t > > graphModel_
#define HELLO
ArrayRCP< const MetricValues< scalar_t > > getMetrics() const
Get the array of metrics Metrics were only computed if user requested metrics with a parameter...
const scalar_t getWeightImbalance(int idx=0) const
Returns the imbalance of the solution.
Time an algorithm (or other entity) as a whole.
RCP< const base_adapter_t > baseInputAdapter_
ignore invalid neighbors
void setPartSizes(int len, part_t *partIds, scalar_t *partSizes, bool makeCopy=true)
Set or reset relative sizes for the parts that Zoltan2 will create.
use mesh nodes as vertices
fast typical checks for valid arguments
#define Z2_FORWARD_EXCEPTIONS
Forward an exception back through call stack.
algorithm requires consecutive ids
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
PartitioningProblem(Adapter *A, ParameterList *p, RCP< const Teuchos::Comm< int > > &comm)
Constructor where Teuchos communicator is specified.
PartitioningProblem(Adapter *A, ParameterList *p)
Constructor where communicator is the Teuchos default.
model must symmetrize input
model must symmetrize input
RCP< Algorithm< Adapter > > algorithm_
RCP< const Comm< int > > comm_
void resetParameters(ParameterList *params)
Reset the list of parameters.
Defines the PartitioningSolution class.
sub-steps, each method&#39;s entry and exit
const RCP< const Environment > & getEnvironment() const
Get the current Environment. Useful for testing.
void resetParameters(ParameterList *params)
Reset the list of parameters.
RCP< IdentifierModel< base_adapter_t > > identifierModel_
void setPartSizesForCriteria(int criteria, int len, part_t *partIds, scalar_t *partSizes, bool makeCopy=true)
Set or reset the relative sizes (per weight) for the parts that Zoltan2 will create.
int numProcs_
number of processes (relative to comm_)
use matrix rows as graph vertices
This class provides geometric coordinates with optional weights to the Zoltan2 algorithm.
Teuchos::ParameterList & getParametersNonConst()
Returns a reference to a non-const copy of the parameters.
algorithm requires no self edges
Defines the IdentifierModel interface.
A PartitioningSolution is a solution to a partitioning problem.
use nonzeros as graph vertices
void printGraphMetrics(std::ostream &os) const
Print the array of metrics.
Defines the EvaluatePartition class.
BaseAdapterType
An enum to identify general types of adapters.
void printMetrics(std::ostream &os) const
Print the array of metrics.
identifier data, just a list of IDs
void localBugAssertion(const char *file, int lineNum, const char *msg, bool ok, AssertionLevel level) const
Test for valid library behavior on local process only.
Problem base class from which other classes (PartitioningProblem, ColoringProblem, OrderingProblem, MatchingProblem, etc.) derive.
The StridedData class manages lists of weights or coordinates.
RCP< const Adapter > inputAdapter_
Defines the Problem base class.
RCP< CoordinateModel< base_adapter_t > > coordinateModel_
The user parameters, debug, timing and memory profiling output objects, and error checking methods...
MachineRepresentation Class Finds the coordinate of the processor. Used to find the processor coordin...
ArrayRCP< const GraphMetricValues< scalar_t > > getGraphMetrics() const
Get the array of graphMetrics Graph metrics were only computed if user requested graph metrics with a...
Define IntegerRangeList validator.
const PartitioningSolution< Adapter > & getSolution()
Get the solution to the problem.
PartitioningProblem sets up partitioning problems for the user.
use mesh elements as vertices
GraphModel defines the interface required for graph models.
RCP< Environment > env_
The base class for all model classes.
IdentifierModel defines the interface for all identifier models.
Defines the GraphModel interface.
RCP< const Model< base_adapter_t > > baseModel_
A class that computes and returns quality metrics.
void solve(bool updateInputData=true)
Direct the problem to create a solution.
RCP< const Environment > envConst_
Multi Jagged coordinate partitioning algorithm.