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