source: inundation/pymetis/metis-4.0/Lib/mpmetis.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.4 KB
Line 
1/*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * mpmetis.c
5 *
6 * This file contains the top level routines for the multilevel recursive
7 * bisection algorithm PMETIS.
8 *
9 * Started 7/24/97
10 * George
11 *
12 * $Id: mpmetis.c,v 1.4 1998/11/30 14:50:44 karypis Exp $
13 *
14 */
15
16#include <metis.h>
17
18
19
20/*************************************************************************
21* This function is the entry point for PWMETIS that accepts exact weights
22* for the target partitions
23**************************************************************************/
24void METIS_mCPartGraphRecursive(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy, 
25       idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, 
26       int *options, int *edgecut, idxtype *part)
27{
28  int i, j;
29  GraphType graph;
30  CtrlType ctrl;
31
32  if (*numflag == 1)
33    Change2CNumbering(*nvtxs, xadj, adjncy);
34
35  SetUpGraph(&graph, OP_PMETIS, *nvtxs, *ncon, xadj, adjncy, vwgt, adjwgt, *wgtflag);
36
37  if (options[0] == 0) {  /* Use the default parameters */
38    ctrl.CType  = McPMETIS_CTYPE;
39    ctrl.IType  = McPMETIS_ITYPE;
40    ctrl.RType  = McPMETIS_RTYPE;
41    ctrl.dbglvl = McPMETIS_DBGLVL;
42  }
43  else {
44    ctrl.CType  = options[OPTION_CTYPE];
45    ctrl.IType  = options[OPTION_ITYPE];
46    ctrl.RType  = options[OPTION_RTYPE];
47    ctrl.dbglvl = options[OPTION_DBGLVL];
48  }
49  ctrl.optype = OP_PMETIS;
50  ctrl.CoarsenTo = 100;
51
52  ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo);
53
54  InitRandom(-1);
55
56  AllocateWorkSpace(&ctrl, &graph, *nparts);
57
58  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
59  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
60
61  *edgecut = MCMlevelRecursiveBisection(&ctrl, &graph, *nparts, part, 1.000, 0);
62
63  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
64  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
65
66  FreeWorkSpace(&ctrl, &graph);
67
68  if (*numflag == 1)
69    Change2FNumbering(*nvtxs, xadj, adjncy, part);
70}
71
72
73
74/*************************************************************************
75* This function is the entry point for PWMETIS that accepts exact weights
76* for the target partitions
77**************************************************************************/
78void METIS_mCHPartGraphRecursive(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy, 
79       idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, 
80       float *ubvec, int *options, int *edgecut, idxtype *part)
81{
82  int i, j;
83  GraphType graph;
84  CtrlType ctrl;
85  float *myubvec;
86
87  if (*numflag == 1)
88    Change2CNumbering(*nvtxs, xadj, adjncy);
89
90  SetUpGraph(&graph, OP_PMETIS, *nvtxs, *ncon, xadj, adjncy, vwgt, adjwgt, *wgtflag);
91
92  if (options[0] == 0) {  /* Use the default parameters */
93    ctrl.CType = PMETIS_CTYPE;
94    ctrl.IType = PMETIS_ITYPE;
95    ctrl.RType = PMETIS_RTYPE;
96    ctrl.dbglvl = PMETIS_DBGLVL;
97  }
98  else {
99    ctrl.CType = options[OPTION_CTYPE];
100    ctrl.IType = options[OPTION_ITYPE];
101    ctrl.RType = options[OPTION_RTYPE];
102    ctrl.dbglvl = options[OPTION_DBGLVL];
103  }
104  ctrl.optype = OP_PMETIS;
105  ctrl.CoarsenTo = 100;
106
107  ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo);
108
109  myubvec = fmalloc(*ncon, "PWMETIS: mytpwgts");
110  scopy(*ncon, ubvec, myubvec);
111
112  InitRandom(-1);
113
114  AllocateWorkSpace(&ctrl, &graph, *nparts);
115
116  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
117  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
118
119  *edgecut = MCHMlevelRecursiveBisection(&ctrl, &graph, *nparts, part, myubvec, 0);
120
121  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
122  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
123
124  FreeWorkSpace(&ctrl, &graph);
125  GKfree(&myubvec, LTERM);
126
127  if (*numflag == 1)
128    Change2FNumbering(*nvtxs, xadj, adjncy, part);
129}
130
131
132
133/*************************************************************************
134* This function is the entry point for PWMETIS that accepts exact weights
135* for the target partitions
136**************************************************************************/
137void METIS_mCPartGraphRecursiveInternal(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy, 
138       float *nvwgt, idxtype *adjwgt, int *nparts, int *options, int *edgecut, idxtype *part)
139{
140  int i, j;
141  GraphType graph;
142  CtrlType ctrl;
143
144  SetUpGraph2(&graph, *nvtxs, *ncon, xadj, adjncy, nvwgt, adjwgt);
145
146  if (options[0] == 0) {  /* Use the default parameters */
147    ctrl.CType = PMETIS_CTYPE;
148    ctrl.IType = PMETIS_ITYPE;
149    ctrl.RType = PMETIS_RTYPE;
150    ctrl.dbglvl = PMETIS_DBGLVL;
151  }
152  else {
153    ctrl.CType = options[OPTION_CTYPE];
154    ctrl.IType = options[OPTION_ITYPE];
155    ctrl.RType = options[OPTION_RTYPE];
156    ctrl.dbglvl = options[OPTION_DBGLVL];
157  }
158  ctrl.optype = OP_PMETIS;
159  ctrl.CoarsenTo = 100;
160
161  ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo);
162
163  InitRandom(-1);
164
165  AllocateWorkSpace(&ctrl, &graph, *nparts);
166
167  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
168  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
169
170  *edgecut = MCMlevelRecursiveBisection(&ctrl, &graph, *nparts, part, 1.000, 0);
171
172  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
173  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
174
175  FreeWorkSpace(&ctrl, &graph);
176
177}
178
179
180/*************************************************************************
181* This function is the entry point for PWMETIS that accepts exact weights
182* for the target partitions
183**************************************************************************/
184void METIS_mCHPartGraphRecursiveInternal(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy, 
185       float *nvwgt, idxtype *adjwgt, int *nparts, float *ubvec, int *options, int *edgecut, 
186       idxtype *part)
187{
188  int i, j;
189  GraphType graph;
190  CtrlType ctrl;
191  float *myubvec;
192
193  SetUpGraph2(&graph, *nvtxs, *ncon, xadj, adjncy, nvwgt, adjwgt);
194
195  if (options[0] == 0) {  /* Use the default parameters */
196    ctrl.CType = PMETIS_CTYPE;
197    ctrl.IType = PMETIS_ITYPE;
198    ctrl.RType = PMETIS_RTYPE;
199    ctrl.dbglvl = PMETIS_DBGLVL;
200  }
201  else {
202    ctrl.CType = options[OPTION_CTYPE];
203    ctrl.IType = options[OPTION_ITYPE];
204    ctrl.RType = options[OPTION_RTYPE];
205    ctrl.dbglvl = options[OPTION_DBGLVL];
206  }
207  ctrl.optype = OP_PMETIS;
208  ctrl.CoarsenTo = 100;
209
210  ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo);
211
212  myubvec = fmalloc(*ncon, "PWMETIS: mytpwgts");
213  scopy(*ncon, ubvec, myubvec);
214
215  InitRandom(-1);
216
217  AllocateWorkSpace(&ctrl, &graph, *nparts);
218
219  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
220  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
221
222  *edgecut = MCHMlevelRecursiveBisection(&ctrl, &graph, *nparts, part, myubvec, 0);
223
224  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
225  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
226
227  FreeWorkSpace(&ctrl, &graph);
228  GKfree(&myubvec, LTERM);
229
230}
231
232
233
234
235/*************************************************************************
236* This function takes a graph and produces a bisection of it
237**************************************************************************/
238int MCMlevelRecursiveBisection(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *part, 
239       float ubfactor, int fpart)
240{
241  int i, j, nvtxs, ncon, cut;
242  idxtype *label, *where;
243  GraphType lgraph, rgraph;
244  float tpwgts[2];
245
246  nvtxs = graph->nvtxs;
247  if (nvtxs == 0) {
248    printf("\t***Cannot bisect a graph with 0 vertices!\n\t***You are trying to partition a graph into too many parts!\n");
249    return 0;
250  }
251
252  /* Determine the weights of the partitions */
253  tpwgts[0] = 1.0*(nparts>>1)/(1.0*nparts);
254  tpwgts[1] = 1.0 - tpwgts[0];
255
256  MCMlevelEdgeBisection(ctrl, graph, tpwgts, ubfactor);
257  cut = graph->mincut;
258
259  label = graph->label;
260  where = graph->where;
261  for (i=0; i<nvtxs; i++)
262    part[label[i]] = where[i] + fpart;
263
264  if (nparts > 2) 
265    SplitGraphPart(ctrl, graph, &lgraph, &rgraph);
266
267  /* Free the memory of the top level graph */
268  GKfree(&graph->gdata, &graph->nvwgt, &graph->rdata, &graph->npwgts, &graph->label, LTERM);
269
270
271  /* Do the recursive call */
272  if (nparts > 3) {
273    cut += MCMlevelRecursiveBisection(ctrl, &lgraph, nparts/2, part, ubfactor, fpart);
274    cut += MCMlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, ubfactor, fpart+nparts/2);
275  }
276  else if (nparts == 3) {
277    cut += MCMlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, ubfactor, fpart+nparts/2);
278    GKfree(&lgraph.gdata, &lgraph.nvwgt, &lgraph.label, LTERM);
279  }
280
281  return cut;
282
283}
284
285
286
287/*************************************************************************
288* This function takes a graph and produces a bisection of it
289**************************************************************************/
290int MCHMlevelRecursiveBisection(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *part, 
291      float *ubvec, int fpart)
292{
293  int i, j, nvtxs, ncon, cut;
294  idxtype *label, *where;
295  GraphType lgraph, rgraph;
296  float tpwgts[2], *npwgts, *lubvec, *rubvec;
297
298  lubvec = rubvec = NULL;
299
300  nvtxs = graph->nvtxs;
301  ncon = graph->ncon;
302  if (nvtxs == 0) {
303    printf("\t***Cannot bisect a graph with 0 vertices!\n\t***You are trying to partition a graph into too many parts!\n");
304    return 0;
305  }
306
307  /* Determine the weights of the partitions */
308  tpwgts[0] = 1.0*(nparts>>1)/(1.0*nparts);
309  tpwgts[1] = 1.0 - tpwgts[0];
310
311  /* For now, relax at the coarsest level only */
312  if (nparts == 2)
313    MCHMlevelEdgeBisection(ctrl, graph, tpwgts, ubvec);
314  else
315    MCMlevelEdgeBisection(ctrl, graph, tpwgts, 1.000);
316  cut = graph->mincut;
317
318  label = graph->label;
319  where = graph->where;
320  for (i=0; i<nvtxs; i++)
321    part[label[i]] = where[i] + fpart;
322
323  if (nparts > 2) {
324    /* Adjust the ubvecs before the split */
325    npwgts = graph->npwgts;
326    lubvec = fmalloc(ncon, "MCHMlevelRecursiveBisection");
327    rubvec = fmalloc(ncon, "MCHMlevelRecursiveBisection");
328
329    for (i=0; i<ncon; i++) {
330      lubvec[i] = ubvec[i]*tpwgts[0]/npwgts[i];
331      lubvec[i] = amax(lubvec[i], 1.01);
332
333      rubvec[i] = ubvec[i]*tpwgts[1]/npwgts[ncon+i];
334      rubvec[i] = amax(rubvec[i], 1.01);
335    }
336
337    SplitGraphPart(ctrl, graph, &lgraph, &rgraph);
338  }
339
340  /* Free the memory of the top level graph */
341  GKfree(&graph->gdata, &graph->nvwgt, &graph->rdata, &graph->npwgts, &graph->label, LTERM);
342
343
344  /* Do the recursive call */
345  if (nparts > 3) {
346    cut += MCHMlevelRecursiveBisection(ctrl, &lgraph, nparts/2, part, lubvec, fpart);
347    cut += MCHMlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, rubvec, fpart+nparts/2);
348  }
349  else if (nparts == 3) {
350    cut += MCHMlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, rubvec, fpart+nparts/2);
351    GKfree(&lgraph.gdata, &lgraph.nvwgt, &lgraph.label, LTERM);
352  }
353
354  GKfree(&lubvec, &rubvec, LTERM);
355
356  return cut;
357
358}
359
360
361
362
363/*************************************************************************
364* This function performs multilevel bisection
365**************************************************************************/
366void MCMlevelEdgeBisection(CtrlType *ctrl, GraphType *graph, float *tpwgts, float ubfactor)
367{
368  GraphType *cgraph;
369
370  cgraph = MCCoarsen2Way(ctrl, graph);
371
372  MocInit2WayPartition(ctrl, cgraph, tpwgts, ubfactor);
373
374  MocRefine2Way(ctrl, graph, cgraph, tpwgts, ubfactor); 
375
376}
377
378
379
380/*************************************************************************
381* This function performs multilevel bisection
382**************************************************************************/
383void MCHMlevelEdgeBisection(CtrlType *ctrl, GraphType *graph, float *tpwgts, float *ubvec)
384{
385  int i;
386  GraphType *cgraph;
387
388/*
389  for (i=0; i<graph->ncon; i++)
390    printf("%.4f ", ubvec[i]);
391  printf("\n");
392*/
393
394  cgraph = MCCoarsen2Way(ctrl, graph);
395
396  MocInit2WayPartition2(ctrl, cgraph, tpwgts, ubvec);
397
398  MocRefine2Way2(ctrl, graph, cgraph, tpwgts, ubvec); 
399
400}
401
402
Note: See TracBrowser for help on using the repository browser.