Hitmap 1.3
Main Page
Related Pages
Modules
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Friends
Macros
Groups
Pages
extern
metis
Lib
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
{
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
workspacedef::edegrees
EDegreeType * edegrees
Definition:
struct.h:102
graphdef::nrinfo
NRInfoType * nrinfo
Definition:
struct.h:190
controldef::ProjectTmr
timer ProjectTmr
Definition:
struct.h:230
vedegreedef
Definition:
struct.h:87
controldef::RefTmr
timer RefTmr
Definition:
struct.h:230
PQueueType::type
int type
Definition:
struct.h:55
controldef::pfactor
int pfactor
Definition:
struct.h:223
rinfodef::ndegrees
int ndegrees
Definition:
struct.h:121
workspacedef::vedegrees
VEDegreeType * vedegrees
Definition:
struct.h:103
controldef::TotalTmr
timer TotalTmr
Definition:
struct.h:230
vrinfodef::edegrees
VEDegreeType * edegrees
Definition:
struct.h:136
workspacedef::ccore
int ccore
Definition:
struct.h:100
graphdef::pwgts
idxtype * pwgts
Definition:
struct.h:176
rinfodef
Definition:
struct.h:119
graphdef::cmap
idxtype * cmap
Definition:
struct.h:172
graphdef::adjwgtsum
idxtype * adjwgtsum
Definition:
struct.h:168
controldef::optype
int optype
Definition:
struct.h:222
graphdef::vrinfo
VRInfoType * vrinfo
Definition:
struct.h:187
PQueueType::nnodes
int nnodes
Definition:
struct.h:56
vrinfodef::ndegrees
int ndegrees
Definition:
struct.h:135
graphdef::nbnd
int nbnd
Definition:
struct.h:177
graphdef::ed
idxtype * ed
Definition:
struct.h:181
vrinfodef::id
int id
Definition:
struct.h:133
edegreedef::ed
idxtype ed
Definition:
struct.h:79
edegreedef::pid
idxtype pid
Definition:
struct.h:78
controldef::SepTmr
timer SepTmr
Definition:
struct.h:230
graphdef::id
idxtype * id
Definition:
struct.h:181
vpwgtdef::imax
int imax[2][MAXNCON]
Definition:
struct.h:244
PQueueType::nodes
ListNodeType * nodes
Definition:
struct.h:63
controldef::IType
int IType
Definition:
struct.h:218
graphdef::mincut
int mincut
Definition:
struct.h:175
graphdef::bndptr
idxtype * bndptr
Definition:
struct.h:178
workspacedef::core
idxtype * core
Definition:
struct.h:99
controldef::oflags
int oflags
Definition:
struct.h:225
edegreedef
Definition:
struct.h:77
graphdef::rdata
idxtype * rdata
Definition:
struct.h:157
KeyValueType
Definition:
struct.h:30
controldef::AuxTmr1
timer AuxTmr1
Definition:
struct.h:230
KeyValueType::key
idxtype key
Definition:
struct.h:31
controldef::ContractTmr
timer ContractTmr
Definition:
struct.h:230
graphdef::coarser
struct graphdef * coarser
Definition:
struct.h:198
graphdef::finer
struct graphdef * finer
Definition:
struct.h:198
vedegreedef::ned
idxtype ned
Definition:
struct.h:89
vedegreedef::ed
idxtype ed
Definition:
struct.h:89
vedegreedef::pid
idxtype pid
Definition:
struct.h:88
controldef
Definition:
struct.h:214
controldef::CType
int CType
Definition:
struct.h:217
graphdef::where
idxtype * where
Definition:
struct.h:176
vrinfodef::nid
int nid
Definition:
struct.h:133
graphdef::npwgts
float * npwgts
Definition:
struct.h:196
idxtype
int idxtype
Definition:
struct.h:19
controldef::nmaxvwgt
float nmaxvwgt
Definition:
struct.h:221
vrinfodef::gv
int gv
Definition:
struct.h:134
nrinfodef
Definition:
struct.h:146
controldef::AuxTmr5
timer AuxTmr5
Definition:
struct.h:230
vrinfodef
Definition:
struct.h:132
controldef::dbglvl
int dbglvl
Definition:
struct.h:216
PQueueType::buckets
ListNodeType ** buckets
Definition:
struct.h:64
rinfodef::ed
int ed
Definition:
struct.h:120
graphdef::label
idxtype * label
Definition:
struct.h:170
PQueueType::maxnodes
int maxnodes
Definition:
struct.h:57
PQueueType::heap
KeyValueType * heap
Definition:
struct.h:67
graphdef::adjwgt
idxtype * adjwgt
Definition:
struct.h:166
controldef::AuxTmr3
timer AuxTmr3
Definition:
struct.h:230
ListNodeType::prev
struct ListNodeType * prev
Definition:
struct.h:43
graphdef::rinfo
RInfoType * rinfo
Definition:
struct.h:184
workspacedef::cdegree
int cdegree
Definition:
struct.h:104
controldef::AuxTmr6
timer AuxTmr6
Definition:
struct.h:230
workspacedef::maxcore
int maxcore
Definition:
struct.h:100
PQueueType::pgainspan
int pgainspan
Definition:
struct.h:61
controldef::CoarsenTo
int CoarsenTo
Definition:
struct.h:215
vedegreedef::gv
idxtype gv
Definition:
struct.h:90
vrinfodef::ed
int ed
Definition:
struct.h:133
PQueueType::maxgain
int maxgain
Definition:
struct.h:62
graphdef::ncon
int ncon
Definition:
struct.h:194
ListNodeType::id
int id
Definition:
struct.h:42
MAXNCON
#define MAXNCON
Definition:
defs.h:20
workspacedef::auxcore
idxtype * auxcore
Definition:
struct.h:106
graphdef
Definition:
struct.h:156
workspacedef
Definition:
struct.h:98
PQueueType::mustfree
int mustfree
Definition:
struct.h:58
vpwgtdef::max
float max[2][MAXNCON]
Definition:
struct.h:243
graphdef::bndind
idxtype * bndind
Definition:
struct.h:178
controldef::AuxTmr2
timer AuxTmr2
Definition:
struct.h:230
controldef::MatchTmr
timer MatchTmr
Definition:
struct.h:230
controldef::UncoarsenTmr
timer UncoarsenTmr
Definition:
struct.h:230
controldef::InitPartTmr
timer InitPartTmr
Definition:
struct.h:230
controldef::SplitTmr
timer SplitTmr
Definition:
struct.h:230
vpwgtdef
Definition:
struct.h:242
graphdef::vwgt
idxtype * vwgt
Definition:
struct.h:163
controldef::CoarsenTmr
timer CoarsenTmr
Definition:
struct.h:230
ListNodeType::next
struct ListNodeType * next
Definition:
struct.h:43
controldef::RType
int RType
Definition:
struct.h:219
graphdef::minvol
int minvol
Definition:
struct.h:175
rinfodef::edegrees
EDegreeType * edegrees
Definition:
struct.h:122
graphdef::nedges
int nedges
Definition:
struct.h:161
controldef::nseps
int nseps
Definition:
struct.h:224
workspacedef::pmat
idxtype * pmat
Definition:
struct.h:108
graphdef::gdata
idxtype * gdata
Definition:
struct.h:157
controldef::maxvwgt
int maxvwgt
Definition:
struct.h:220
nrinfodef::edegrees
idxtype edegrees[2]
Definition:
struct.h:147
graphdef::nvtxs
int nvtxs
Definition:
struct.h:161
KeyValueType::val
idxtype val
Definition:
struct.h:32
controldef::wspace
WorkSpaceType wspace
Definition:
struct.h:227
graphdef::nvwgt
float * nvwgt
Definition:
struct.h:195
graphdef::vsize
idxtype * vsize
Definition:
struct.h:164
timer
double timer
Definition:
struct.h:208
PQueueType
Definition:
struct.h:54
rinfodef::id
int id
Definition:
struct.h:120
ListNodeType
Definition:
struct.h:41
graphdef::adjncy
idxtype * adjncy
Definition:
struct.h:165
graphdef::xadj
idxtype * xadj
Definition:
struct.h:162
controldef::AuxTmr4
timer AuxTmr4
Definition:
struct.h:230
PQueueType::locator
idxtype * locator
Definition:
struct.h:68
PQueueType::ngainspan
int ngainspan
Definition:
struct.h:61
Generated on Thu Oct 11 2018 12:23:26 for Hitmap 1.3 by
1.8.5