Zoltan2
Zoltan2_PartitioningProblem.hpp
Go to the documentation of this file.
00001 // @HEADER
00002 //
00003 // ***********************************************************************
00004 //
00005 //   Zoltan2: A package of combinatorial algorithms for scientific computing
00006 //                  Copyright 2012 Sandia Corporation
00007 //
00008 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
00009 // the U.S. Government retains certain rights in this software.
00010 //
00011 // Redistribution and use in source and binary forms, with or without
00012 // modification, are permitted provided that the following conditions are
00013 // met:
00014 //
00015 // 1. Redistributions of source code must retain the above copyright
00016 // notice, this list of conditions and the following disclaimer.
00017 //
00018 // 2. Redistributions in binary form must reproduce the above copyright
00019 // notice, this list of conditions and the following disclaimer in the
00020 // documentation and/or other materials provided with the distribution.
00021 //
00022 // 3. Neither the name of the Corporation nor the names of the
00023 // contributors may be used to endorse or promote products derived from
00024 // this software without specific prior written permission.
00025 //
00026 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00027 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00028 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00029 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00030 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00031 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00032 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00033 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00034 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00035 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00036 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00037 //
00038 // Questions? Contact Karen Devine      (kddevin@sandia.gov)
00039 //                    Erik Boman        (egboman@sandia.gov)
00040 //                    Siva Rajamanickam (srajama@sandia.gov)
00041 //
00042 // ***********************************************************************
00043 //
00044 // @HEADER
00045 
00050 #ifndef _ZOLTAN2_PARTITIONINGPROBLEM_HPP_
00051 #define _ZOLTAN2_PARTITIONINGPROBLEM_HPP_
00052 
00053 #include <Zoltan2_Problem.hpp>
00054 #include <Zoltan2_PartitioningAlgorithms.hpp>
00055 #include <Zoltan2_PartitioningSolution.hpp>
00056 #include <Zoltan2_PartitioningSolutionQuality.hpp>
00057 #include <Zoltan2_GraphModel.hpp>
00058 #include <Zoltan2_IdentifierModel.hpp>
00059 #include <Zoltan2_IntegerRangeList.hpp>
00060 #include <Zoltan2_MachineRepresentation.hpp>
00061 #include <Zoltan2_TaskMapping.hpp>
00062 
00063 #include <unistd.h>
00064 
00065 #ifdef HAVE_ZOLTAN2_OVIS
00066 #include <ovis.h>
00067 #endif
00068 
00069 namespace Zoltan2{
00070 
00094 template<typename Adapter>
00095 class PartitioningProblem : public Problem<Adapter>
00096 {
00097 public:
00098 
00099   typedef typename Adapter::scalar_t scalar_t;
00100   typedef typename Adapter::gid_t gid_t;
00101   typedef typename Adapter::gno_t gno_t;
00102   typedef typename Adapter::lno_t lno_t;
00103   typedef typename Adapter::part_t part_t;
00104   typedef typename Adapter::user_t user_t;
00105   typedef typename Adapter::base_adapter_t base_adapter_t;
00106 
00107 #ifdef HAVE_ZOLTAN2_MPI
00108   typedef Teuchos::OpaqueWrapper<MPI_Comm> mpiWrapper_t;
00109 #endif
00110 
00113   ~PartitioningProblem() {};
00114 
00115 #ifdef HAVE_ZOLTAN2_MPI
00116 
00119   PartitioningProblem(Adapter *A, Teuchos::ParameterList *p, MPI_Comm comm); 
00120 
00121 #endif
00122 
00124   PartitioningProblem(Adapter *A, Teuchos::ParameterList *p) ;
00125 
00127   //
00128   //    \param updateInputData   If true this indicates that either
00129   //          this is the first attempt at solution, or that we
00130   //          are computing a new solution and the input data has
00131   //          changed since the previous solution was computed.  
00132   //          By input data we mean coordinates, topology, or weights.
00133   //          If false, this indicates that we are computing a
00134   //          new solution using the same input data was used for
00135   //          the previous solution, even though the parameters
00136   //          may have been changed.
00137   //
00138   //  For the sake of performance, we ask the caller to set \c updateInputData
00139   //  to false if he/she is computing a new solution using the same input data,
00140   //  but different problem parameters, than that which was used to compute 
00141   //  the most recent solution.
00142 
00143   void solve(bool updateInputData=true );
00144  
00146   //
00147   //   \return  a reference to the solution to the most recent solve().
00148 
00149   const PartitioningSolution<Adapter> &getSolution() {
00150     return *(solution_.getRawPtr());
00151   };
00152 
00161   const scalar_t getWeightImbalance(int idx=0) const {
00162     scalar_t imb = 0;
00163     if (!metrics_.is_null())
00164       metrics_->getWeightImbalance(imb, idx);
00165 
00166     return imb;
00167   }
00168 
00173   ArrayRCP<const MetricValues<scalar_t> > getMetrics() const {
00174    if (metrics_.is_null()){
00175       ArrayRCP<const MetricValues<scalar_t> > emptyMetrics;
00176       return emptyMetrics;
00177     }
00178     else
00179       return metrics_->getMetrics();
00180   }
00181 
00187   void printMetrics(std::ostream &os) const {
00188     if (metrics_.is_null())
00189       os << "No metrics available." << endl;
00190     else
00191       metrics_->printMetrics(os);
00192   };
00193 
00232   void setPartSizes(int len, part_t *partIds, scalar_t *partSizes, 
00233     bool makeCopy=true) 
00234   { 
00235     setPartSizesForCriteria(0, len, partIds, partSizes, makeCopy);
00236   }
00237 
00272   void setPartSizesForCriteria(int criteria, int len, part_t *partIds,
00273     scalar_t *partSizes, bool makeCopy=true) ;
00274 /*
00275   void setMachine(MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> *machine);
00276 */
00279   void resetParameters(ParameterList *params)
00280   {
00281     Problem<Adapter>::resetParameters(params);  // creates new environment
00282     if (timer_.getRawPtr() != NULL)
00283       this->env_->setTimer(timer_);
00284   }
00285 
00290   const RCP<const Environment> & getEnvironment() const 
00291   {
00292     return this->envConst_;
00293   }
00294 
00295 private:
00296   void initializeProblem();
00297 
00298   void createPartitioningProblem(bool newData);
00299 
00300   RCP<PartitioningSolution<Adapter> > solution_;
00301 
00302   RCP<MachineRepresentation <typename Adapter::base_adapter_t::scalar_t>  > machine_;
00303 
00304   RCP<Comm<int> > problemComm_;
00305   RCP<const Comm<int> > problemCommConst_;
00306 
00307 #ifdef HAVE_ZOLTAN2_MPI
00308   MPI_Comm mpiComm_;
00309 #endif
00310 
00311   BaseAdapterType inputType_;
00312 
00313   //ModelType modelType_;
00314   bool modelAvail_[MAX_NUM_MODEL_TYPES];
00315 
00316   modelFlag_t graphFlags_;
00317   modelFlag_t idFlags_;
00318   modelFlag_t coordFlags_;
00319   std::string algorithm_;
00320 
00321   int numberOfWeights_;
00322 
00323   // Suppose Array<part_t> partIds = partIds_[w].  If partIds.size() > 0
00324   // then the user supplied part sizes for weight index "w", and the sizes
00325   // corresponding to the Ids in partIds are partSizes[w].
00326   //
00327   // If numberOfWeights_ >= 0, then there is an Id and Sizes array for
00328   // for each weight.  Otherwise the user did not supply object weights,
00329   // but they can still specify part sizes. 
00330   // So numberOfCriteria_ is numberOfWeights_ or one, whichever is greater.
00331 
00332   ArrayRCP<ArrayRCP<part_t> > partIds_;
00333   ArrayRCP<ArrayRCP<scalar_t> > partSizes_;
00334   int numberOfCriteria_;
00335 
00336   // Number of parts to be computed at each level in hierarchical partitioning.
00337   
00338   ArrayRCP<int> levelNumberParts_;
00339   bool hierarchical_;
00340 
00341   // Create a Timer if the user asked for timing stats.
00342 
00343   RCP<TimerManager> timer_;
00344 
00345   // Did the user request metrics?
00346 
00347   bool metricsRequested_;
00348   RCP<const PartitioningSolutionQuality<Adapter> > metrics_;
00349 };
00351 
00352 #ifdef HAVE_ZOLTAN2_MPI
00353 template <typename Adapter>
00354   PartitioningProblem<Adapter>::PartitioningProblem(Adapter *A, 
00355     ParameterList *p, MPI_Comm comm):
00356       Problem<Adapter>(A,p,comm), solution_(),
00357       problemComm_(), problemCommConst_(),
00358       inputType_(InvalidAdapterType), 
00359       graphFlags_(), idFlags_(), coordFlags_(), algorithm_(),
00360       numberOfWeights_(), partIds_(), partSizes_(), 
00361       numberOfCriteria_(), levelNumberParts_(), hierarchical_(false), 
00362       timer_(), metricsRequested_(false), metrics_()
00363 {
00364 
00365   for(int i=0;i<MAX_NUM_MODEL_TYPES;i++)
00366   {
00367     modelAvail_[i]=false;
00368   }
00369 
00370   initializeProblem();
00371 
00372 }
00373 #endif
00374 /*
00375 template <typename Adapter>
00376 void PartitioningProblem<Adapter>::setMachine(MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> *machine){
00377   this->machine_ = RCP<MachineRepresentation<typename Adapter::base_adapter_t::scalar_t> > (machine, false);
00378 }
00379 */
00380 template <typename Adapter>
00381   PartitioningProblem<Adapter>::PartitioningProblem(Adapter *A, 
00382     ParameterList *p):
00383       Problem<Adapter>(A,p), solution_(),
00384       problemComm_(), problemCommConst_(),
00385       inputType_(InvalidAdapterType), 
00386       graphFlags_(), idFlags_(), coordFlags_(), algorithm_(),
00387       numberOfWeights_(), 
00388       partIds_(), partSizes_(), numberOfCriteria_(), 
00389       levelNumberParts_(), hierarchical_(false), timer_(),
00390       metricsRequested_(false), metrics_()
00391 {
00392   for(int i=0;i<MAX_NUM_MODEL_TYPES;i++)
00393   {
00394     modelAvail_[i]=false;
00395   }
00396 
00397   initializeProblem();
00398 }
00399 
00400 template <typename Adapter>
00401   void PartitioningProblem<Adapter>::initializeProblem()
00402 {
00403   HELLO;
00404 
00405   this->env_->debug(DETAILED_STATUS, "PartitioningProblem::initializeProblem");
00406 
00407   if (getenv("DEBUGME")){
00408     std::cout << getpid() << std::endl;
00409     sleep(15);
00410   }
00411 
00412 #ifdef HAVE_ZOLTAN2_OVIS
00413   ovis_enabled(this->comm_->getRank());
00414 #endif
00415 
00416   // Create a copy of the user's communicator.  
00417 
00418   problemComm_ = this->comm_->duplicate();
00419   problemCommConst_ = rcp_const_cast<const Comm<int> > (problemComm_);
00420 
00421   machine_ = RCP <Zoltan2::MachineRepresentation<typename Adapter::scalar_t> >(new Zoltan2::MachineRepresentation<typename Adapter::scalar_t>(problemComm_));
00422 #ifdef HAVE_ZOLTAN2_MPI
00423 
00424   // TPLs may want an MPI communicator
00425 
00426   mpiComm_ = Teuchos2MPI(problemComm_);
00427 
00428 #endif
00429 
00430   // Number of criteria is number of user supplied weights if non-zero.
00431   // Otherwise it is 1 and uniform weight is implied.
00432 
00433   numberOfWeights_ = this->inputAdapter_->getNumWeightsPerID();
00434 
00435   numberOfCriteria_ = (numberOfWeights_ > 1) ? numberOfWeights_ : 1;
00436 
00437   inputType_ = this->inputAdapter_->adapterType();
00438 
00439   // The Caller can specify part sizes in setPartSizes().  If he/she
00440   // does not, the part size arrays are empty.
00441 
00442   ArrayRCP<part_t> *noIds = new ArrayRCP<part_t> [numberOfCriteria_];
00443   ArrayRCP<scalar_t> *noSizes = new ArrayRCP<scalar_t> [numberOfCriteria_];
00444 
00445   partIds_ = arcp(noIds, 0, numberOfCriteria_, true);
00446   partSizes_ = arcp(noSizes, 0, numberOfCriteria_, true);
00447 
00448   if (this->env_->getDebugLevel() >= DETAILED_STATUS){
00449     std::ostringstream msg;
00450     msg << problemComm_->getSize() << " procs,"
00451       << numberOfWeights_ << " user-defined weights\n";
00452     this->env_->debug(DETAILED_STATUS, msg.str());
00453   }
00454 
00455   this->env_->memory("After initializeProblem");
00456 }
00457 
00458 template <typename Adapter>
00459   void PartitioningProblem<Adapter>::setPartSizesForCriteria(
00460     int criteria, int len, part_t *partIds, scalar_t *partSizes, bool makeCopy) 
00461 {
00462   this->env_->localInputAssertion(__FILE__, __LINE__, "invalid length", 
00463     len>= 0, BASIC_ASSERTION);
00464 
00465   this->env_->localInputAssertion(__FILE__, __LINE__, "invalid criteria", 
00466     criteria >= 0 && criteria < numberOfCriteria_, BASIC_ASSERTION);
00467 
00468   if (len == 0){
00469     partIds_[criteria] = ArrayRCP<part_t>();
00470     partSizes_[criteria] = ArrayRCP<scalar_t>();
00471     return;
00472   }
00473 
00474   this->env_->localInputAssertion(__FILE__, __LINE__, "invalid arrays", 
00475     partIds && partSizes, BASIC_ASSERTION);
00476 
00477   // The global validity of the partIds and partSizes arrays is performed
00478   // by the PartitioningSolution, which computes global part distribution and
00479   // part sizes.
00480 
00481   part_t *z2_partIds = NULL;
00482   scalar_t *z2_partSizes = NULL;
00483   bool own_memory = false;
00484 
00485   if (makeCopy){
00486     z2_partIds = new part_t [len];
00487     z2_partSizes = new scalar_t [len];
00488     this->env_->localMemoryAssertion(__FILE__, __LINE__, len, z2_partSizes);
00489     memcpy(z2_partIds, partIds, len * sizeof(part_t));
00490     memcpy(z2_partSizes, partSizes, len * sizeof(scalar_t));
00491     own_memory=true;
00492   }
00493   else{
00494     z2_partIds = partIds;
00495     z2_partSizes = partSizes;
00496   }
00497 
00498   partIds_[criteria] = arcp(z2_partIds, 0, len, own_memory);
00499   partSizes_[criteria] = arcp(z2_partSizes, 0, len, own_memory);
00500 }
00501 
00502 template <typename Adapter>
00503 void PartitioningProblem<Adapter>::solve(bool updateInputData)
00504 {
00505   HELLO;
00506   this->env_->debug(DETAILED_STATUS, "Entering solve");
00507 
00508   // Create the computational model.
00509 
00510   this->env_->timerStart(MACRO_TIMERS, "create problem");
00511 
00512   createPartitioningProblem(updateInputData);
00513 
00514   this->env_->timerStop(MACRO_TIMERS, "create problem");
00515 
00516   // TODO: If hierarchical_
00517 
00518   // Create the solution. The algorithm will query the Solution
00519   //   for part and weight information. The algorithm will
00520   //   update the solution with part assignments and quality
00521   //   metrics.  The Solution object itself will convert our internal
00522   //   global numbers back to application global Ids if needed.
00523 
00524   RCP<const IdentifierMap<user_t> > idMap = 
00525     this->baseModel_->getIdentifierMap();
00526 
00527   PartitioningSolution<Adapter> *soln = NULL;
00528 
00529   this->env_->timerStart(MACRO_TIMERS, "create solution");
00530 
00531   try{
00532     soln = new PartitioningSolution<Adapter>( 
00533       this->envConst_, problemCommConst_, idMap, numberOfWeights_, 
00534       partIds_.view(0, numberOfCriteria_), 
00535       partSizes_.view(0, numberOfCriteria_));
00536   }
00537   Z2_FORWARD_EXCEPTIONS;
00538 
00539   solution_ = rcp(soln);
00540 
00541   this->env_->timerStop(MACRO_TIMERS, "create solution");
00542 
00543   this->env_->memory("After creating Solution");
00544 
00545   // Call the algorithm
00546 
00547   try {
00548     if (algorithm_ == std::string("scotch")){
00549       AlgPTScotch<Adapter>(this->envConst_, problemComm_,
00550 #ifdef HAVE_ZOLTAN2_MPI
00551         mpiComm_,
00552 #endif
00553         this->graphModel_, solution_);
00554     }
00555     else if (algorithm_ == std::string("block")){
00556       AlgBlock<Adapter> algblock(this->envConst_, problemComm_,
00557         this->identifierModel_, solution_);
00558       algblock.partition();
00559     }
00560     else if (algorithm_ == std::string("rcb")){
00561       AlgRCB<Adapter>(this->envConst_, problemComm_,
00562         this->coordinateModel_, solution_);
00563     }
00564     else if (algorithm_ == std::string("multijagged")){
00565       Zoltan2_AlgMJ<Adapter> alg_mj;
00566       alg_mj.partition( this->envConst_, problemComm_,
00567          this->coordinateModel_, solution_);
00568     }
00569     else if (algorithm_ == std::string("wolf"))
00570     {
00571       AlgWolf<Adapter> alg_wolf(this->envConst_, problemComm_,this->graphModel_,
00572         this->coordinateModel_);
00573 
00574       // need to add coordModel, make sure this is built
00575 
00576       alg_wolf.partition(solution_);
00577 
00578     }
00579     else
00580     {
00581       throw std::logic_error("partitioning algorithm not supported yet");
00582     }
00583   }
00584   Z2_FORWARD_EXCEPTIONS;
00585 
00586   //if mapping is requested
00587   const Teuchos::ParameterEntry *pe = this->envConst_->getParameters().getEntryPtr("mapping_type");
00588   int mapping_type = -1;
00589   if (pe){
00590     mapping_type = pe->getValue(&mapping_type);
00591   }
00592   //if mapping is 0 -- coordinate mapping
00593 
00594   if (mapping_type == 0){
00595 
00596     //part_t *task_communication_xadj = NULL, *task_communication_adj = NULL;
00597 
00598     Zoltan2::CoordinateTaskMapper <Adapter, part_t> *ctm=
00599                   new Zoltan2::CoordinateTaskMapper<Adapter,part_t>(
00600                           problemComm_.getRawPtr(),
00601                           machine_.getRawPtr(),
00602                           this->coordinateModel_.getRawPtr(),
00603                           solution_.getRawPtr(),
00604                           this->envConst_.getRawPtr()
00605                           //,task_communication_xadj,
00606                           //task_communication_adj
00607                           );
00608     //for now just delete the object.
00609     delete ctm;
00610   }
00611   else if (mapping_type == 1){
00612     //if mapping is 1 -- graph mapping
00613   }
00614 
00615 #ifdef KDDKDD_SHOULD_NEVER_CHANGE_PROBLEMCOMM
00616 #ifdef HAVE_ZOLTAN2_MPI
00617 
00618   // The algorithm may have changed the communicator.  Change it back.
00619   // KDD:  Why would the algorithm change the communicator? TODO
00620   // KDD:  Should we allow such a side effect? TODO
00621 
00622   RCP<const mpiWrapper_t > wrappedComm = rcp(new mpiWrapper_t(mpiComm_));
00623   problemComm_ = rcp(new Teuchos::MpiComm<int>(wrappedComm));
00624   problemCommConst_ = rcp_const_cast<const Comm<int> > (problemComm_);
00625 
00626 #endif
00627 #endif
00628 
00629   if (metricsRequested_){
00630     typedef PartitioningSolution<Adapter> ps_t;
00631     typedef PartitioningSolutionQuality<Adapter> psq_t;
00632 
00633     psq_t *quality = NULL;
00634     RCP<const ps_t> solutionConst = rcp_const_cast<const ps_t>(solution_);
00635     RCP<const Adapter> adapter = rcp(this->inputAdapter_, false);
00636 
00637     try{
00638       quality = new psq_t(this->envConst_, problemCommConst_, adapter, 
00639         solutionConst);
00640     }
00641     Z2_FORWARD_EXCEPTIONS
00642 
00643     metrics_ = rcp(quality);
00644   }
00645 
00646   this->env_->debug(DETAILED_STATUS, "Exiting solve");
00647 }
00648 
00649 template <typename Adapter>
00650 void PartitioningProblem<Adapter>::createPartitioningProblem(bool newData)
00651 {
00652   HELLO;
00653   this->env_->debug(DETAILED_STATUS, 
00654     "PartitioningProblem::createPartitioningProblem");
00655 
00656   using std::string;
00657   using Teuchos::ParameterList;
00658 
00659   // A Problem object may be reused.  The input data may have changed and
00660   // new parameters or part sizes may have been set.
00661   //
00662   // Save these values in order to determine if we need to create a new model.
00663 
00664   //ModelType previousModel = modelType_;
00665   bool prevModelAvail[MAX_NUM_MODEL_TYPES];
00666   for(int i=0;i<MAX_NUM_MODEL_TYPES;i++)
00667   {
00668     prevModelAvail[i] = modelAvail_[i];
00669   }
00670 
00671 
00672   modelFlag_t previousGraphModelFlags = graphFlags_;
00673   modelFlag_t previousIdentifierModelFlags = idFlags_;
00674   modelFlag_t previousCoordinateModelFlags = coordFlags_;
00675 
00676   //modelType_ = InvalidModel;
00677   for(int i=0;i<MAX_NUM_MODEL_TYPES;i++)
00678   {
00679     modelAvail_[i] = false;
00680   }
00681 
00682   graphFlags_.reset();
00683   idFlags_.reset();
00684   coordFlags_.reset();
00685 
00687   // It's possible at this point that the Problem may want to
00688   // add problem parameters to the parameter list in the Environment. 
00689   //
00690   // Since the parameters in the Environment have already been
00691   // validated in its constructor, a new Environment must be created:
00693   // Teuchos::RCP<const Teuchos::Comm<int> > oldComm = this->env_->comm_;
00694   // const ParameterList &oldParams = this->env_->getUnvalidatedParameters();
00695   // 
00696   // ParameterList newParams = oldParams;
00697   // newParams.set("new_parameter", "new_value");
00698   // 
00699   // ParameterList &newPartParams = newParams.sublist("partitioning");
00700   // newPartParams.set("new_partitioning_parameter", "its_value");
00701   // 
00702   // this->env_ = rcp(new Environment(newParams, oldComm));
00704 
00705   this->env_->debug(DETAILED_STATUS, "    parameters");
00706   Environment &env = *(this->env_);
00707   ParameterList &pl = env.getParametersNonConst();
00708 
00709   std::string defString("default");
00710 
00711   // Did the user ask for computation of quality metrics?
00712 
00713   int yesNo=0;
00714   const Teuchos::ParameterEntry *pe = pl.getEntryPtr("compute_metrics");
00715   if (pe){
00716     yesNo = pe->getValue<int>(&yesNo);
00717     metricsRequested_ = true;
00718   }
00719 
00720   // Did the user specify a computational model?
00721 
00722   std::string model(defString);
00723   pe = pl.getEntryPtr("model");
00724   if (pe)
00725     model = pe->getValue<std::string>(&model);
00726 
00727   // Did the user specify an algorithm?
00728 
00729   std::string algorithm(defString);
00730   pe = pl.getEntryPtr("algorithm");
00731   if (pe)
00732     algorithm = pe->getValue<std::string>(&algorithm);
00733 
00734   // Possible algorithm requirements that must be conveyed to the model:
00735 
00736   bool needConsecutiveGlobalIds = false;
00737   bool removeSelfEdges= false;
00738 
00740   // Determine algorithm, model, and algorithm requirements.  This
00741   // is a first pass.  Feel free to change this and add to it.
00742 
00743   if (algorithm != defString)
00744   {
00745 
00746     // Figure out the model required by the algorithm
00747     if (algorithm == std::string("block") ||
00748         algorithm == std::string("random") ||
00749         algorithm == std::string("cyclic") ){
00750 
00751       //modelType_ = IdentifierModelType;
00752       modelAvail_[IdentifierModelType] = true;
00753 
00754       algorithm_ = algorithm;
00755       needConsecutiveGlobalIds = true;
00756     }
00757     else if (algorithm == std::string("rcb") ||
00758              algorithm == std::string("rib") ||
00759              algorithm == std::string("multijagged") ||
00760              algorithm == std::string("hsfc"))
00761     {
00762       //modelType_ = CoordinateModelType;
00763       modelAvail_[CoordinateModelType]=true;
00764     
00765       algorithm_ = algorithm;
00766     }
00767     else if (algorithm == std::string("metis") ||
00768              algorithm == std::string("parmetis") ||
00769              algorithm == std::string("scotch") ||
00770              algorithm == std::string("ptscotch"))
00771     {
00772 
00773       //modelType_ = GraphModelType;
00774       modelAvail_[GraphModelType]=true;
00775 
00776       algorithm_ = algorithm;
00777       removeSelfEdges = true;
00778       needConsecutiveGlobalIds = true;
00779     }
00780     else if (algorithm == std::string("patoh") ||
00781              algorithm == std::string("phg"))
00782     {
00783       // if ((modelType_ != GraphModelType) &&
00784       //     (modelType_ != HypergraphModelType) )
00785       if ((modelAvail_[GraphModelType]==false) &&
00786           (modelAvail_[HypergraphModelType]==false) )
00787       {
00788         //modelType_ = HypergraphModelType;
00789         modelAvail_[HypergraphModelType]=true;
00790       }
00791       algorithm_ = algorithm;
00792       needConsecutiveGlobalIds = true;
00793     }
00794     else if (algorithm == std::string("wolf"))
00795     {
00796       modelAvail_[GraphModelType]=true;
00797       modelAvail_[CoordinateModelType]=true;
00798       algorithm_ = algorithm;
00799     }
00800     else
00801     {
00802       // Parameter list should ensure this does not happen.
00803       throw std::logic_error("parameter list algorithm is invalid");
00804     }
00805   }
00806   else if (model != defString)
00807   {
00808     // Figure out the algorithm suggested by the model.
00809     if (model == std::string("hypergraph"))
00810     {      
00811       //modelType_ = HypergraphModelType;
00812       modelAvail_[HypergraphModelType]=true;
00813 
00814       if (problemComm_->getSize() > 1)
00815         algorithm_ = std::string("phg"); 
00816       else
00817         algorithm_ = std::string("patoh"); 
00818       needConsecutiveGlobalIds = true;
00819     }
00820     else if (model == std::string("graph"))
00821     {
00822       //modelType_ = GraphModelType;
00823       modelAvail_[GraphModelType]=true;
00824 
00825 #ifdef HAVE_ZOLTAN2_SCOTCH
00826       if (problemComm_->getSize() > 1)
00827         algorithm_ = std::string("ptscotch"); 
00828       else
00829         algorithm_ = std::string("scotch"); 
00830       removeSelfEdges = true;
00831       needConsecutiveGlobalIds = true;
00832 #else
00833 #ifdef HAVE_ZOLTAN2_PARMETIS
00834       if (problemComm_->getSize() > 1)
00835         algorithm_ = std::string("parmetis"); 
00836       else
00837         algorithm_ = std::string("metis"); 
00838       removeSelfEdges = true;
00839       needConsecutiveGlobalIds = true;
00840 #else
00841       if (problemComm_->getSize() > 1)
00842         algorithm_ = std::string("phg"); 
00843       else
00844         algorithm_ = std::string("patoh"); 
00845       removeSelfEdges = true;
00846       needConsecutiveGlobalIds = true;
00847 #endif
00848 #endif
00849     }
00850     else if (model == std::string("geometry"))
00851     {
00852       //modelType_ = CoordinateModelType;
00853       modelAvail_[CoordinateModelType]=true;
00854 
00855       algorithm_ = std::string("rcb");
00856     }
00857     else if (model == std::string("ids"))
00858     {
00859       //modelType_ = IdentifierModelType;
00860       modelAvail_[IdentifierModelType]=true;
00861 
00862       algorithm_ = std::string("block");
00863       needConsecutiveGlobalIds = true;
00864     }
00865     else
00866     {
00867       // Parameter list should ensure this does not happen.
00868       env.localBugAssertion(__FILE__, __LINE__, 
00869         "parameter list model type is invalid", 1, BASIC_ASSERTION);
00870     }
00871   }
00872   else
00873   {   
00874     // Determine an algorithm and model suggested by the input type.
00875     //   TODO: this is a good time to use the time vs. quality parameter
00876     //     in choosing an algorithm, and setting some parameters
00877 
00878     if (inputType_ == MatrixAdapterType)
00879     {
00880       //modelType_ = HypergraphModelType;
00881       modelAvail_[HypergraphModelType]=true;
00882       
00883       if (problemComm_->getSize() > 1)
00884         algorithm_ = std::string("phg"); 
00885       else
00886         algorithm_ = std::string("patoh"); 
00887     }
00888     else if (inputType_ == GraphAdapterType ||
00889         inputType_ == MeshAdapterType)
00890     {
00891       //modelType_ = GraphModelType;
00892       modelAvail_[GraphModelType]=true;
00893 
00894       if (problemComm_->getSize() > 1)
00895         algorithm_ = std::string("phg"); 
00896       else
00897         algorithm_ = std::string("patoh"); 
00898     }
00899     else if (inputType_ == CoordinateAdapterType)
00900     {
00901       //modelType_ = CoordinateModelType;
00902       modelAvail_[CoordinateModelType]=true;
00903 
00904       if(algorithm_ != std::string("multijagged"))
00905       algorithm_ = std::string("rcb");
00906     }
00907     else if (inputType_ == VectorAdapterType ||
00908              inputType_ == IdentifierAdapterType)
00909     {
00910       //modelType_ = IdentifierModelType;
00911       modelAvail_[IdentifierModelType]=true;
00912 
00913       algorithm_ = std::string("block");
00914     }
00915     else{
00916       // This should never happen
00917       throw std::logic_error("input type is invalid");
00918     }
00919   }
00920 
00921   // Hierarchical partitioning?
00922 
00923   Array<int> valueList;
00924   pe = pl.getEntryPtr("topology");
00925 
00926   if (pe){
00927     valueList = pe->getValue<Array<int> >(&valueList);
00928 
00929     if (!Zoltan2::noValuesAreInRangeList<int>(valueList)){
00930       int *n = new int [valueList.size() + 1];
00931       levelNumberParts_ = arcp(n, 0, valueList.size() + 1, true);
00932       int procsPerNode = 1;
00933       for (int i=0; i < valueList.size(); i++){
00934         levelNumberParts_[i+1] = valueList[i];
00935         procsPerNode *= valueList[i];
00936       }
00937       // Number of parts in the first level
00938       levelNumberParts_[0] = env.numProcs_ / procsPerNode;
00939 
00940       if (env.numProcs_ % procsPerNode > 0)
00941         levelNumberParts_[0]++;
00942     }
00943   }
00944   else{
00945     levelNumberParts_.clear();
00946   }
00947 
00948   hierarchical_ = levelNumberParts_.size() > 0;
00949 
00950   // Object to be partitioned? (rows, columns, etc)
00951 
00952   std::string objectOfInterest(defString);
00953   pe = pl.getEntryPtr("objects_to_partition");
00954   if (pe)
00955     objectOfInterest = pe->getValue<std::string>(&objectOfInterest);
00956 
00958   // Set model creation flags, if any.
00959 
00960   this->env_->debug(DETAILED_STATUS, "    models");
00961   //  if (modelType_ == GraphModelType)
00962   if (modelAvail_[GraphModelType]==true)
00963   {
00964 
00965     // Any parameters in the graph sublist?
00966 
00967     std::string symParameter(defString);
00968     pe = pl.getEntryPtr("symmetrize_graph");
00969     if (pe){
00970       symParameter = pe->getValue<std::string>(&symParameter);
00971       if (symParameter == std::string("transpose"))
00972         graphFlags_.set(SYMMETRIZE_INPUT_TRANSPOSE);
00973       else if (symParameter == std::string("bipartite"))
00974         graphFlags_.set(SYMMETRIZE_INPUT_BIPARTITE);
00975     } 
00976 
00977     int sgParameter = 0;
00978     pe = pl.getEntryPtr("subset_graph");
00979     if (pe)
00980       sgParameter = pe->getValue<int>(&sgParameter);
00981 
00982     if (sgParameter == 1)
00983         graphFlags_.set(GRAPH_IS_A_SUBSET_GRAPH);
00984 
00985     // Any special behaviors required by the algorithm?
00986     
00987     if (removeSelfEdges)
00988       graphFlags_.set(SELF_EDGES_MUST_BE_REMOVED);
00989 
00990     if (needConsecutiveGlobalIds)
00991       graphFlags_.set(IDS_MUST_BE_GLOBALLY_CONSECUTIVE);
00992 
00993     // How does user input map to vertices and edges?
00994 
00995     if (inputType_ == MatrixAdapterType){
00996       if (objectOfInterest == defString ||
00997           objectOfInterest == std::string("matrix_rows") )
00998         graphFlags_.set(VERTICES_ARE_MATRIX_ROWS);
00999       else if (objectOfInterest == std::string("matrix_columns"))
01000         graphFlags_.set(VERTICES_ARE_MATRIX_COLUMNS);
01001       else if (objectOfInterest == std::string("matrix_nonzeros"))
01002         graphFlags_.set(VERTICES_ARE_MATRIX_NONZEROS);
01003     }
01004 
01005     else if (inputType_ == MeshAdapterType){
01006       if (objectOfInterest == defString ||
01007           objectOfInterest == std::string("mesh_nodes") )
01008         graphFlags_.set(VERTICES_ARE_MESH_NODES);
01009       else if (objectOfInterest == std::string("mesh_elements"))
01010         graphFlags_.set(VERTICES_ARE_MESH_ELEMENTS);
01011     } 
01012   }
01013   //MMW is it ok to remove else?
01014   //  else if (modelType_ == IdentifierModelType)
01015   if (modelAvail_[IdentifierModelType]==true)
01016   {
01017 
01018     // Any special behaviors required by the algorithm?
01019     
01020     if (needConsecutiveGlobalIds)
01021       idFlags_.set(IDS_MUST_BE_GLOBALLY_CONSECUTIVE);
01022   }
01023   //  else if (modelType_ == CoordinateModelType)
01024   if (modelAvail_[CoordinateModelType]==true)
01025   {
01026 
01027     // Any special behaviors required by the algorithm?
01028     
01029     if (needConsecutiveGlobalIds)
01030       coordFlags_.set(IDS_MUST_BE_GLOBALLY_CONSECUTIVE);
01031   }
01032 
01033 
01034   if ( newData ||
01035        (modelAvail_[GraphModelType]!=prevModelAvail[GraphModelType]) ||
01036        (modelAvail_[HypergraphModelType]!=prevModelAvail[HypergraphModelType]) ||
01037        (modelAvail_[CoordinateModelType]!=prevModelAvail[CoordinateModelType]) ||
01038        (modelAvail_[IdentifierModelType]!=prevModelAvail[IdentifierModelType]) ||
01039   //       (modelType_ != previousModel) ||
01040        (graphFlags_ != previousGraphModelFlags) ||
01041        (coordFlags_ != previousCoordinateModelFlags) ||
01042        (idFlags_ != previousIdentifierModelFlags) ) 
01043   {
01044 
01045     // Create the computational model.
01046     // Models are instantiated for base input adapter types (mesh,
01047     // matrix, graph, and so on).  We pass a pointer to the input
01048     // adapter, cast as the base input type.
01049 
01050     //KDD Not sure why this shadow declaration is needed
01051     //KDD Comment out for now; revisit later if problems.
01052     //KDD const Teuchos::ParameterList pl = this->envConst_->getParameters();
01053     //bool exceptionThrow = true;
01054 
01055     if(modelAvail_[GraphModelType]==false && modelAvail_[HypergraphModelType]==false &&
01056        modelAvail_[CoordinateModelType]==false && modelAvail_[IdentifierModelType]==false)
01057     {
01058       cout << __func__ << " Invalid model"  << endl;
01059     }
01060     else
01061     {
01062       if(modelAvail_[GraphModelType]==true)
01063       {
01064         this->env_->debug(DETAILED_STATUS, "    building graph model");
01065         this->graphModel_ = rcp(new GraphModel<base_adapter_t>(
01066           this->baseInputAdapter_, this->envConst_, problemComm_, graphFlags_));
01067 
01068         this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(this->graphModel_);
01069       }
01070       if(modelAvail_[HypergraphModelType]==true)
01071       {
01072   std::cout << "Hypergraph model not implemented yet..." << std::endl;
01073       }
01074 
01075       if(modelAvail_[CoordinateModelType]==true)
01076       {
01077         this->env_->debug(DETAILED_STATUS, "    building coordinate model");
01078         this->coordinateModel_ = rcp(new CoordinateModel<base_adapter_t>(
01079                    this->baseInputAdapter_, this->envConst_, problemComm_, coordFlags_));
01080 
01081         this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(this->coordinateModel_);
01082       }
01083 
01084       if(modelAvail_[IdentifierModelType]==true)
01085       {
01086         this->env_->debug(DETAILED_STATUS, "    building identifier model");
01087         this->identifierModel_ = rcp(new IdentifierModel<base_adapter_t>(
01088                                      this->baseInputAdapter_, this->envConst_, problemComm_, idFlags_));
01089 
01090         this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(this->identifierModel_);
01091       }
01092   
01093 
01094     }
01095 
01096 
01097 
01098     this->env_->memory("After creating Model");
01099     this->env_->debug(DETAILED_STATUS, "createPartitioningProblem done");
01100   }
01101 
01102 }
01103 
01104 }  // namespace Zoltan2
01105 #endif