00001 /* 00002 * Copyright 1997, Regents of the University of Minnesota 00003 * 00004 * struct.h 00005 * 00006 * This file contains data structures for ILU routines. 00007 * 00008 * Started 9/26/95 00009 * George 00010 * 00011 * $Id$ 00012 */ 00013 00014 #ifndef __parmetis_h__ 00015 /* Undefine the following #define in order to use short int as the idxtype */ 00016 #define IDXTYPE_INT 00017 00018 /* Indexes are as long as integers for now */ 00019 #ifdef IDXTYPE_INT 00020 typedef int idxtype; 00021 #else 00022 typedef short idxtype; 00023 #endif 00024 #endif 00025 00026 /* define floattype to double for maximum fp precision */ 00027 typedef double floattype; 00028 00029 #define MAXIDX (1<<8*sizeof(idxtype)-2) 00030 /* This is the type passed as the size argument to malloc(). 00031 It can be helpful to have this be longer than "int" 00032 on 64-bit machines that still have a 32-bit "int". 00033 */ 00034 typedef unsigned long memsize_t; 00035 00036 00037 /************************************************************************* 00038 * The following data structure stores key-value pair 00039 **************************************************************************/ 00040 struct KeyValueType { 00041 idxtype key; 00042 idxtype val; 00043 }; 00044 00045 typedef struct KeyValueType KeyValueType; 00046 00047 00048 /************************************************************************* 00049 * The following data structure will hold a node of a doubly-linked list. 00050 **************************************************************************/ 00051 struct ListNodeType { 00052 int id; /* The id value of the node */ 00053 struct ListNodeType *prev, *next; /* It's a doubly-linked list */ 00054 }; 00055 00056 typedef struct ListNodeType ListNodeType; 00057 00058 00059 00060 /************************************************************************* 00061 * The following data structure is used to store the buckets for the 00062 * refinment algorithms 00063 **************************************************************************/ 00064 struct PQueueType { 00065 int type; /* The type of the representation used */ 00066 int nnodes; 00067 int maxnodes; 00068 int mustfree; 00069 00070 /* Linear array version of the data structures */ 00071 int pgainspan, ngainspan; /* plus and negative gain span */ 00072 int maxgain; 00073 ListNodeType *nodes; 00074 ListNodeType **buckets; 00075 00076 /* Heap version of the data structure */ 00077 KeyValueType *heap; 00078 idxtype *locator; 00079 }; 00080 00081 typedef struct PQueueType PQueueType; 00082 00083 00084 /************************************************************************* 00085 * The following data structure stores an edge 00086 **************************************************************************/ 00087 struct edegreedef { 00088 idxtype pid; 00089 idxtype ed; 00090 }; 00091 typedef struct edegreedef EDegreeType; 00092 00093 00094 /************************************************************************* 00095 * The following data structure stores an edge for vol 00096 **************************************************************************/ 00097 struct vedegreedef { 00098 idxtype pid; 00099 idxtype ed, ned; 00100 idxtype gv; 00101 }; 00102 typedef struct vedegreedef VEDegreeType; 00103 00104 00105 /************************************************************************* 00106 * This data structure holds various working space data 00107 **************************************************************************/ 00108 struct workspacedef { 00109 idxtype *core; /* Where pairs, indices, and degrees are coming from */ 00110 memsize_t maxcore, ccore; 00111 00112 EDegreeType *edegrees; 00113 VEDegreeType *vedegrees; 00114 int cdegree; 00115 00116 idxtype *auxcore; /* This points to the memory of the edegrees */ 00117 00118 idxtype *pmat; /* An array of k^2 used for eliminating domain 00119 connectivity in k-way refinement */ 00120 }; 00121 00122 typedef struct workspacedef WorkSpaceType; 00123 00124 00125 /************************************************************************* 00126 * The following data structure holds information on degrees for k-way 00127 * partition 00128 **************************************************************************/ 00129 struct rinfodef { 00130 int id, ed; /* ID/ED of nodes */ 00131 int ndegrees; /* The number of different ext-degrees */ 00132 EDegreeType *edegrees; /* List of edges */ 00133 }; 00134 00135 typedef struct rinfodef RInfoType; 00136 00137 00138 /************************************************************************* 00139 * The following data structure holds information on degrees for k-way 00140 * vol-based partition 00141 **************************************************************************/ 00142 struct vrinfodef { 00143 int id, ed, nid; /* ID/ED of nodes */ 00144 int gv; /* IV/EV of nodes */ 00145 int ndegrees; /* The number of different ext-degrees */ 00146 VEDegreeType *edegrees; /* List of edges */ 00147 }; 00148 00149 typedef struct vrinfodef VRInfoType; 00150 00151 00152 /************************************************************************* 00153 * The following data structure holds information on degrees for k-way 00154 * partition 00155 **************************************************************************/ 00156 struct nrinfodef { 00157 idxtype edegrees[2]; 00158 }; 00159 00160 typedef struct nrinfodef NRInfoType; 00161 00162 00163 /************************************************************************* 00164 * This data structure holds the input graph 00165 **************************************************************************/ 00166 struct graphdef { 00167 idxtype *gdata, *rdata; /* Memory pools for graph and refinement data. 00168 This is where memory is allocated and used 00169 the rest of the fields in this structure */ 00170 00171 int nvtxs, nedges; /* The # of vertices and edges in the graph */ 00172 idxtype *xadj; /* Pointers to the locally stored vertices */ 00173 idxtype *vwgt; /* Vertex weights */ 00174 idxtype *vsize; /* Vertex sizes for min-volume formulation */ 00175 idxtype *adjncy; /* Array that stores the adjacency lists of nvtxs */ 00176 idxtype *adjwgt; /* Array that stores the weights of the adjacency lists */ 00177 00178 idxtype *adjwgtsum; /* The sum of the adjacency weight of each vertex */ 00179 00180 idxtype *label; 00181 00182 idxtype *cmap; 00183 00184 /* Partition parameters */ 00185 int mincut, minvol; 00186 idxtype *where, *pwgts; 00187 int nbnd; 00188 idxtype *bndptr, *bndind; 00189 00190 /* Bisection refinement parameters */ 00191 idxtype *id, *ed; 00192 00193 /* K-way refinement parameters */ 00194 RInfoType *rinfo; 00195 00196 /* K-way volume refinement parameters */ 00197 VRInfoType *vrinfo; 00198 00199 /* Node refinement information */ 00200 NRInfoType *nrinfo; 00201 00202 00203 /* Additional info needed by the MOC routines */ 00204 int ncon; /* The # of constrains */ 00205 floattype *nvwgt; /* Normalized vertex weights */ 00206 floattype *npwgts; /* The normalized partition weights */ 00207 00208 struct graphdef *coarser, *finer; 00209 }; 00210 00211 typedef struct graphdef GraphType; 00212 00213 00214 00215 /************************************************************************* 00216 * The following data type implements a timer 00217 **************************************************************************/ 00218 typedef double timer; 00219 00220 00221 /************************************************************************* 00222 * The following structure stores information used by Metis 00223 **************************************************************************/ 00224 struct controldef { 00225 int CoarsenTo; /* The # of vertices in the coarsest graph */ 00226 int dbglvl; /* Controls the debuging output of the program */ 00227 int CType; /* The type of coarsening */ 00228 int IType; /* The type of initial partitioning */ 00229 int RType; /* The type of refinement */ 00230 int maxvwgt; /* The maximum allowed weight for a vertex */ 00231 floattype nmaxvwgt; /* The maximum allowed weight for a vertex for each constrain */ 00232 int optype; /* Type of operation */ 00233 int pfactor; /* .1*prunning factor */ 00234 int nseps; /* The number of separators to be found during multiple bisections */ 00235 int oflags; 00236 00237 WorkSpaceType wspace; /* Work Space Informations */ 00238 00239 /* Various Timers */ 00240 timer TotalTmr, InitPartTmr, MatchTmr, ContractTmr, CoarsenTmr, UncoarsenTmr, 00241 SepTmr, RefTmr, ProjectTmr, SplitTmr, AuxTmr1, AuxTmr2, AuxTmr3, AuxTmr4, AuxTmr5, AuxTmr6; 00242 00243 }; 00244 00245 typedef struct controldef CtrlType; 00246 00247 00248 /************************************************************************* 00249 * The following data structure stores max-partition weight info for 00250 * Vertical MOC k-way refinement 00251 **************************************************************************/ 00252 struct vpwgtdef { 00253 floattype max[2][MAXNCON]; 00254 int imax[2][MAXNCON]; 00255 }; 00256 00257 typedef struct vpwgtdef VPInfoType; 00258 00259 00260 00261
1.5.5