My title

00001 /* ****************************************************************** **
00002 **    OpenSees - Open System for Earthquake Engineering Simulation    **
00003 **          Pacific Earthquake Engineering Research Center            **
00004 **                                                                    **
00005 **                                                                    **
00006 ** (C) Copyright 1999, The Regents of the University of California    **
00007 ** All Rights Reserved.                                               **
00008 **                                                                    **
00009 ** Commercial use of this program without express permission of the   **
00010 ** University of California, Berkeley, is strictly prohibited.  See   **
00011 ** file 'COPYRIGHT'  in main directory for information on usage and   **
00012 ** redistribution,  and for a DISCLAIMER OF ALL WARRANTIES.           **
00013 **                                                                    **
00014 ** Developed by:                                                      **
00015 **   Frank McKenna (fmckenna@ce.berkeley.edu)                         **
00016 **   Gregory L. Fenves (fenves@ce.berkeley.edu)                       **
00017 **   Filip C. Filippou (filippou@ce.berkeley.edu)                     **
00018 **                                                                    **
00019 ** ****************************************************************** */
00020                                                                         
00021 // $Revision: 1.1.1.1 $
00022 // $Date: 2000/09/15 08:23:21 $
00023 // $Source: /usr/local/cvs/OpenSees/SRC/graph/partitioner/Metis.cpp,v $
00024                                                                         
00025                                                                         
00026 // File: ~/graph/partitioner/Metis.C
00027 // 
00028 // Written: fmk 
00029 // Created: Sun Sept 15 11:47:47: 1996
00030 // Revision: A
00031 //
00032 // Description: This file contains the class definition for Metis.
00033 // Metis is a type of GraphPartitioner which uses 'METIS - Unstructured
00034 // Graph Partitioning And Sparse Matrix Ordering System', developed by
00035 // G. Karypis and V. Kumar at the University of Minnesota. The metis
00036 // files are found in metis-2.0 which were downloaded.
00037 //     This class provides the C++ interface for metis which will allow
00038 // it to fit seamlessly into our system.
00039 //
00040 // What: "@(#) Metis.C, revA"
00041 
00042 #include <Metis.h>
00043 #include <Graph.h>
00044 #include <Vertex.h>
00045 
00046 /* stuff needed to get the program working on the clump & NOW machines*/
00047 #include <bool.h>
00048 #ifdef _LINUX
00049 extern "C" {
00050 #include <GKlib.h>
00051 }
00052 
00053 int IsWeighted;
00054 timer TotalTmr;         /* Times the entire algorithm */
00055 timer CoarsenTmr;       /* Times total coarsening time */
00056 timer GreedyTmr;        /* Times Total Greedy Time */
00057 timer GreedyInitTmr;    /* Times initialization cost of Greedy */
00058 timer GreedyIterTmr;    /* Times Iterative cost of Greedy */
00059 timer GreedyWrapUpTmr;  /* Times the wrap up phase of Greedy */
00060 timer MlevelTmr;        /* Times the entire multilevel algorithm */
00061 timer InitPartTmr;      /* Times the initial partition phase */
00062 timer ProjectTmr;       /* Times the projection of the partition */
00063 timer SplitTmr;         /* Times the boundary creation */
00064 timer BalanceTmr;       /* Times the time required for balancing */
00065 timer IOTmr;            /* Times the file input time */
00066 timer UncrsTmr;         /* Times the file input time */
00067 #endif
00068 
00069 extern "C" 
00070 int PMETIS(int *, int *, int *, int *, int *, int *, int *, int *, int *, int *, int *);
00071 
00072 extern "C" 
00073 int KMETIS(int *, int *, int *, int *, int *, int *, int *, int *, int *, int *, int *);
00074 
00075 
00076 Metis::Metis(int numParts) 
00077 :GraphNumberer(GraphNUMBERER_TAG_Metis),
00078  myPtype(0), myMtype(0), myCoarsenTo(0), myRtype(0), myIPtype(0),
00079  defaultOptions(true), numPartitions(numParts), theRefResult(0)
00080 {
00081     
00082 }
00083 
00084 Metis::Metis(int Ptype, 
00085    int Mtype, 
00086    int coarsenTo,
00087    int Rtype, 
00088          int IPtype,
00089    int numParts)
00090 :GraphNumberer(GraphNUMBERER_TAG_Metis),
00091  myPtype(Ptype), myMtype(Mtype), myCoarsenTo(coarsenTo), myRtype(Rtype), 
00092  myIPtype(IPtype), defaultOptions(false), numPartitions(numParts), theRefResult(0)
00093 {
00094     // check the options are valid
00095     checkOptions();
00096 }    
00097 
00098     
00099 Metis::~Metis() 
00100 {
00101 
00102 }    
00103 
00104 bool
00105 Metis::setOptions(int Ptype, 
00106     int Mtype,
00107     int coarsenTo,
00108     int Rtype, 
00109     int IPtype)
00110 {
00111     myPtype=Ptype; 
00112     myMtype = Mtype; 
00113     myCoarsenTo = coarsenTo; 
00114     myRtype = Rtype; 
00115     myIPtype = IPtype; 
00116 
00117     defaultOptions = false;
00118     
00119     return checkOptions();
00120     
00121 }    
00122 
00123 
00124 // bool checkOptions(void) const
00125 // returns true if options are o.k., false otherwise
00126 
00127 bool
00128 Metis::checkOptions(void) 
00129 {
00130 
00131     // check default not set
00132     
00133     if (defaultOptions == true)
00134  return true;
00135 
00136     
00137     // otherwise check all options for valid value
00138     bool okFlag = true;    
00139     
00140     if ((myPtype != 1) || (myPtype != 2)) {
00141  okFlag = false;
00142  cerr << "WARNING: Metis::partition ";
00143  cerr << " - Illegal Ptype " << myPtype << endl;
00144     }
00145  
00146     if ((myMtype != 1) ||  (myMtype != 2) || (myMtype != 3) || 
00147  ((myMtype != 4) || (myMtype != 5) || myMtype != 11) || 
00148  (myMtype != 21) || (myMtype != 51)) {
00149  okFlag = false;
00150  cerr << "WARNING: Metis::partition ";
00151  cerr << " - Illegal Mtype " << myMtype << endl;
00152     }
00153 
00154     if (myPtype == 1)  
00155  if ((myRtype != 1) || (myRtype != 2) || (myRtype != 3) ||
00156      (myRtype != 11) || (myRtype != 12) || (myRtype != 13) ||
00157      (myRtype != 20)) {
00158      okFlag = false;
00159      cerr << "WARNING: Metis::partition ";
00160      cerr << " - Illegal Rtype " << myRtype << endl;
00161      cerr << " for Ptype " << myPtype << endl;     
00162  }
00163     else 
00164  if (myPtype == 2)
00165      if ((myRtype != 11) || (myRtype != 12) || (myRtype != 20)) {
00166   okFlag = false;
00167   cerr << "WARNING: Metis::partition ";
00168   cerr << " - Illegal Rtype " << myRtype << endl;
00169   cerr << " for Ptype " << myPtype << endl;     
00170      }
00171     
00172     if ((myIPtype != 1) || (myIPtype != 2) || (myIPtype != 3) || 
00173  (myIPtype != 4)) {
00174  okFlag = false;
00175  cerr << "WARNING: Metis::partition ";
00176  cerr << " - Illegal IPtype " << myIPtype << endl;
00177     }     
00178  
00179     if (myCoarsenTo < 0) {
00180  okFlag = false;
00181  cerr << "WARNING: Metis::partition ";
00182  cerr << " - Illegal coarsen To " << myCoarsenTo << endl;
00183     }     
00184 
00185     if (okFlag == false)
00186  defaultOptions = true;
00187     
00188     return okFlag;
00189 
00190 }
00191 
00192 
00193 bool 
00194 Metis::setDefaultOptions(void)
00195 {
00196     defaultOptions = true;
00197     return true;
00198 }
00199 
00200 
00201 // int partition(Graph &theGraph, int numPart)
00202 // Method to partition the graph. It first creates the arrays needed
00203 // by the metis lib and then invokes a function from the metis lib to
00204 // partition the graph. The solors of the vertices of the graph are
00205 // set to colors 0 through numPart-1 to indicate which partition the
00206 // vrtices are in. Returns -1 if options are not set, -2 if metis failed.
00207 
00208 int
00209 Metis::partition(Graph &theGraph, int numPart)
00210 {
00211     // first we check that the options are valid
00212     if (checkOptions() == false)
00213  return -1;
00214     
00215     // now we get room for the data structures metis needs
00216 
00217     int numVertex = theGraph.getNumVertex();
00218     int numEdge = theGraph.getNumEdge();
00219 
00220     int *options = new int [5];
00221     int *partition = new int [numVertex+1];    
00222     int *xadj = new int [numVertex+2];
00223     int *adjncy = new int [2*numEdge];
00224     int *vwgts = 0;
00225     int *ewgts = 0;
00226     int numbering = 0;
00227     int weightflag = 0; // no weights on our graphs yet
00228 
00229     if (START_VERTEX_NUM == 0)
00230  numbering = 0; 
00231     else if (START_VERTEX_NUM == 1)
00232  numbering = 1;
00233     else {
00234  cerr << "WARNING Metis::partition - No partitioning done";
00235  cerr << " vertex numbering must start at 0 or 1\n";
00236  return (-2);
00237     }
00238     int edgecut;
00239     
00240     if ((options == 0) || (partition == 0) || (xadj == 0) || (adjncy == 0)) {
00241  cerr << "WARNING Metis::partition - No partitioning done";
00242  cerr << " as ran out of memory\n";
00243  return (-2);
00244     }
00245 
00246 
00247     // we build these data structures
00248     
00249     int indexEdge = 0;
00250     xadj[0] = 0;
00251 
00252     Vertex *vertexPtr;
00253     for (int vertex =0; vertex<numVertex; vertex++) {
00254  vertexPtr = theGraph.getVertexPtr(vertex+START_VERTEX_NUM);
00255  
00256  // check we don't have an invalid vertex numbering scheme
00257  // if so WARNING message, clean up and return -2
00258 
00259  if (vertexPtr == 0) {
00260      cerr << "WARNING Metis::partition - No partitioning done";
00261      cerr << " Metis requires consequtive Vertex Numbering\n";
00262      
00263      delete [] options;
00264      delete [] partition;
00265      delete [] xadj;
00266      delete [] adjncy;
00267      
00268      return -2;
00269  }
00270  
00271  const ID&adjacency = vertexPtr->getAdjacency();
00272  int degree = adjacency.Size();
00273  for (int i=0; i<degree; i++) {
00274      adjncy[indexEdge++] = adjacency(i)-START_VERTEX_NUM;
00275  }
00276  
00277  xadj[vertex+1] = indexEdge;
00278     }
00279 
00280 
00281     if (defaultOptions == true) 
00282  options[0] = 0;
00283     else {
00284  options[0] =1;
00285  options[1] = myCoarsenTo;
00286  options[2] = myMtype;
00287  options[3] = myIPtype;
00288  options[4] = myRtype;
00289     }
00290     
00291     
00292     // we now the metis routines
00293 
00294     if (myPtype == 1)
00295  PMETIS(&numVertex, xadj, adjncy, vwgts, ewgts, &weightflag, &numPart,
00296         options, &numbering, &edgecut, partition);
00297     else  
00298  KMETIS(&numVertex, xadj, adjncy, vwgts, ewgts, &weightflag, &numPart,
00299         options, &numbering, &edgecut, partition);
00300 
00301 
00302     // we set the vertex colors to correspond to the partitioned scheme
00303     for (int vert =0; vert<numVertex; vert++) {
00304  vertexPtr = theGraph.getVertexPtr(vert+START_VERTEX_NUM);
00305  vertexPtr->setColor(partition[vert]+1); // start colors at 1
00306     }
00307 
00308     // clean up the space and return
00309     
00310     delete [] options;
00311     delete [] partition;
00312     delete [] xadj;
00313     delete [] adjncy;
00314     
00315     return 0;
00316 }
00317 
00318 
00319 
00320 
00321 
00322 
00323 const ID &
00324 Metis::number(Graph &theGraph, int lastVertex)
00325 {
00326     // first we check that the options are valid
00327     // first check our size, if not same make new
00328     int numVertex = theGraph.getNumVertex();
00329     // delete the old
00330     if (theRefResult != 0)
00331       delete theRefResult;
00332  
00333     theRefResult = new ID(numVertex);
00334 
00335     if (theRefResult == 0) {
00336       cerr << "ERROR:  Metis::number - Out of Memory\n";
00337       theRefResult = new ID(0);
00338       return *theRefResult;
00339     }
00340 
00341     if (checkOptions() == false) {
00342       cerr << "ERROR:  Metis::number - chek options failed\n";
00343       return *theRefResult;
00344     }
00345     
00346     // now we get room for the data structures metis needs
00347     int numEdge = theGraph.getNumEdge();
00348 
00349     int *options = new int [5];
00350     int *partition = new int [numVertex+1];    
00351     int *xadj = new int [numVertex+2];
00352     int *adjncy = new int [2*numEdge];
00353     int *vwgts = 0;
00354     int *ewgts = 0;
00355     int numbering = 0;
00356     int weightflag = 0; // no weights on our graphs yet
00357 
00358     if (START_VERTEX_NUM == 0)
00359  numbering = 0; 
00360     else if (START_VERTEX_NUM == 1)
00361  numbering = 1;
00362     else {
00363  cerr << "WARNING Metis::partition - No partitioning done";
00364  cerr << " vertex numbering must start at 0 or 1\n";
00365  return *theRefResult;
00366     }
00367     int edgecut;
00368     
00369     if ((options == 0) || (partition == 0) || (xadj == 0) || (adjncy == 0)) {
00370  cerr << "WARNING Metis::partition - No partitioning done";
00371  cerr << " as ran out of memory\n";
00372  return *theRefResult;
00373     }
00374 
00375 
00376     // we build these data structures
00377     
00378     int indexEdge = 0;
00379     xadj[0] = 0;
00380 
00381     Vertex *vertexPtr;
00382     for (int vertex =0; vertex<numVertex; vertex++) {
00383  vertexPtr = theGraph.getVertexPtr(vertex+START_VERTEX_NUM);
00384  
00385  // check we don't have an invalid vertex numbering scheme
00386  // if so WARNING message, clean up and return -2
00387 
00388  if (vertexPtr == 0) {
00389      cerr << "WARNING Metis::partition - No partitioning done";
00390      cerr << " Metis requires consequtive Vertex Numbering\n";
00391      
00392      delete [] options;
00393      delete [] partition;
00394      delete [] xadj;
00395      delete [] adjncy;
00396      
00397      return *theRefResult;
00398  }
00399  
00400  const ID&adjacency = vertexPtr->getAdjacency();
00401  int degree = adjacency.Size();
00402  for (int i=0; i<degree; i++) {
00403      adjncy[indexEdge++] = adjacency(i)-START_VERTEX_NUM;
00404  }
00405  
00406  xadj[vertex+1] = indexEdge;
00407     }
00408 
00409 
00410     if (defaultOptions == true) 
00411  options[0] = 0;
00412     else {
00413  options[0] =1;
00414  options[1] = myCoarsenTo;
00415  options[2] = myMtype;
00416  options[3] = myIPtype;
00417  options[4] = myRtype;
00418     }
00419     
00420     
00421     // we now the metis routines
00422 
00423     if (myPtype == 1)
00424 
00425       PMETIS(&numVertex, xadj, adjncy, vwgts, ewgts, &weightflag, 
00426       &numPartitions, options, &numbering, &edgecut, partition);
00427     else  
00428       KMETIS(&numVertex, xadj, adjncy, vwgts, ewgts, &weightflag, 
00429       &numPartitions, options, &numbering, &edgecut, partition);
00430 
00431 cerr << "Metis::number -2\n";
00432     // we assign numbers now based on the partitions returned.
00433     // each vertex in partion i is assigned a number less than
00434     // thos in partion i+1: NOTE WE DON'T CARE WHAT THE NUMBERING IS
00435     // WITHIN A PARTITION
00436     int count = 0;
00437     for (int i=0; i<numPartitions; i++) {
00438       for (int vert=0; vert<numVertex; vert++) {
00439  if (partition[vert] == i) {
00440    vertexPtr = theGraph.getVertexPtr(vert+START_VERTEX_NUM);
00441    vertexPtr->setTmp(count+1);
00442    (*theRefResult)(count) = vertexPtr->getRef();
00443    count++;
00444  }
00445       }
00446     }
00447 cerr << "Metis::number -3\n";
00448     // clean up the space and return
00449     delete [] options;
00450     delete [] partition;
00451     delete [] xadj;
00452     delete [] adjncy;
00453 cerr << "Metis::number -4\n";    
00454     return *theRefResult;
00455 }
00456 
00457 
00458 const ID &
00459 Metis::number(Graph &theGraph, const ID &lastVertices)
00460 {
00461   return this->number(theGraph);
00462 }
00463 
00464 int 
00465 Metis::sendSelf(int cTag, Channel &theChannel)
00466 {
00467   return 0;
00468 }
00469 
00470 int 
00471 Metis::recvSelf(int cTag, Channel &theChannel, FEM_ObjectBroker &theBroker)
00472 {
00473   return 0;
00474 }
00475