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