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