Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
struct.h
Go to the documentation of this file.
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 {
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;
65 
66  /* Heap version of the data structure */
69 };
70 
71 typedef struct PQueueType PQueueType;
72 
73 
74 /*************************************************************************
75 * The following data structure stores an edge
76 **************************************************************************/
77 struct edegreedef {
80 };
81 typedef struct edegreedef EDegreeType;
82 
83 
84 /*************************************************************************
85 * The following data structure stores an edge for vol
86 **************************************************************************/
87 struct vedegreedef {
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 */
101 
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 
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 {
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 
171 
173 
174  /* Partition parameters */
177  int nbnd;
179 
180  /* Bisection refinement parameters */
182 
183  /* K-way refinement parameters */
185 
186  /* K-way volume refinement parameters */
188 
189  /* Node refinement information */
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 */
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 
EDegreeType * edegrees
Definition: struct.h:102
NRInfoType * nrinfo
Definition: struct.h:190
timer ProjectTmr
Definition: struct.h:230
timer RefTmr
Definition: struct.h:230
int type
Definition: struct.h:55
int pfactor
Definition: struct.h:223
int ndegrees
Definition: struct.h:121
VEDegreeType * vedegrees
Definition: struct.h:103
timer TotalTmr
Definition: struct.h:230
VEDegreeType * edegrees
Definition: struct.h:136
int ccore
Definition: struct.h:100
idxtype * pwgts
Definition: struct.h:176
idxtype * cmap
Definition: struct.h:172
idxtype * adjwgtsum
Definition: struct.h:168
int optype
Definition: struct.h:222
VRInfoType * vrinfo
Definition: struct.h:187
int nnodes
Definition: struct.h:56
int ndegrees
Definition: struct.h:135
int nbnd
Definition: struct.h:177
idxtype * ed
Definition: struct.h:181
int id
Definition: struct.h:133
idxtype ed
Definition: struct.h:79
idxtype pid
Definition: struct.h:78
timer SepTmr
Definition: struct.h:230
idxtype * id
Definition: struct.h:181
int imax[2][MAXNCON]
Definition: struct.h:244
ListNodeType * nodes
Definition: struct.h:63
int IType
Definition: struct.h:218
int mincut
Definition: struct.h:175
idxtype * bndptr
Definition: struct.h:178
idxtype * core
Definition: struct.h:99
int oflags
Definition: struct.h:225
idxtype * rdata
Definition: struct.h:157
timer AuxTmr1
Definition: struct.h:230
idxtype key
Definition: struct.h:31
timer ContractTmr
Definition: struct.h:230
struct graphdef * coarser
Definition: struct.h:198
struct graphdef * finer
Definition: struct.h:198
idxtype ned
Definition: struct.h:89
idxtype ed
Definition: struct.h:89
idxtype pid
Definition: struct.h:88
int CType
Definition: struct.h:217
idxtype * where
Definition: struct.h:176
int nid
Definition: struct.h:133
float * npwgts
Definition: struct.h:196
int idxtype
Definition: struct.h:19
float nmaxvwgt
Definition: struct.h:221
int gv
Definition: struct.h:134
timer AuxTmr5
Definition: struct.h:230
int dbglvl
Definition: struct.h:216
ListNodeType ** buckets
Definition: struct.h:64
int ed
Definition: struct.h:120
idxtype * label
Definition: struct.h:170
int maxnodes
Definition: struct.h:57
KeyValueType * heap
Definition: struct.h:67
idxtype * adjwgt
Definition: struct.h:166
timer AuxTmr3
Definition: struct.h:230
struct ListNodeType * prev
Definition: struct.h:43
RInfoType * rinfo
Definition: struct.h:184
int cdegree
Definition: struct.h:104
timer AuxTmr6
Definition: struct.h:230
int maxcore
Definition: struct.h:100
int pgainspan
Definition: struct.h:61
int CoarsenTo
Definition: struct.h:215
idxtype gv
Definition: struct.h:90
int ed
Definition: struct.h:133
int maxgain
Definition: struct.h:62
int ncon
Definition: struct.h:194
int id
Definition: struct.h:42
#define MAXNCON
Definition: defs.h:20
idxtype * auxcore
Definition: struct.h:106
int mustfree
Definition: struct.h:58
float max[2][MAXNCON]
Definition: struct.h:243
idxtype * bndind
Definition: struct.h:178
timer AuxTmr2
Definition: struct.h:230
timer MatchTmr
Definition: struct.h:230
timer UncoarsenTmr
Definition: struct.h:230
timer InitPartTmr
Definition: struct.h:230
timer SplitTmr
Definition: struct.h:230
idxtype * vwgt
Definition: struct.h:163
timer CoarsenTmr
Definition: struct.h:230
struct ListNodeType * next
Definition: struct.h:43
int RType
Definition: struct.h:219
int minvol
Definition: struct.h:175
EDegreeType * edegrees
Definition: struct.h:122
int nedges
Definition: struct.h:161
int nseps
Definition: struct.h:224
idxtype * pmat
Definition: struct.h:108
idxtype * gdata
Definition: struct.h:157
int maxvwgt
Definition: struct.h:220
idxtype edegrees[2]
Definition: struct.h:147
int nvtxs
Definition: struct.h:161
idxtype val
Definition: struct.h:32
WorkSpaceType wspace
Definition: struct.h:227
float * nvwgt
Definition: struct.h:195
idxtype * vsize
Definition: struct.h:164
double timer
Definition: struct.h:208
int id
Definition: struct.h:120
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
timer AuxTmr4
Definition: struct.h:230
idxtype * locator
Definition: struct.h:68
int ngainspan
Definition: struct.h:61