source: inundation/pymetis/metis-4.0/Lib/struct.h @ 2806

Last change on this file since 2806 was 2806, checked in by jack, 18 years ago

Update to use long as the index type. Needs verification on 32-bit
machines.

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