Epetra Package Browser (Single Doxygen Collection) Development
Epetra_MapColoring.cpp
Go to the documentation of this file.
00001 
00002 //@HEADER
00003 // ************************************************************************
00004 // 
00005 //               Epetra: Linear Algebra Services Package 
00006 //                 Copyright 2011 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 Michael A. Heroux (maherou@sandia.gov) 
00039 // 
00040 // ************************************************************************
00041 //@HEADER
00042 
00043 #include "Epetra_ConfigDefs.h"
00044 #include "Epetra_HashTable.h"
00045 #include "Epetra_Comm.h"
00046 #include "Epetra_Map.h"
00047 #include "Epetra_MapColoring.h"
00048 #include "Epetra_Util.h"
00049 
00050 //=============================================================================
00051 Epetra_MapColoring::Epetra_MapColoring(const Epetra_BlockMap& map, int * elementColors, 
00052                const int defaultColor)
00053   : Epetra_DistObject(map, "Epetra::MapColoring"),
00054     DefaultColor_(defaultColor),
00055     ColorIDs_(0),
00056     FirstColor_(0),
00057     NumColors_(0),
00058     ListOfColors_(0),
00059     ColorCount_(0),
00060     ElementColors_(0),
00061     ColorLists_(0),
00062     Allocated_(false),
00063     ListsAreGenerated_(false),
00064     ListsAreValid_(false)
00065 {
00066   Allocate(elementColors, 1);
00067 }
00068 //=============================================================================
00069 Epetra_MapColoring::Epetra_MapColoring(const Epetra_BlockMap& map,
00070                const int defaultColor)
00071   : Epetra_DistObject(map, "Epetra::MapColoring"),
00072     DefaultColor_(defaultColor),
00073     ColorIDs_(0),
00074     FirstColor_(0),
00075     NumColors_(0),
00076     ListOfColors_(0),
00077     ColorCount_(0),
00078     ElementColors_(0),
00079     ColorLists_(0),
00080     Allocated_(false),
00081     ListsAreGenerated_(false),
00082     ListsAreValid_(false)
00083 {
00084   Allocate(&DefaultColor_, 0);
00085 }
00086 //=============================================================================
00087 Epetra_MapColoring::Epetra_MapColoring(const Epetra_MapColoring& Source)
00088   : Epetra_DistObject(Source),
00089     DefaultColor_(Source.DefaultColor_),
00090     ColorIDs_(0),
00091     FirstColor_(0),
00092     NumColors_(0),
00093     ListOfColors_(0),
00094     ColorCount_(0),
00095     ElementColors_(0),
00096     ColorLists_(0),
00097     Allocated_(false),
00098     ListsAreGenerated_(false),
00099     ListsAreValid_(false)
00100 {
00101   Allocate(Source.ElementColors_, 1);
00102 }
00103 //=========================================================================
00104 Epetra_MapColoring::~Epetra_MapColoring(){
00105 
00106 
00107   if (Allocated_ && Map().NumMyElements()>0) delete [] ElementColors_;
00108   if (ListsAreGenerated_) DeleteLists();
00109 }
00110 
00111 //=========================================================================
00112 int Epetra_MapColoring::DeleteLists() const {
00113 
00114 
00115   if (ListsAreGenerated_) {
00116     for (int i=0; i<NumColors_; i++) if (ColorLists_[i]!=0) delete [] ColorLists_[i];
00117     delete [] ColorLists_;
00118     delete [] ColorCount_;
00119     delete [] ListOfColors_;
00120     delete ColorIDs_;
00121     ListItem * CurItem = FirstColor_;
00122     while (CurItem!=0) {
00123       ListItem * NextItem = CurItem->NextItem;
00124       delete CurItem;
00125       CurItem = NextItem;
00126     }
00127   }
00128   ListsAreValid_ = false;
00129   return(0);
00130 }
00131 
00132 //=========================================================================
00133 int Epetra_MapColoring::Allocate(int * elementColors, int Increment)
00134 {
00135   
00136   if (Allocated_) return(0);
00137   
00138   int NumMyElements = Map().NumMyElements();
00139   if (NumMyElements>0) ElementColors_ = new int[NumMyElements];
00140   for (int i=0; i< NumMyElements; i++) ElementColors_[i] = elementColors[i*Increment];
00141   Allocated_ = true;
00142   return(0);
00143 }
00144 
00145 //=========================================================================
00146 int Epetra_MapColoring::GenerateLists() const {
00147   int NumMyElements = Map().NumMyElements();
00148   if (NumMyElements==0) return(0); // Nothing to do
00149 
00150   if (ListsAreValid_) return(0); // Already been here
00151 
00152   if (ListsAreGenerated_) DeleteLists();  // Delete any existing lists
00153 
00154 
00155   // Scan the ElementColors to determine how many colors we have
00156   NumColors_ = 1;
00157   FirstColor_ = new ListItem(ElementColors_[0]); // Initialize First color in list
00158   for (int i=1; i<NumMyElements; i++) if (!InItemList(ElementColors_[i])) NumColors_++;
00159 
00160   // Create hash table that maps color IDs to the integers 0,...NumColors_
00161   ColorIDs_ = new Epetra_HashTable<int>(NumColors_);
00162   ListOfColors_ = new int[NumColors_];
00163   ListItem * CurItem = FirstColor_;
00164   {for (int i=0; i<NumColors_; i++) {
00165     ColorIDs_->Add(CurItem->ItemValue, i); // Create hash table entry
00166     ListOfColors_[i] = CurItem->ItemValue; // Put color value in a list of colors
00167     CurItem = CurItem->NextItem;
00168   }}
00169   Epetra_Util util;
00170   util.Sort(true, NumColors_, ListOfColors_, 0, 0, 0, 0, 0, 0); // Sort List of colors in ascending order
00171   // Count the number of IDs of each color
00172   ColorCount_ = new int[NumColors_];
00173   {for (int i=0; i<NumColors_; i++) ColorCount_[i] = 0;}
00174   {for (int i=0; i<NumMyElements; i++) ColorCount_[ColorIDs_->Get(ElementColors_[i])]++;}
00175 
00176   // Finally build list of IDs grouped by color
00177   ColorLists_ = new int *[NumColors_];
00178   {for (int i=0; i<NumColors_; i++) ColorLists_[i] = new int[ColorCount_[i]];}
00179   {for (int i=0; i<NumColors_; i++) ColorCount_[i] = 0;} // Reset so we can use for counting
00180   {for (int i=0; i<NumMyElements; i++) {
00181     int j = ColorIDs_->Get(ElementColors_[i]);
00182     ColorLists_[j][ColorCount_[j]++] = i;
00183   }}
00184   ListsAreValid_ = true;
00185   ListsAreGenerated_ = true;
00186 
00187   return(0);
00188 }
00189 //=========================================================================
00190 bool Epetra_MapColoring::InItemList(int ColorValue) const {
00191   bool ColorFound = false;
00192   ListItem * CurColor = 0;
00193   ListItem * NextColor = FirstColor_;
00194   while (!ColorFound && NextColor!=0) {
00195     CurColor = NextColor;
00196     NextColor = CurColor->NextItem;
00197     if (ColorValue==CurColor->ItemValue) ColorFound = true;
00198   }
00199 
00200   if (!ColorFound) CurColor->NextItem = new ListItem(ColorValue);
00201 
00202   return(ColorFound);
00203 }
00204 //=========================================================================
00205 int Epetra_MapColoring::NumElementsWithColor(int Color) const  {
00206   if (!ListsAreValid_) GenerateLists(); 
00207   int arrayIndex = -1;
00208   if( ColorIDs_ )
00209     arrayIndex = ColorIDs_->Get(Color);
00210   if (arrayIndex>-1) return(ColorCount_[arrayIndex]);
00211   else return(0);
00212 }
00213 //=========================================================================
00214 int * Epetra_MapColoring::ColorLIDList(int Color) const  {
00215   if (!ListsAreValid_) GenerateLists(); 
00216   int arrayIndex = -1;
00217   if( ColorIDs_ )
00218     arrayIndex = ColorIDs_->Get(Color);
00219   if (arrayIndex>-1) return(ColorLists_[arrayIndex]);
00220   else return(0);
00221 }
00222 //=========================================================================
00223 template<typename int_type>
00224 Epetra_Map * Epetra_MapColoring::TGenerateMap(int Color) const {
00225 
00226   if (!ListsAreValid_) GenerateLists(); 
00227   int arrayIndex = -1;
00228   if( ColorIDs_ )
00229     arrayIndex = ColorIDs_->Get(Color);
00230   int NumElements = 0;
00231   int * ColorElementLIDs = 0;
00232   int_type * ColorElementGIDs =0;
00233   if (arrayIndex>-1) NumElements = ColorCount_[arrayIndex];
00234   if (NumElements>0) {
00235     ColorElementLIDs = ColorLIDList(Color);
00236     ColorElementGIDs = new int_type[NumElements];
00237     for (int i=0; i<NumElements; i++) ColorElementGIDs[i] = (int_type) Map().GID64(ColorElementLIDs[i]);
00238   }
00239   Epetra_Map * map = new Epetra_Map((int_type) -1, NumElements, ColorElementGIDs,
00240             (int_type) Map().IndexBase64(), Map().Comm());
00241   if (ColorElementGIDs!=0) delete [] ColorElementGIDs;
00242   return(map);
00243 }
00244 
00245 Epetra_Map * Epetra_MapColoring::GenerateMap(int Color) const {
00246 #ifndef EPETRA_NO_32BIT_GLOBAL_INDICES
00247   if(Map().GlobalIndicesInt()) {
00248     return TGenerateMap<int>(Color);
00249   }
00250   else
00251 #endif
00252 #ifndef EPETRA_NO_64BIT_GLOBAL_INDICES
00253   if(Map().GlobalIndicesLongLong()) {
00254     return TGenerateMap<long long>(Color);
00255   }
00256   else
00257 #endif
00258     throw "Epetra_MapColoring::GenerateMap: GlobalIndices type unknown";
00259 }
00260 
00261 //=========================================================================
00262 template<typename int_type>
00263 Epetra_BlockMap * Epetra_MapColoring::TGenerateBlockMap(int Color) const {
00264 
00265   if (!ListsAreValid_) GenerateLists(); 
00266   int arrayIndex = -1;
00267   if( ColorIDs_ )
00268     arrayIndex = ColorIDs_->Get(Color);
00269   int NumElements = 0;
00270   int * ColorElementLIDs = 0;
00271   int * ColorElementSizes = 0;
00272   int_type * ColorElementGIDs = 0;
00273   if (arrayIndex>-1) NumElements = ColorCount_[arrayIndex];
00274   if (NumElements>0) {
00275     ColorElementLIDs = ColorLIDList(Color);
00276     ColorElementSizes = new int[NumElements];
00277     ColorElementGIDs = new int_type[NumElements];
00278     for (int i=0; i<NumElements; i++) ColorElementGIDs[i] = (int_type) Map().GID64(ColorElementLIDs[i]);
00279   }
00280   int * MapElementSizes = Map().ElementSizeList();
00281 
00282   {for (int i=0; i<NumElements; i++) 
00283     ColorElementSizes[i] = MapElementSizes[ColorElementLIDs[i]];}
00284 
00285   Epetra_BlockMap * map = new Epetra_BlockMap((int_type) -1, NumElements, ColorElementGIDs,
00286                 ColorElementSizes,
00287                 (int_type) Map().IndexBase64(), Map().Comm());
00288 
00289   if (ColorElementGIDs!=0) delete [] ColorElementGIDs;
00290   if (ColorElementSizes!=0) delete [] ColorElementSizes;
00291 
00292   return(map);
00293 }
00294 
00295 Epetra_BlockMap * Epetra_MapColoring::GenerateBlockMap(int Color) const {
00296 #ifndef EPETRA_NO_32BIT_GLOBAL_INDICES
00297   if(Map().GlobalIndicesInt()) {
00298     return TGenerateBlockMap<int>(Color);
00299   }
00300   else
00301 #endif
00302 #ifndef EPETRA_NO_64BIT_GLOBAL_INDICES
00303   if(Map().GlobalIndicesLongLong()) {
00304     return TGenerateBlockMap<long long>(Color);
00305   }
00306   else
00307 #endif
00308     throw "Epetra_MapColoring::GenerateBlockMap: GlobalIndices type unknown";
00309 }
00310 
00311 //=========================================================================
00312 void Epetra_MapColoring::Print(std::ostream& os) const {
00313   int MyPID = Map().Comm().MyPID();
00314   int NumProc = Map().Comm().NumProc();
00315   
00316   if (MyPID==0) os 
00317     << std::endl 
00318     << " *****************************************" << std::endl
00319     << " Coloring information arranged map element" << std::endl 
00320     << " *****************************************" << std::endl
00321     << std::endl;
00322   for (int iproc=0; iproc < NumProc; iproc++) {
00323     if (MyPID==iproc) {
00324       int NumMyElements1 =Map(). NumMyElements();
00325 
00326       if (MyPID==0) {
00327   os.width(8);
00328   os <<  "     MyPID"; os << "    ";
00329   os.width(12);
00330   os <<  "GID  ";
00331   os.width(20);
00332   os <<  "Color  ";
00333   os << std::endl;
00334       }
00335       for (int i=0; i < NumMyElements1; i++) {
00336   os.width(10);
00337   os <<  MyPID; os << "    ";
00338   os.width(10);
00339 
00340     if(Map().GlobalIndicesInt()) {
00341 #ifndef EPETRA_NO_32BIT_GLOBAL_INDICES
00342         int * MyGlobalElements1 = Map().MyGlobalElements();
00343         os << MyGlobalElements1[i] << "    ";
00344 #else
00345         throw ReportError("Epetra_MapColoring::Print: ERROR, GlobalIndicesInt but no API for it.",-1);
00346 #endif
00347     }
00348     else if(Map().GlobalIndicesLongLong())
00349     {
00350 #ifndef EPETRA_NO_64BIT_GLOBAL_INDICES
00351     long long * MyGlobalElements1 = Map().MyGlobalElements64();
00352     os << MyGlobalElements1[i] << "    ";
00353 #else
00354         throw ReportError("Epetra_MapColoring::Print: ERROR, GlobalIndicesLongLong but no API for it.",-1);
00355 #endif
00356     }
00357     else
00358     throw ReportError("Epetra_MapColoring::Print: ERROR, Don't know map global index type.",-1);
00359 
00360   os.width(20);
00361   os <<  ElementColors_[i];
00362   os << std::endl;
00363       }
00364       os << std::flush; 
00365     }
00366 
00367     // Do a few global ops to give I/O a chance to complete
00368     Map().Comm().Barrier();
00369     Map().Comm().Barrier();
00370     Map().Comm().Barrier();
00371   }
00372 
00373   if (MyPID==0) os 
00374     << std::endl 
00375     << " **************************************" << std::endl
00376     << " Coloring information arranged by color" << std::endl 
00377     << " **************************************" << std::endl
00378     << std::endl;
00379   {for (int iproc=0; iproc < NumProc; iproc++) {
00380     if (MyPID==iproc) {
00381       if (NumColors()==0) os << " No colored elements on processor " << MyPID << std::endl;
00382       else {
00383         os << "Number of colors in map = " << NumColors() << std::endl
00384            << "Default color           = " << DefaultColor() << std::endl << std::endl;
00385         if (MyPID==0) {
00386           os.width(8);
00387           os <<  "     MyPID"; os << "    ";
00388           os.width(12);
00389           os <<  "LID  ";
00390           os.width(20);
00391           os <<  "Color  ";
00392           os << std::endl;
00393         }
00394         int * ColorValues = ListOfColors();
00395         for (int ii=0; ii<NumColors(); ii++) {
00396           int CV = ColorValues[ii];
00397     int ColorCount = NumElementsWithColor(CV);
00398     int * LIDList = ColorLIDList(CV);
00399     
00400     
00401     for (int i=0; i < ColorCount; i++) {
00402       os.width(10);
00403       os <<  MyPID; os << "    ";
00404       os.width(10);
00405       os << LIDList[i] << "    ";
00406       os.width(20);
00407       os << CV;
00408       os << std::endl;
00409     }
00410     os << std::flush; 
00411   }
00412       }
00413     }
00414     // Do a few global ops to give I/O a chance to complete
00415     Map().Comm().Barrier();
00416     Map().Comm().Barrier();
00417     Map().Comm().Barrier();
00418   }}
00419   return;
00420 }
00421 //=========================================================================
00422 int Epetra_MapColoring::MaxNumColors() const {
00423 
00424   if (!ListsAreValid_) GenerateLists(); 
00425   int tmp1 = NumColors_, tmp2;
00426   Map().Comm().MaxAll(&tmp1, &tmp2, 1);
00427   return(tmp2);
00428 }
00429 //=========================================================================
00430 int Epetra_MapColoring::CheckSizes(const Epetra_SrcDistObject& Source) {
00431   (void)Source;//prevents unused variable compiler warning
00432   return(0);
00433 }
00434 
00435 //=========================================================================
00436 int Epetra_MapColoring::CopyAndPermute(const Epetra_SrcDistObject& Source,
00437                                        int NumSameIDs, 
00438                int NumPermuteIDs,
00439                                        int * PermuteToLIDs, 
00440                int *PermuteFromLIDs,
00441                                        const Epetra_OffsetIndex * Indexor)
00442 {
00443   (void)Indexor;
00444   const Epetra_MapColoring & A = dynamic_cast<const Epetra_MapColoring &>(Source);
00445 
00446   int * From = A.ElementColors();
00447   int *To = ElementColors_;
00448 
00449   // Do copy first
00450   if (NumSameIDs>0)
00451     if (To!=From) {
00452       for (int j=0; j<NumSameIDs; j++)
00453   To[j] = From[j];
00454     }
00455   // Do local permutation next
00456   if (NumPermuteIDs>0)
00457     for (int j=0; j<NumPermuteIDs; j++) 
00458       To[PermuteToLIDs[j]] = From[PermuteFromLIDs[j]];
00459   
00460   return(0);
00461 }
00462 
00463 //=========================================================================
00464 int Epetra_MapColoring::PackAndPrepare(const Epetra_SrcDistObject & Source,
00465                                        int NumExportIDs,
00466                                        int * ExportLIDs,
00467                int & LenExports,
00468                                        char * & Exports,
00469                int & SizeOfPacket,
00470                int * Sizes,
00471                bool & VarSizes,
00472                                        Epetra_Distributor & Distor)
00473 {
00474   (void)Sizes;
00475   (void)VarSizes;
00476   (void)Distor;
00477   const Epetra_MapColoring & A = dynamic_cast<const Epetra_MapColoring &>(Source);
00478 
00479   int  * From = A.ElementColors();
00480   int * IntExports = 0;
00481 
00482   SizeOfPacket = (int)sizeof(int); 
00483 
00484   if (NumExportIDs*SizeOfPacket>LenExports) {
00485     if (LenExports>0) delete [] Exports;
00486     LenExports = NumExportIDs*SizeOfPacket;
00487     IntExports = new int[LenExports];
00488     Exports = (char *) IntExports;
00489   }
00490 
00491   int * ptr;
00492 
00493   if (NumExportIDs>0) {
00494     ptr = (int *) Exports;    
00495     for (int j=0; j<NumExportIDs; j++) ptr[j] = From[ExportLIDs[j]];
00496   }
00497   
00498   return(0);
00499 }
00500 
00501 //=========================================================================
00502 int Epetra_MapColoring::UnpackAndCombine(const Epetra_SrcDistObject & Source,
00503            int NumImportIDs,
00504                                          int * ImportLIDs, 
00505                                          int LenImports,
00506            char * Imports,
00507                                          int & SizeOfPacket, 
00508            Epetra_Distributor & Distor, 
00509            Epetra_CombineMode CombineMode,
00510                                          const Epetra_OffsetIndex * Indexor )
00511 {
00512   (void)Source;
00513   (void)LenImports;
00514   (void)Imports;
00515   (void)SizeOfPacket;
00516   (void)Distor;
00517   (void)Indexor;
00518   int j;
00519   
00520   if(    CombineMode != Add
00521       && CombineMode != Zero
00522       && CombineMode != Insert
00523       && CombineMode != AbsMax )
00524     EPETRA_CHK_ERR(-1); //Unsupported CombinedMode, will default to Zero
00525 
00526   if (NumImportIDs<=0) return(0);
00527 
00528   int * To = ElementColors_;
00529 
00530   int * ptr;
00531   // Unpack it...
00532 
00533   ptr = (int *) Imports;
00534     
00535   if (CombineMode==Add)
00536     for (j=0; j<NumImportIDs; j++) To[ImportLIDs[j]] += ptr[j]; // Add to existing value
00537   else if(CombineMode==Insert)
00538     for (j=0; j<NumImportIDs; j++) To[ImportLIDs[j]] = ptr[j];
00539   else if(CombineMode==AbsMax) {
00540     for (j=0; j<NumImportIDs; j++) To[ImportLIDs[j]] = 0;
00541     for (j=0; j<NumImportIDs; j++)  To[ImportLIDs[j]] = EPETRA_MAX( To[ImportLIDs[j]],std::abs(ptr[j]));
00542   }
00543   
00544   return(0);
00545 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines