1 /* 2 * Copyright 1997, Regents of the University of Minnesota 3 * 4 * struct.h 5 * 6 * This file contains data structures for ILU routines. 7 * 8 * Started 9/26/95 9 * George 10 * 11 * $Id: struct.h,v 1.1 1998/11/27 17:59:31 karypis Exp $ 12 */ 13 14 /* Undefine the following #define in order to use short int as the idxtype */ 15 #define IDXTYPE_INT 16 17 /* Indexes are as long as integers for now */ 18 #ifdef IDXTYPE_INT 19 typedef int idxtype; 20 #else 21 typedef short idxtype; 22 #endif 23 24 #define MAXIDX (1<<8*sizeof(idxtype)-2) 25 26 27 /************************************************************************* 28 * The following data structure stores key-value pair 29 **************************************************************************/ 30 struct KeyValueType { 31 idxtype key; 32 idxtype val; 33 }; 34 35 typedef struct KeyValueType KeyValueType; 36 37 38 /************************************************************************* 39 * The following data structure will hold a node of a doubly-linked list. 40 **************************************************************************/ 41 struct ListNodeType { 42 int id; /* The id value of the node */ 43 struct ListNodeType *prev, *next; /* It's a doubly-linked list */ 44 }; 45 46 typedef struct ListNodeType ListNodeType; 47 48 49 50 /************************************************************************* 51 * The following data structure is used to store the buckets for the 52 * refinment algorithms 53 **************************************************************************/ 54 struct PQueueType { 55 int type; /* The type of the representation used */ 56 int nnodes; 57 int maxnodes; 58 int mustfree; 59 60 /* Linear array version of the data structures */ 61 int pgainspan, ngainspan; /* plus and negative gain span */ 62 int maxgain; 63 ListNodeType *nodes; 64 ListNodeType **buckets; 65 66 /* Heap version of the data structure */ 67 KeyValueType *heap; 68 idxtype *locator; 69 }; 70 71 typedef struct PQueueType PQueueType; 72 73 74 /************************************************************************* 75 * The following data structure stores an edge 76 **************************************************************************/ 77 struct edegreedef { 78 idxtype pid; 79 idxtype ed; 80 }; 81 typedef struct edegreedef EDegreeType; 82 83 84 /************************************************************************* 85 * The following data structure stores an edge for vol 86 **************************************************************************/ 87 struct vedegreedef { 88 idxtype pid; 89 idxtype ed, ned; 90 idxtype gv; 91 }; 92 typedef struct vedegreedef VEDegreeType; 93 94 95 /************************************************************************* 96 * This data structure holds various working space data 97 **************************************************************************/ 98 struct workspacedef { 99 idxtype *core; /* Where pairs, indices, and degrees are coming from */ 100 int maxcore, ccore; 101 102 EDegreeType *edegrees; 103 VEDegreeType *vedegrees; 104 int cdegree; 105 106 idxtype *auxcore; /* This points to the memory of the edegrees */ 107 108 idxtype *pmat; /* An array of k^2 used for eliminating domain 109 connectivity in k-way refinement */ 110 }; 111 112 typedef struct workspacedef WorkSpaceType; 113 114 115 /************************************************************************* 116 * The following data structure holds information on degrees for k-way 117 * partition 118 **************************************************************************/ 119 struct rinfodef { 120 int id, ed; /* ID/ED of nodes */ 121 int ndegrees; /* The number of different ext-degrees */ 122 EDegreeType *edegrees; /* List of edges */ 123 }; 124 125 typedef struct rinfodef RInfoType; 126 127 128 /************************************************************************* 129 * The following data structure holds information on degrees for k-way 130 * vol-based partition 131 **************************************************************************/ 132 struct vrinfodef { 133 int id, ed, nid; /* ID/ED of nodes */ 134 int gv; /* IV/EV of nodes */ 135 int ndegrees; /* The number of different ext-degrees */ 136 VEDegreeType *edegrees; /* List of edges */ 137 }; 138 139 typedef struct vrinfodef VRInfoType; 140 141 142 /************************************************************************* 143 * The following data structure holds information on degrees for k-way 144 * partition 145 **************************************************************************/ 146 struct nrinfodef { 147 idxtype edegrees[2]; 148 }; 149 150 typedef struct nrinfodef NRInfoType; 151 152 153 /************************************************************************* 154 * This data structure holds the input graph 155 **************************************************************************/ 156 struct graphdef { 157 idxtype *gdata, *rdata; /* Memory pools for graph and refinement data. 158 This is where memory is allocated and used 159 the rest of the fields in this structure */ 160 161 int nvtxs, nedges; /* The # of vertices and edges in the graph */ 162 idxtype *xadj; /* Pointers to the locally stored vertices */ 163 idxtype *vwgt; /* Vertex weights */ 164 idxtype *vsize; /* Vertex sizes for min-volume formulation */ 165 idxtype *adjncy; /* Array that stores the adjacency lists of nvtxs */ 166 idxtype *adjwgt; /* Array that stores the weights of the adjacency lists */ 167 168 idxtype *adjwgtsum; /* The sum of the adjacency weight of each vertex */ 169 170 idxtype *label; 171 172 idxtype *cmap; 173 174 /* Partition parameters */ 175 int mincut, minvol; 176 idxtype *where, *pwgts; 177 int nbnd; 178 idxtype *bndptr, *bndind; 179 180 /* Bisection refinement parameters */ 181 idxtype *id, *ed; 182 183 /* K-way refinement parameters */ 184 RInfoType *rinfo; 185 186 /* K-way volume refinement parameters */ 187 VRInfoType *vrinfo; 188 189 /* Node refinement information */ 190 NRInfoType *nrinfo; 191 192 193 /* Additional info needed by the MOC routines */ 194 int ncon; /* The # of constrains */ 195 float *nvwgt; /* Normalized vertex weights */ 196 float *npwgts; /* The normalized partition weights */ 197 198 struct graphdef *coarser, *finer; 199 }; 200 201 typedef struct graphdef GraphType; 202 203 204 205 /************************************************************************* 206 * The following data type implements a timer 207 **************************************************************************/ 208 typedef double timer; 209 210 211 /************************************************************************* 212 * The following structure stores information used by Metis 213 **************************************************************************/ 214 struct controldef { 215 int CoarsenTo; /* The # of vertices in the coarsest graph */ 216 int dbglvl; /* Controls the debuging output of the program */ 217 int CType; /* The type of coarsening */ 218 int IType; /* The type of initial partitioning */ 219 int RType; /* The type of refinement */ 220 int maxvwgt; /* The maximum allowed weight for a vertex */ 221 float nmaxvwgt; /* The maximum allowed weight for a vertex for each constrain */ 222 int optype; /* Type of operation */ 223 int pfactor; /* .1*prunning factor */ 224 int nseps; /* The number of separators to be found during multiple bisections */ 225 int oflags; 226 227 WorkSpaceType wspace; /* Work Space Informations */ 228 229 /* Various Timers */ 230 timer TotalTmr, InitPartTmr, MatchTmr, ContractTmr, CoarsenTmr, UncoarsenTmr, 231 SepTmr, RefTmr, ProjectTmr, SplitTmr, AuxTmr1, AuxTmr2, AuxTmr3, AuxTmr4, AuxTmr5, AuxTmr6; 232 233 }; 234 235 typedef struct controldef CtrlType; 236 237 238 /************************************************************************* 239 * The following data structure stores max-partition weight info for 240 * Vertical MOC k-way refinement 241 **************************************************************************/ 242 struct vpwgtdef { 243 float max[2][MAXNCON]; 244 int imax[2][MAXNCON]; 245 }; 246 247 typedef struct vpwgtdef VPInfoType; 248 249 250 251 252