source: inundation/pymetis/metis-4.0/Lib/parmetis.c @ 2051

Last change on this file since 2051 was 2051, checked in by jack, 19 years ago

Python interface to metis. Currently provides only the
METIS_PartMeshNodal function, since that is what is currently needed for partitioning.
Module name is metis.
File size: 11.1 KB
Line 
1/*
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 1998/11/27 17:59:27 karypis 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**************************************************************************/
22void 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**************************************************************************/
44void 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  int i, j;
49  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**************************************************************************/
95void METIS_NodeNDP(int nvtxs, idxtype *xadj, idxtype *adjncy, int npes, 
96                   int *options, idxtype *perm, idxtype *iperm, idxtype *sizes) 
97{
98  int i, ii, j, l, wflag, nflag;
99  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**************************************************************************/
193void MlevelNestedDissectionP(CtrlType *ctrl, GraphType *graph, idxtype *order, int lastvtx, 
194                             int npes, int cpos, idxtype *sizes)
195{
196  int i, j, nvtxs, nbnd, tvwgt, tpwgts2[2];
197  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**************************************************************************/
262void METIS_NodeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
263           idxtype *adjwgt, int *options, int *sepsize, idxtype *part) 
264{
265  int i, j, tvwgt, tpwgts[2];
266  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**************************************************************************/
320void METIS_EdgeComputeSeparator(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, 
321           idxtype *adjwgt, int *options, int *sepsize, idxtype *part) 
322{
323  int i, j, tvwgt, tpwgts[2];
324  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}
Note: See TracBrowser for help on using the repository browser.