Zoltan2
Zoltan2_OrderingProblem.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_ORDERINGPROBLEM_HPP_
00051 #define _ZOLTAN2_ORDERINGPROBLEM_HPP_
00052 
00053 #include <Zoltan2_Problem.hpp>
00054 #include <Zoltan2_OrderingAlgorithms.hpp>
00055 #include <Zoltan2_OrderingSolution.hpp>
00056 
00057 #include <Zoltan2_GraphModel.hpp>
00058 #include <string>
00059 #ifdef HAVE_ZOLTAN2_OVIS
00060 #include <ovis.h>
00061 #endif
00062 
00063 #include <bitset>
00064 
00065 using Teuchos::rcp_dynamic_cast;
00066 
00067 namespace Zoltan2{
00068 
00070 
00089 template<typename Adapter>
00090 class OrderingProblem : public Problem<Adapter>
00091 {
00092 public:
00093 
00094   typedef typename Adapter::scalar_t scalar_t;
00095   typedef typename Adapter::zgid_t zgid_t;
00096   typedef typename Adapter::gno_t gno_t;
00097   typedef typename Adapter::lno_t lno_t;
00098   typedef typename Adapter::user_t user_t;
00099   typedef typename Adapter::base_adapter_t base_adapter_t;
00100 
00101 #ifdef HAVE_ZOLTAN2_MPI
00102    typedef Teuchos::OpaqueWrapper<MPI_Comm> mpiWrapper_t;
00103 #endif
00104 
00107   virtual ~OrderingProblem() {};
00108 
00109 
00110 #ifdef HAVE_ZOLTAN2_MPI
00111 
00113   OrderingProblem(Adapter *A, ParameterList *p, MPI_Comm comm) 
00114                       : Problem<Adapter>(A, p, comm) 
00115   {
00116     HELLO;
00117     createOrderingProblem();
00118   };
00119 #endif
00120 
00123   OrderingProblem(Adapter *A, ParameterList *p) : Problem<Adapter>(A, p) 
00124   {
00125     HELLO;
00126     createOrderingProblem();
00127   };
00128 
00130   //
00131   //    \param updateInputData   If true this indicates that either
00132   //          this is the first attempt at solution, or that we
00133   //          are computing a new solution and the input data has
00134   //          changed since the previous solution was computed.
00135   //          If false, this indicates that we are computing a
00136   //          new solution using the same input data was used for
00137   //          the previous solution, even though the parameters
00138   //          may have been changed.
00139   //
00140   //  For the sake of performance, we ask the caller to set \c updateInputData
00141   //  to false if he/she is computing a new solution using the same input data,
00142   //  but different problem parameters, than that which was used to compute
00143   //  the most recent solution.
00144   
00145   void solve(bool updateInputData=true);
00146 
00148   //
00149   //   \return  a reference to the solution to the most recent solve().
00150 
00151   OrderingSolution<zgid_t, lno_t> *getSolution() {
00152     // cout << "havePerm= " << solution_->havePerm() <<  " haveInverse= " << solution_->haveInverse() << endl;
00153     // Compute Perm or InvPerm, if one is missing.
00154     if (!(solution_->havePerm()))
00155       solution_->computePerm();
00156     if (!(solution_->haveInverse()))
00157       solution_->computeInverse();
00158     return solution_.getRawPtr();
00159   };
00160 
00161 private:
00162   void createOrderingProblem();
00163 
00164   RCP<OrderingSolution<zgid_t, lno_t> > solution_;
00165 
00166   RCP<Comm<int> > problemComm_;
00167   RCP<const Comm<int> > problemCommConst_;
00168 
00169 #ifdef HAVE_ZOLTAN2_MPI
00170   MPI_Comm mpiComm_;
00171 #endif
00172 };
00173 
00175 template <typename Adapter>
00176 void OrderingProblem<Adapter>::solve(bool newData)
00177 {
00178   HELLO;
00179 
00180   size_t nVtx = this->baseModel_->getLocalNumObjects();
00181 
00182   // TODO: Assuming one MPI process now. nVtx = ngids = nlids
00183   try
00184   {
00185       this->solution_ = rcp(new OrderingSolution<zgid_t, lno_t>(nVtx));
00186   }
00187   Z2_FORWARD_EXCEPTIONS;
00188 
00189   // Reset status for perm and InvPerm.
00190   this->solution_->setHavePerm(false);
00191   this->solution_->setHaveInverse(false);
00192 
00193   // Determine which algorithm to use based on defaults and parameters.
00194   // TODO: Use rcm if graph model is defined, otherwise use natural.
00195   // Need some exception handling here, too.
00196 
00197   std::string method = this->params_->template get<std::string>("order_method", "rcm");
00198 
00199   // TODO: Ignore case
00200   try
00201   {
00202   if (method.compare("rcm") == 0)
00203   {
00204       AlgRCM<base_adapter_t> alg(this->graphModel_,
00205                                  this->params_, problemComm_);
00206       alg.order(this->solution_);
00207   }
00208   else if (method.compare("natural") == 0)
00209   {
00210       AlgNatural<base_adapter_t> alg(this->identifierModel_,
00211                                      this->params_, problemComm_);
00212       alg.order(this->solution_);
00213   }
00214   else if (method.compare("random") == 0)
00215   {
00216       AlgRandom<base_adapter_t> alg(this->identifierModel_,
00217                                     this->params_, problemComm_);
00218       alg.order(this->solution_);
00219   }
00220   else if (method.compare("sorted_degree") == 0)
00221   {
00222       AlgSortedDegree<base_adapter_t> alg(this->graphModel_,
00223                                           this->params_, problemComm_);
00224       alg.order(this->solution_);
00225   }
00226   else if (method.compare("minimum_degree") == 0)
00227   {
00228       std::string pkg = this->params_->template get<std::string>("order_package", "amd");
00229       if (pkg.compare("amd") == 0)
00230       {
00231           AlgAMD<base_adapter_t> alg(this->graphModel_,
00232                                      this->params_, problemComm_);
00233           alg.order(this->solution_);
00234       }
00235   }
00236   }
00237   Z2_FORWARD_EXCEPTIONS;
00238 
00239 #ifdef HAVE_ZOLTAN2_MPI
00240 
00241   // The algorithm may have changed the communicator.  Change it back.
00242 
00243   RCP<const mpiWrapper_t > wrappedComm = rcp(new mpiWrapper_t(mpiComm_));
00244   problemComm_ = rcp(new Teuchos::MpiComm<int>(wrappedComm));
00245   problemCommConst_ = rcp_const_cast<const Comm<int> > (problemComm_);
00246 
00247 #endif
00248 
00249 }
00250 
00252 //template <typename Adapter>
00253 //void OrderingProblem<Adapter>::redistribute()
00254 //{
00255 //  HELLO;
00256 //}
00257 
00260 //  Method with common functionality for creating a OrderingProblem.
00261 //  Individual constructors do appropriate conversions of input, etc.
00262 //  This method does everything that all constructors must do.
00263 
00264 template <typename Adapter>
00265 void OrderingProblem<Adapter>::createOrderingProblem()
00266 {
00267   HELLO;
00268   using Teuchos::ParameterList;
00269 
00270 //  cout << __func__ << " input adapter type " 
00271 //       << this->inputAdapter_->inputAdapterType() << " " 
00272 //       << this->inputAdapter_->inputAdapterName() << endl;
00273 
00274 #ifdef HAVE_ZOLTAN2_OVIS
00275   ovis_enabled(this->comm_->getRank());
00276 #endif
00277 
00278   // Create a copy of the user's communicator.
00279 
00280   problemComm_ = this->comm_->duplicate();
00281   problemCommConst_ = rcp_const_cast<const Comm<int> > (problemComm_);
00282 
00283 
00284 #ifdef HAVE_ZOLTAN2_MPI
00285 
00286   // TPLs may want an MPI communicator
00287 
00288   Comm<int> *c = problemComm_.getRawPtr();
00289   Teuchos::MpiComm<int> *mc = dynamic_cast<Teuchos::MpiComm<int> *>(c);
00290   if (mc){
00291     RCP<const mpiWrapper_t> wrappedComm = mc->getRawMpiComm();
00292     mpiComm_ = (*wrappedComm.getRawPtr())();
00293   }
00294   else{
00295     mpiComm_ = MPI_COMM_SELF;   // or would this be an error?
00296   }
00297 
00298 #endif
00299 
00300   // Determine which parameters are relevant here.
00301   // For now, assume parameters similar to Zoltan:
00302   //   MODEL = graph, hypergraph, geometric, ids
00303   //   ALGORITHM = rcm, random, amd
00304 
00305   ModelType modelType = IdentifierModelType; //default, change later
00306   std::string method = this->params_->template get<std::string>("order_method", "rcm");
00307 
00308   if ((method == std::string("rcm")) || 
00309       (method == std::string("sorted_degree")) || 
00310       (method == std::string("minimum_degree"))) {
00311     modelType = GraphModelType;
00312   }
00313 
00314   // Select Model based on parameters and InputAdapter type
00315 
00316   std::bitset<NUM_MODEL_FLAGS> graphFlags;
00317   std::bitset<NUM_MODEL_FLAGS> idFlags;
00318 
00319   switch (modelType) {
00320 
00321   case GraphModelType:
00322     graphFlags.set(SELF_EDGES_MUST_BE_REMOVED);
00323     this->graphModel_ = rcp(new GraphModel<base_adapter_t>(
00324       this->baseInputAdapter_, this->envConst_, problemCommConst_, graphFlags));
00325 
00326     this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
00327       this->graphModel_);
00328 
00329     break;
00330 
00331 
00332 
00333   case IdentifierModelType:
00334     this->identifierModel_ = rcp(new IdentifierModel<base_adapter_t>(
00335       this->baseInputAdapter_, this->envConst_, problemCommConst_, idFlags));
00336 
00337     this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
00338       this->identifierModel_);
00339 
00340     break;
00341 
00342   case HypergraphModelType:
00343   case CoordinateModelType:
00344     cout << __func__ << " Model type " << modelType << " not yet supported." 
00345          << endl;
00346     break;
00347 
00348   default:
00349     cout << __func__ << " Invalid model" << modelType << endl;
00350     break;
00351   }
00352 }
00353 } //namespace Zoltan2
00354 #endif