SCM

SCM Repository

[matrix] Annotation of /pkg/src/Metis/parmetis.c
ViewVC logotype

Annotation of /pkg/src/Metis/parmetis.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 563 - (view) (download) (as text)

1 : bates 10 /*
2 :     * Copyright 1997, Regents of the University of Minnesota
3 :     *
4 :     * parmetis.c
5 :     *
6 :     * This file contains top level routines that are used by ParMETIS
7 :     *
8 :     * Started 10/14/97
9 :     * George
10 :     *
11 :     * $Id: parmetis.c,v 1.1 2003/12/31 21:32:30 bates Exp $
12 :     *
13 :     */
14 :    
15 :     #include <metis.h>
16 :    
17 :    
18 :     /*************************************************************************
19 :     * This function is the entry point for KMETIS with seed specification
20 :     * in options[7]
21 :     **************************************************************************/
22 :     void METIS_PartGraphKway2(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
23 :     idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts,
24 :     int *options, int *edgecut, idxtype *part)
25 :     {
26 :     int i;
27 :     float *tpwgts;
28 :    
29 :     tpwgts = fmalloc(*nparts, "KMETIS: tpwgts");
30 :     for (i=0; i<*nparts; i++)
31 :     tpwgts[i] = 1.0/(1.0*(*nparts));
32 :    
33 :     METIS_WPartGraphKway2(nvtxs, xadj, adjncy, vwgt, adjwgt, wgtflag, numflag, nparts,
34 :     tpwgts, options, edgecut, part);
35 :    
36 :     free(tpwgts);
37 :     }
38 :    
39 :    
40 :     /*************************************************************************
41 :     * This function is the entry point for KWMETIS with seed specification
42 :     * in options[7]
43 :     **************************************************************************/
44 :     void METIS_WPartGraphKway2(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
45 :     idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts,
46 :     float *tpwgts, int *options, int *edgecut, idxtype *part)
47 :     {
48 : bates 563 /* int i, j; */
49 : bates 10 GraphType graph;
50 :     CtrlType ctrl;
51 :    
52 :     if (*numflag == 1)
53 :     Change2CNumbering(*nvtxs, xadj, adjncy);
54 :    
55 :     SetUpGraph(&graph, OP_KMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, *wgtflag);
56 :    
57 :     if (options[0] == 0) { /* Use the default parameters */
58 :     ctrl.CType = KMETIS_CTYPE;
59 :     ctrl.IType = KMETIS_ITYPE;
60 :     ctrl.RType = KMETIS_RTYPE;
61 :     ctrl.dbglvl = KMETIS_DBGLVL;
62 :     }
63 :     else {
64 :     ctrl.CType = options[OPTION_CTYPE];
65 :     ctrl.IType = options[OPTION_ITYPE];
66 :     ctrl.RType = options[OPTION_RTYPE];
67 :     ctrl.dbglvl = options[OPTION_DBGLVL];
68 :     }
69 :     ctrl.optype = OP_KMETIS;
70 :     ctrl.CoarsenTo = 20*(*nparts);
71 :     ctrl.maxvwgt = 1.5*((graph.vwgt ? idxsum(*nvtxs, graph.vwgt) : (*nvtxs))/ctrl.CoarsenTo);
72 :    
73 :     InitRandom(options[7]);
74 :    
75 :     AllocateWorkSpace(&ctrl, &graph, *nparts);
76 :    
77 :     IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
78 :     IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
79 :    
80 :     *edgecut = MlevelKWayPartitioning(&ctrl, &graph, *nparts, part, tpwgts, 1.03);
81 :    
82 :     IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
83 :     IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
84 :    
85 :     FreeWorkSpace(&ctrl, &graph);
86 :    
87 :     if (*numflag == 1)
88 :     Change2FNumbering(*nvtxs, xadj, adjncy, part);
89 :     }
90 :    
91 :    
92 :     /*************************************************************************
93 :     * This function is the entry point for the node ND code for ParMETIS
94 :     **************************************************************************/
95 :     void METIS_NodeNDP(int nvtxs, idxtype *xadj, idxtype *adjncy, int npes,
96 :     int *options, idxtype *perm, idxtype *iperm, idxtype *sizes)
97 :     {
98 : bates 563 int i, ii, j, l/* , wflag, nflag */;
99 : bates 10 GraphType graph;
100 :     CtrlType ctrl;
101 :     idxtype *cptr, *cind;
102 :    
103 :     if (options[0] == 0) { /* Use the default parameters */
104 :     ctrl.CType = ONMETIS_CTYPE;
105 :     ctrl.IType = ONMETIS_ITYPE;
106 :     ctrl.RType = ONMETIS_RTYPE;
107 :     ctrl.dbglvl = ONMETIS_DBGLVL;
108 :     ctrl.oflags = ONMETIS_OFLAGS;
109 :     ctrl.pfactor = ONMETIS_PFACTOR;
110 :     ctrl.nseps = ONMETIS_NSEPS;
111 :     }
112 :     else {
113 :     ctrl.CType = options[OPTION_CTYPE];
114 :     ctrl.IType = options[OPTION_ITYPE];
115 :     ctrl.RType = options[OPTION_RTYPE];
116 :     ctrl.dbglvl = options[OPTION_DBGLVL];
117 :     ctrl.oflags = options[OPTION_OFLAGS];
118 :     ctrl.pfactor = options[OPTION_PFACTOR];
119 :     ctrl.nseps = options[OPTION_NSEPS];
120 :     }
121 :     if (ctrl.nseps < 1)
122 :     ctrl.nseps = 1;
123 :    
124 :     ctrl.optype = OP_ONMETIS;
125 :     ctrl.CoarsenTo = 100;
126 :    
127 :     IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
128 :     IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
129 :    
130 :     InitRandom(-1);
131 :    
132 :     if (ctrl.oflags&OFLAG_COMPRESS) {
133 :     /*============================================================
134 :     * Compress the graph
135 :     ==============================================================*/
136 :     cptr = idxmalloc(nvtxs+1, "ONMETIS: cptr");
137 :     cind = idxmalloc(nvtxs, "ONMETIS: cind");
138 :    
139 :     CompressGraph(&ctrl, &graph, nvtxs, xadj, adjncy, cptr, cind);
140 :    
141 :     if (graph.nvtxs >= COMPRESSION_FRACTION*(nvtxs)) {
142 :     ctrl.oflags--; /* We actually performed no compression */
143 :     GKfree(&cptr, &cind, LTERM);
144 :     }
145 :     else if (2*graph.nvtxs < nvtxs && ctrl.nseps == 1)
146 :     ctrl.nseps = 2;
147 :     }
148 :     else {
149 :     SetUpGraph(&graph, OP_ONMETIS, nvtxs, 1, xadj, adjncy, NULL, NULL, 0);
150 :     }
151 :    
152 :    
153 :     /*=============================================================
154 :     * Do the nested dissection ordering
155 :     --=============================================================*/
156 :     ctrl.maxvwgt = 1.5*(idxsum(graph.nvtxs, graph.vwgt)/ctrl.CoarsenTo);
157 :     AllocateWorkSpace(&ctrl, &graph, 2);
158 :    
159 :     idxset(2*npes-1, 0, sizes);
160 :     MlevelNestedDissectionP(&ctrl, &graph, iperm, graph.nvtxs, npes, 0, sizes);
161 :    
162 :     FreeWorkSpace(&ctrl, &graph);
163 :    
164 :     if (ctrl.oflags&OFLAG_COMPRESS) { /* Uncompress the ordering */
165 :     if (graph.nvtxs < COMPRESSION_FRACTION*(nvtxs)) {
166 :     /* construct perm from iperm */
167 :     for (i=0; i<graph.nvtxs; i++)
168 :     perm[iperm[i]] = i;
169 :     for (l=ii=0; ii<graph.nvtxs; ii++) {
170 :     i = perm[ii];
171 :     for (j=cptr[i]; j<cptr[i+1]; j++)
172 :     iperm[cind[j]] = l++;
173 :     }
174 :     }
175 :    
176 :     GKfree(&cptr, &cind, LTERM);
177 :     }
178 :    
179 :    
180 :     for (i=0; i<nvtxs; i++)
181 :     perm[iperm[i]] = i;
182 :    
183 :     IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
184 :     IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
185 :    
186 :     }
187 :    
188 :    
189 :    
190 :     /*************************************************************************
191 :     * This function takes a graph and produces a bisection of it
192 :     **************************************************************************/
193 :     void MlevelNestedDissectionP(CtrlType *ctrl, GraphType *graph, idxtype *order, int lastvtx,
194 :     int npes, int cpos, idxtype *sizes)
195 :     {
196 : bates 563 int i/* , j */, nvtxs, nbnd, tvwgt, tpwgts2[2];
197 : bates 10 idxtype *label, *bndind;
198 :     GraphType lgraph, rgraph;
199 :     float ubfactor;
200 :    
201 :     nvtxs = graph->nvtxs;
202 :    
203 :     if (nvtxs == 0) {
204 :     GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
205 :     return;
206 :     }
207 :    
208 :     /* Determine the weights of the partitions */
209 :     tvwgt = idxsum(nvtxs, graph->vwgt);
210 :     tpwgts2[0] = tvwgt/2;
211 :     tpwgts2[1] = tvwgt-tpwgts2[0];
212 :    
213 :     if (cpos >= npes-1)
214 :     ubfactor = ORDER_UNBALANCE_FRACTION;
215 :     else
216 :     ubfactor = 1.05;
217 :    
218 :    
219 :     MlevelNodeBisectionMultiple(ctrl, graph, tpwgts2, ubfactor);
220 :    
221 :     IFSET(ctrl->dbglvl, DBG_SEPINFO, printf("Nvtxs: %6d, [%6d %6d %6d]\n", graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
222 :    
223 :     if (cpos < npes-1) {
224 :     sizes[2*npes-2-cpos] = graph->pwgts[2];
225 :     sizes[2*npes-2-(2*cpos+1)] = graph->pwgts[1];
226 :     sizes[2*npes-2-(2*cpos+2)] = graph->pwgts[0];
227 :     }
228 :    
229 :     /* Order the nodes in the separator */
230 :     nbnd = graph->nbnd;
231 :     bndind = graph->bndind;
232 :     label = graph->label;
233 :     for (i=0; i<nbnd; i++)
234 :     order[label[bndind[i]]] = --lastvtx;
235 :    
236 :     SplitGraphOrder(ctrl, graph, &lgraph, &rgraph);
237 :    
238 :     /* Free the memory of the top level graph */
239 :     GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
240 :    
241 :     if (rgraph.nvtxs > MMDSWITCH || 2*cpos+1 < npes-1)
242 :     MlevelNestedDissectionP(ctrl, &rgraph, order, lastvtx, npes, 2*cpos+1, sizes);
243 :     else {
244 :     MMDOrder(ctrl, &rgraph, order, lastvtx);
245 :     GKfree(&rgraph.gdata, &rgraph.rdata, &rgraph.label, LTERM);
246 :     }
247 :     if (lgraph.nvtxs > MMDSWITCH || 2*cpos+2 < npes-1)
248 :     MlevelNestedDissectionP(ctrl, &lgraph, order, lastvtx-rgraph.nvtxs, npes, 2*cpos+2, sizes);
249 :     else {
250 :     MMDOrder(ctrl, &lgraph, order, lastvtx-rgraph.nvtxs);
251 :     GKfree(&lgraph.gdata, &lgraph.rdata, &lgraph.label, LTERM);
252 :     }
253 :     }
254 :    
255 :    
256 :    
257 :    
258 :     /*************************************************************************
259 :     * This function is the entry point for ONWMETIS. It requires weights on the
260 :     * vertices. It is for the case that the matrix has been pre-compressed.
261 :     **************************************************************************/
262 :     void METIS_NodeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
263 :     idxtype *adjwgt, int *options, int *sepsize, idxtype *part)
264 :     {
265 : bates 563 int /* i, j, */ tvwgt, tpwgts[2];
266 : bates 10 GraphType graph;
267 :     CtrlType ctrl;
268 :    
269 :     SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, 3);
270 :     tvwgt = idxsum(*nvtxs, graph.vwgt);
271 :    
272 :     if (options[0] == 0) { /* Use the default parameters */
273 :     ctrl.CType = ONMETIS_CTYPE;
274 :     ctrl.IType = ONMETIS_ITYPE;
275 :     ctrl.RType = ONMETIS_RTYPE;
276 :     ctrl.dbglvl = ONMETIS_DBGLVL;
277 :     }
278 :     else {
279 :     ctrl.CType = options[OPTION_CTYPE];
280 :     ctrl.IType = options[OPTION_ITYPE];
281 :     ctrl.RType = options[OPTION_RTYPE];
282 :     ctrl.dbglvl = options[OPTION_DBGLVL];
283 :     }
284 :    
285 :     ctrl.oflags = 0;
286 :     ctrl.pfactor = 0;
287 :     ctrl.nseps = 1;
288 :     ctrl.optype = OP_ONMETIS;
289 :     ctrl.CoarsenTo = amin(100, *nvtxs-1);
290 :     ctrl.maxvwgt = 1.5*tvwgt/ctrl.CoarsenTo;
291 :    
292 :     InitRandom(options[7]);
293 :    
294 :     AllocateWorkSpace(&ctrl, &graph, 2);
295 :    
296 :     /*============================================================
297 :     * Perform the bisection
298 :     *============================================================*/
299 :     tpwgts[0] = tvwgt/2;
300 :     tpwgts[1] = tvwgt-tpwgts[0];
301 :    
302 :     MlevelNodeBisectionMultiple(&ctrl, &graph, tpwgts, 1.05);
303 :    
304 :     *sepsize = graph.pwgts[2];
305 :     idxcopy(*nvtxs, graph.where, part);
306 :    
307 :     GKfree(&graph.gdata, &graph.rdata, &graph.label, LTERM);
308 :    
309 :    
310 :     FreeWorkSpace(&ctrl, &graph);
311 :    
312 :     }
313 :    
314 :    
315 :    
316 :     /*************************************************************************
317 :     * This function is the entry point for ONWMETIS. It requires weights on the
318 :     * vertices. It is for the case that the matrix has been pre-compressed.
319 :     **************************************************************************/
320 :     void METIS_EdgeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
321 :     idxtype *adjwgt, int *options, int *sepsize, idxtype *part)
322 :     {
323 : bates 563 int /* i, j, */ tvwgt, tpwgts[2];
324 : bates 10 GraphType graph;
325 :     CtrlType ctrl;
326 :    
327 :     SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, 3);
328 :     tvwgt = idxsum(*nvtxs, graph.vwgt);
329 :    
330 :     if (options[0] == 0) { /* Use the default parameters */
331 :     ctrl.CType = ONMETIS_CTYPE;
332 :     ctrl.IType = ONMETIS_ITYPE;
333 :     ctrl.RType = ONMETIS_RTYPE;
334 :     ctrl.dbglvl = ONMETIS_DBGLVL;
335 :     }
336 :     else {
337 :     ctrl.CType = options[OPTION_CTYPE];
338 :     ctrl.IType = options[OPTION_ITYPE];
339 :     ctrl.RType = options[OPTION_RTYPE];
340 :     ctrl.dbglvl = options[OPTION_DBGLVL];
341 :     }
342 :    
343 :     ctrl.oflags = 0;
344 :     ctrl.pfactor = 0;
345 :     ctrl.nseps = 1;
346 :     ctrl.optype = OP_OEMETIS;
347 :     ctrl.CoarsenTo = amin(100, *nvtxs-1);
348 :     ctrl.maxvwgt = 1.5*tvwgt/ctrl.CoarsenTo;
349 :    
350 :     InitRandom(options[7]);
351 :    
352 :     AllocateWorkSpace(&ctrl, &graph, 2);
353 :    
354 :     /*============================================================
355 :     * Perform the bisection
356 :     *============================================================*/
357 :     tpwgts[0] = tvwgt/2;
358 :     tpwgts[1] = tvwgt-tpwgts[0];
359 :    
360 :     MlevelEdgeBisection(&ctrl, &graph, tpwgts, 1.05);
361 :     ConstructMinCoverSeparator(&ctrl, &graph, 1.05);
362 :    
363 :     *sepsize = graph.pwgts[2];
364 :     idxcopy(*nvtxs, graph.where, part);
365 :    
366 :     GKfree(&graph.gdata, &graph.rdata, &graph.label, LTERM);
367 :    
368 :    
369 :     FreeWorkSpace(&ctrl, &graph);
370 :    
371 :     }

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge