Ifpack_GreedyPartitioner.cpp

00001 #include "Ifpack_ConfigDefs.h"
00002 #ifdef HAVE_IFPACK_TEUCHOS
00003 #include "Ifpack_Partitioner.h"
00004 #include "Ifpack_OverlappingPartitioner.h"
00005 #include "Ifpack_GreedyPartitioner.h"
00006 #include "Ifpack_Graph.h"
00007 
00008 #include "Epetra_Comm.h"
00009 #include "Epetra_BlockMap.h"
00010 #include "Epetra_Map.h"
00011 #include "Epetra_CrsGraph.h"
00012 #include "Teuchos_ParameterList.hpp"
00013 
00014 //==============================================================================
00015 int Ifpack_GreedyPartitioner::ComputePartitions()
00016 {
00017   vector<int> ElementsPerPart(NumLocalParts());
00018   vector<int> Count(NumLocalParts());
00019   for (int i = 0 ; i < NumLocalParts() ; ++i)
00020     Count[i] = 0;
00021 
00022   // define how many nodes have to be put on each part
00023   int div = NumMyRows() / NumLocalParts();
00024   int mod = NumMyRows() % NumLocalParts();
00025 
00026   for (int i = 0 ; i < NumLocalParts() ; ++i) {
00027     Count[i] = 0;
00028     ElementsPerPart[i] = div;
00029     if (i < mod) ElementsPerPart[i]++;
00030   }
00031 
00032   for( int i=0 ; i<NumMyRows() ; ++i ) {
00033     Partition_[i] = -1;
00034   }
00035 
00036   int NumEntries;
00037   vector<int> Indices(MaxNumEntries());
00038   
00039   // load root node for partition 0
00040   int CurrentPartition = 0;
00041   int TotalCount = 0;
00042 
00043   // filter singletons and empty rows, put all of them in partition 0
00044   for (int i = 0 ; i < NumMyRows() ; ++i) {
00045     int NumEntries = 0;
00046     int ierr = Graph_->ExtractMyRowCopy(i, MaxNumEntries(),
00047                                         NumEntries, &Indices[0]);
00048     IFPACK_CHK_ERR(ierr);
00049     if (NumEntries <= 1) {
00050       Partition_[i] = 0;
00051       TotalCount++;
00052     }
00053   }
00054 
00055   if (TotalCount)
00056     CurrentPartition = 1;
00057 
00058   vector<int> ThisLevel(1);
00059   ThisLevel[0] = RootNode_;
00060 
00061   // be sure that RootNode is not a singleton or empty row
00062   if (Partition_[RootNode_] != -1) {
00063     // look for another RN
00064     for (int i = 0 ; i < NumMyRows() ; ++i)
00065       if (Partition_[i] == -1) {
00066         ThisLevel[0] = i;
00067         break;
00068       }
00069   }
00070   else {
00071     Partition_[RootNode_] = CurrentPartition;
00072   }
00073 
00074   // now aggregate the non-empty and non-singleton rows
00075   while (ThisLevel.size()) {
00076 
00077     vector<int> NextLevel;
00078 
00079     for (unsigned int i = 0 ; i < ThisLevel.size() ; ++i) {
00080 
00081       int CurrentNode = ThisLevel[i];
00082       int ierr = Graph_->ExtractMyRowCopy(CurrentNode, MaxNumEntries(),
00083                                           NumEntries, &Indices[0]);
00084       IFPACK_CHK_ERR(ierr);
00085 
00086       if (NumEntries <= 1)
00087         continue;
00088 
00089       for (int j = 0 ; j < NumEntries ; ++j) {
00090 
00091         int NextNode = Indices[j];
00092         if (NextNode >= NumMyRows()) continue;
00093 
00094         if (Partition_[NextNode] == -1) {
00095           // this is a free node
00096           NumLocalParts_ = CurrentPartition + 1;
00097           Partition_[NextNode] = CurrentPartition;
00098           ++Count[CurrentPartition];
00099           ++TotalCount;
00100           NextLevel.push_back(NextNode);
00101         }
00102       }
00103     } // for (i)
00104 
00105     // check whether change partition or not
00106     if (Count[CurrentPartition] >= ElementsPerPart[CurrentPartition])
00107       ++CurrentPartition;
00108 
00109     // swap next and this
00110     ThisLevel.resize(0);
00111     for (unsigned int i = 0 ; i < NextLevel.size() ; ++i)
00112       ThisLevel.push_back(NextLevel[i]);
00113 
00114     if (ThisLevel.size() == 0 && (TotalCount != NumMyRows())) {
00115       // need to look for new RootNode, do this in a simple way
00116       for (int i = 0 ; i < NumMyRows() ; i++) {
00117         if (Partition_[i] == -1)
00118           ThisLevel.push_back(i);
00119         break;
00120       }
00121     }
00122 
00123   } // while (ok)
00124 
00125   return(0);
00126 }
00127 
00128 #endif // HAVE_IFPACK_TEUCHOS

Generated on Thu Sep 18 12:37:07 2008 for IFPACK by doxygen 1.3.9.1