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::gid_t gid_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<gid_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<gid_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<gid_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;
00205       alg.order(this->graphModel_, this->solution_, this->params_, problemComm_);
00206   }
00207   else if (method.compare("natural") == 0)
00208   {
00209       AlgNatural<base_adapter_t> alg;
00210       alg.order(this->identifierModel_, this->solution_, this->params_, problemComm_);
00211   }
00212   else if (method.compare("random") == 0)
00213   {
00214       AlgRandom<base_adapter_t> alg;
00215       alg.order(this->identifierModel_, this->solution_, this->params_, problemComm_);
00216   }
00217   else if (method.compare("sorted_degree") == 0)
00218   {
00219       AlgSortedDegree<base_adapter_t> alg;
00220       alg.order(this->graphModel_, this->solution_, this->params_, problemComm_);
00221   }
00222   else if (method.compare("minimum_degree") == 0)
00223   {
00224       std::string pkg = this->params_->template get<std::string>("order_package", "amd");
00225       if (pkg.compare("amd") == 0)
00226       {
00227           AlgAMD<base_adapter_t> alg;
00228           alg.order (this->graphModel_, this->solution_, this->params_,
00229                           problemComm_);
00230       }
00231   }
00232   }
00233   Z2_FORWARD_EXCEPTIONS;
00234 
00235 #ifdef HAVE_ZOLTAN2_MPI
00236 
00237   // The algorithm may have changed the communicator.  Change it back.
00238 
00239   RCP<const mpiWrapper_t > wrappedComm = rcp(new mpiWrapper_t(mpiComm_));
00240   problemComm_ = rcp(new Teuchos::MpiComm<int>(wrappedComm));
00241   problemCommConst_ = rcp_const_cast<const Comm<int> > (problemComm_);
00242 
00243 #endif
00244 
00245 }
00246 
00248 //template <typename Adapter>
00249 //void OrderingProblem<Adapter>::redistribute()
00250 //{
00251 //  HELLO;
00252 //}
00253 
00256 //  Method with common functionality for creating a OrderingProblem.
00257 //  Individual constructors do appropriate conversions of input, etc.
00258 //  This method does everything that all constructors must do.
00259 
00260 template <typename Adapter>
00261 void OrderingProblem<Adapter>::createOrderingProblem()
00262 {
00263   HELLO;
00264   using Teuchos::ParameterList;
00265 
00266 //  cout << __func__ << " input adapter type " 
00267 //       << this->inputAdapter_->inputAdapterType() << " " 
00268 //       << this->inputAdapter_->inputAdapterName() << endl;
00269 
00270 #ifdef HAVE_ZOLTAN2_OVIS
00271   ovis_enabled(this->comm_->getRank());
00272 #endif
00273 
00274   // Create a copy of the user's communicator.
00275 
00276   problemComm_ = this->comm_->duplicate();
00277   problemCommConst_ = rcp_const_cast<const Comm<int> > (problemComm_);
00278 
00279 
00280 #ifdef HAVE_ZOLTAN2_MPI
00281 
00282   // TPLs may want an MPI communicator
00283 
00284   Comm<int> *c = problemComm_.getRawPtr();
00285   Teuchos::MpiComm<int> *mc = dynamic_cast<Teuchos::MpiComm<int> *>(c);
00286   if (mc){
00287     RCP<const mpiWrapper_t> wrappedComm = mc->getRawMpiComm();
00288     mpiComm_ = (*wrappedComm.getRawPtr())();
00289   }
00290   else{
00291     mpiComm_ = MPI_COMM_SELF;   // or would this be an error?
00292   }
00293 
00294 #endif
00295 
00296   // Determine which parameters are relevant here.
00297   // For now, assume parameters similar to Zoltan:
00298   //   MODEL = graph, hypergraph, geometric, ids
00299   //   ALGORITHM = rcm, random, amd
00300 
00301   ModelType modelType = IdentifierModelType; //default, change later
00302   std::string method = this->params_->template get<std::string>("order_method", "rcm");
00303 
00304   if ((method == std::string("rcm")) || 
00305       (method == std::string("sorted_degree")) || 
00306       (method == std::string("minimum_degree"))) {
00307     modelType = GraphModelType;
00308   }
00309 
00310   // Select Model based on parameters and InputAdapter type
00311 
00312   std::bitset<NUM_MODEL_FLAGS> graphFlags;
00313   std::bitset<NUM_MODEL_FLAGS> idFlags;
00314 
00315   switch (modelType) {
00316 
00317   case GraphModelType:
00318     graphFlags.set(SELF_EDGES_MUST_BE_REMOVED);
00319     this->graphModel_ = rcp(new GraphModel<base_adapter_t>(
00320       this->baseInputAdapter_, this->envConst_, problemCommConst_, graphFlags));
00321 
00322     this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
00323       this->graphModel_);
00324 
00325     break;
00326 
00327 
00328 
00329   case IdentifierModelType:
00330     this->identifierModel_ = rcp(new IdentifierModel<base_adapter_t>(
00331       this->baseInputAdapter_, this->envConst_, problemCommConst_, idFlags));
00332 
00333     this->baseModel_ = rcp_implicit_cast<const Model<base_adapter_t> >(
00334       this->identifierModel_);
00335 
00336     break;
00337 
00338   case HypergraphModelType:
00339   case CoordinateModelType:
00340     cout << __func__ << " Model type " << modelType << " not yet supported." 
00341          << endl;
00342     break;
00343 
00344   default:
00345     cout << __func__ << " Invalid model" << modelType << endl;
00346     break;
00347   }
00348 }
00349 } //namespace Zoltan2
00350 #endif