MetisNumberer.cpp

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.2 $
00022 // $Date: 2003/02/14 23:01:23 $
00023 // $Source: /usr/local/cvs/OpenSees/SRC/graph/numberer/MetisNumberer.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 NOW
00049 #include <GKlib.h>
00050 int IsWeighted;
00051 timer TotalTmr;         /* Times the entire algorithm */
00052 timer CoarsenTmr;       /* Times total coarsening time */
00053 timer GreedyTmr;        /* Times Total Greedy Time */
00054 timer GreedyInitTmr;    /* Times initialization cost of Greedy */
00055 timer GreedyIterTmr;    /* Times Iterative cost of Greedy */
00056 timer GreedyWrapUpTmr;  /* Times the wrap up phase of Greedy */
00057 timer MlevelTmr;        /* Times the entire multilevel algorithm */
00058 timer InitPartTmr;      /* Times the initial partition phase */
00059 timer ProjectTmr;       /* Times the projection of the partition */
00060 timer SplitTmr;         /* Times the boundary creation */
00061 timer BalanceTmr;       /* Times the time required for balancing */
00062 timer IOTmr;            /* Times the file input time */
00063 timer UncrsTmr;         /* Times the file input time */
00064 #endif
00065 
00066 extern "C" 
00067 int PMETIS(int *, int *, int *, int *, int *, int *, int *, int *, int *, int *, int *);
00068 
00069 extern "C" 
00070 int KMETIS(int *, int *, int *, int *, int *, int *, int *, int *, int *, int *, int *);
00071 
00072 
00073 Metis::Metis() 
00074 :myPtype(0), myMtype(0), myCoarsenTo(0), myRtype(0), myIPtype(0),
00075  defaultOptions(true)
00076 {
00077     
00078 }
00079 
00080 Metis::Metis(int Ptype, 
00081           int Mtype, 
00082           int coarsenTo,
00083           int Rtype, 
00084           int IPtype)
00085 :myPtype(Ptype), myMtype(Mtype), myCoarsenTo(coarsenTo), myRtype(Rtype), 
00086  myIPtype(IPtype), defaultOptions(false)
00087 {
00088     // check the options are valid
00089     checkOptions();
00090 }    
00091 
00092     
00093 Metis::~Metis() 
00094 {
00095 
00096 }    
00097 
00098 bool
00099 Metis::setOptions(int Ptype, 
00100                   int Mtype,
00101                   int coarsenTo,
00102                   int Rtype, 
00103                   int IPtype)
00104 {
00105     myPtype=Ptype; 
00106     myMtype = Mtype; 
00107     myCoarsenTo = coarsenTo; 
00108     myRtype = Rtype; 
00109     myIPtype = IPtype; 
00110 
00111     defaultOptions = false;
00112     
00113     return checkOptions();
00114     
00115 }    
00116 
00117 
00118 // bool checkOptions(void) const
00119 //      returns true if options are o.k., false otherwise
00120 
00121 bool
00122 Metis::checkOptions(void) 
00123 {
00124 
00125     // check default not set
00126     
00127     if (defaultOptions == true)
00128         return true;
00129 
00130     
00131     // otherwise check all options for valid value
00132     bool okFlag = true;    
00133     
00134     if ((myPtype != 1) || (myPtype != 2)) {
00135         okFlag = false;
00136         opserr << "WARNING: Metis::partition ";
00137         opserr << " - Illegal Ptype " << myPtype << endln;
00138     }
00139         
00140     if ((myMtype != 1) ||  (myMtype != 2) || (myMtype != 3) || 
00141         ((myMtype != 4) || (myMtype != 5) || myMtype != 11) || 
00142         (myMtype != 21) || (myMtype != 51)) {
00143         okFlag = false;
00144         opserr << "WARNING: Metis::partition ";
00145         opserr << " - Illegal Mtype " << myMtype << endln;
00146     }
00147 
00148     if (myPtype == 1)  
00149         if ((myRtype != 1) || (myRtype != 2) || (myRtype != 3) ||
00150             (myRtype != 11) || (myRtype != 12) || (myRtype != 13) ||
00151             (myRtype != 20)) {
00152             okFlag = false;
00153             opserr << "WARNING: Metis::partition ";
00154             opserr << " - Illegal Rtype " << myRtype << endln;
00155             opserr << " for Ptype " << myPtype << endln;            
00156         }
00157     else 
00158         if (myPtype == 2)
00159             if ((myRtype != 11) || (myRtype != 12) || (myRtype != 20)) {
00160                 okFlag = false;
00161                 opserr << "WARNING: Metis::partition ";
00162                 opserr << " - Illegal Rtype " << myRtype << endln;
00163                 opserr << " for Ptype " << myPtype << endln;        
00164             }
00165     
00166     if ((myIPtype != 1) || (myIPtype != 2) || (myIPtype != 3) || 
00167         (myIPtype != 4)) {
00168         okFlag = false;
00169         opserr << "WARNING: Metis::partition ";
00170         opserr << " - Illegal IPtype " << myIPtype << endln;
00171     }       
00172         
00173     if (myCoarsenTo < 0) {
00174         okFlag = false;
00175         opserr << "WARNING: Metis::partition ";
00176         opserr << " - Illegal coarsen To " << myCoarsenTo << endln;
00177     }       
00178 
00179     if (okFlag == false)
00180         defaultOptions = true;
00181     
00182     return okFlag;
00183 
00184 }
00185 
00186 
00187 bool 
00188 Metis::setDefaultOptions(void)
00189 {
00190     defaultOptions = true;
00191     return true;
00192 }
00193 
00194 
00195 // int partition(Graph &theGraph, int numPart)
00196 //      Method to partition the graph. It first creates the arrays needed
00197 //      by the metis lib and then invokes a function from the metis lib to
00198 //      partition the graph. The solors of the vertices of the graph are
00199 //      set to colors 0 through numPart-1 to indicate which partition the
00200 //      vrtices are in. Returns -1 if options are not set, -2 if metis failed.
00201 
00202 int
00203 Metis::partition(Graph &theGraph, int numPart)
00204 {
00205     // first we check that the options are valid
00206     if (checkOptions() == false)
00207         return -1;
00208     
00209     // now we get room for the data structures metis needs
00210 
00211     int numVertex = theGraph.getNumVertex();
00212     int numEdge = theGraph.getNumEdge();
00213 
00214     int *options = new int [5];
00215     int *partition = new int [numVertex+1];    
00216     int *xadj = new int [numVertex+2];
00217     int *adjncy = new int [2*numEdge];
00218     int *vwgts = 0;
00219     int *ewgts = 0;
00220     int numbering = 0;
00221     int weightflag = 0; // no weights on our graphs yet
00222 
00223     if (START_VERTEX_NUM == 0)
00224         numbering = 0;  
00225     else if (START_VERTEX_NUM == 1)
00226         numbering = 1;
00227     else {
00228         opserr << "WARNING Metis::partition - No partitioning done";
00229         opserr << " vertex numbering must start at 0 or 1\n";
00230         return (-2);
00231     }
00232     int edgecut;
00233     
00234     if ((options == 0) || (partition == 0) || (xadj == 0) || (adjncy == 0)) {
00235         opserr << "WARNING Metis::partition - No partitioning done";
00236         opserr << " as ran out of memory\n";
00237         return (-2);
00238     }
00239 
00240 
00241     // we build these data structures
00242     
00243     int indexEdge = 0;
00244     xadj[0] = 0;
00245 
00246     Vertex *vertexPtr;
00247     for (int vertex =0; vertex<numVertex; vertex++) {
00248         vertexPtr = theGraph.getVertexPtr(vertex+START_VERTEX_NUM);
00249         
00250         // check we don't have an invalid vertex numbering scheme
00251         // if so WARNING message, clean up and return -2
00252 
00253         if (vertexPtr == 0) {
00254             opserr << "WARNING Metis::partition - No partitioning done";
00255             opserr << " Metis requires consequtive Vertex Numbering\n";
00256             
00257             delete [] options;
00258             delete [] partition;
00259             delete [] xadj;
00260             delete [] adjncy;
00261             
00262             return -2;
00263         }
00264         
00265         const ID&adjacency = vertexPtr->getAdjacency();
00266         int degree = adjacency.Size();
00267         for (int i=0; i<degree; i++) {
00268             adjncy[indexEdge++] = adjacency(i)-START_VERTEX_NUM;
00269         }
00270         
00271         xadj[vertex+1] = indexEdge;
00272     }
00273 
00274 
00275     if (defaultOptions == true) 
00276         options[0] = 0;
00277     else {
00278         options[0] =1;
00279         options[1] = myCoarsenTo;
00280         options[2] = myMtype;
00281         options[3] = myIPtype;
00282         options[4] = myRtype;
00283     }
00284     
00285     
00286     int j;
00287     
00288     // we now the metis routines
00289 
00290     if (myPtype == 1)
00291         PMETIS(&numVertex, xadj, adjncy, vwgts, ewgts, &weightflag, &numPart,
00292                options, &numbering, &edgecut, partition);
00293     else                
00294         KMETIS(&numVertex, xadj, adjncy, vwgts, ewgts, &weightflag, &numPart,
00295                options, &numbering, &edgecut, partition);
00296 
00297 
00298     // we set the vertex colors to correspond to the partitioned scheme
00299     for (int vert =0; vert<numVertex; vert++) {
00300         vertexPtr = theGraph.getVertexPtr(vert+START_VERTEX_NUM);
00301         vertexPtr->setColor(partition[vert]+1); // start colors at 1
00302     }
00303 
00304     // clean up the space and return
00305     
00306     delete [] options;
00307     delete [] partition;
00308     delete [] xadj;
00309     delete [] adjncy;
00310     
00311     return 0;
00312 }
00313 
00314 
00315 
00316
Generated on Mon Oct 23 15:05:12 2006 for OpenSees by 1.5.0
opensees-support @ berkeley.edu
Supported by the National Science Foundation