source: inundation/pymetis/metis-4.0/Lib/initpart.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: 12.2 KB
Line 
1/*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * initpart.c
5 *
6 * This file contains code that performs the initial partition of the
7 * coarsest graph
8 *
9 * Started 7/23/97
10 * George
11 *
12 * $Id: initpart.c,v 1.1 1998/11/27 17:59:15 karypis Exp $
13 *
14 */
15
16#include <metis.h>
17
18/*************************************************************************
19* This function computes the initial bisection of the coarsest graph
20**************************************************************************/
21void Init2WayPartition(CtrlType *ctrl, GraphType *graph, int *tpwgts, float ubfactor) 
22{
23  int dbglvl;
24
25  dbglvl = ctrl->dbglvl;
26  IFSET(ctrl->dbglvl, DBG_REFINE, ctrl->dbglvl -= DBG_REFINE);
27  IFSET(ctrl->dbglvl, DBG_MOVEINFO, ctrl->dbglvl -= DBG_MOVEINFO);
28
29  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->InitPartTmr));
30
31  switch (ctrl->IType) {
32    case IPART_GGPKL:
33      GrowBisection(ctrl, graph, tpwgts, ubfactor);
34      break;
35    case 3:
36      RandomBisection(ctrl, graph, tpwgts, ubfactor);
37      break;
38    default:
39      errexit("Unknown initial partition type: %d\n", ctrl->IType);
40  }
41
42  IFSET(ctrl->dbglvl, DBG_IPART, printf("Initial Cut: %d\n", graph->mincut));
43  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->InitPartTmr));
44  ctrl->dbglvl = dbglvl;
45
46/*
47  IsConnectedSubdomain(ctrl, graph, 0);
48  IsConnectedSubdomain(ctrl, graph, 1);
49*/
50}
51
52/*************************************************************************
53* This function computes the initial bisection of the coarsest graph
54**************************************************************************/
55void InitSeparator(CtrlType *ctrl, GraphType *graph, float ubfactor) 
56{
57  int dbglvl;
58
59  dbglvl = ctrl->dbglvl;
60  IFSET(ctrl->dbglvl, DBG_REFINE, ctrl->dbglvl -= DBG_REFINE);
61  IFSET(ctrl->dbglvl, DBG_MOVEINFO, ctrl->dbglvl -= DBG_MOVEINFO);
62
63  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->InitPartTmr));
64
65  GrowBisectionNode(ctrl, graph, ubfactor);
66  Compute2WayNodePartitionParams(ctrl, graph);
67
68  IFSET(ctrl->dbglvl, DBG_IPART, printf("Initial Sep: %d\n", graph->mincut));
69  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->InitPartTmr));
70
71  ctrl->dbglvl = dbglvl;
72
73}
74
75
76
77/*************************************************************************
78* This function takes a graph and produces a bisection by using a region
79* growing algorithm. The resulting partition is returned in
80* graph->where
81**************************************************************************/
82void GrowBisection(CtrlType *ctrl, GraphType *graph, int *tpwgts, float ubfactor)
83{
84  int i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;
85  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where;
86  idxtype *queue, *touched, *gain, *bestwhere;
87
88
89  nvtxs = graph->nvtxs;
90  xadj = graph->xadj;
91  vwgt = graph->vwgt;
92  adjncy = graph->adjncy;
93  adjwgt = graph->adjwgt;
94
95  Allocate2WayPartitionMemory(ctrl, graph);
96  where = graph->where;
97
98  bestwhere = idxmalloc(nvtxs, "BisectGraph: bestwhere");
99  queue = idxmalloc(nvtxs, "BisectGraph: queue");
100  touched = idxmalloc(nvtxs, "BisectGraph: touched");
101
102  ASSERTP(tpwgts[0]+tpwgts[1] == idxsum(nvtxs, vwgt), ("%d %d\n", tpwgts[0]+tpwgts[1], idxsum(nvtxs, vwgt)));
103
104  maxpwgt[0] = ubfactor*tpwgts[0];
105  maxpwgt[1] = ubfactor*tpwgts[1];
106  minpwgt[0] = (1.0/ubfactor)*tpwgts[0];
107  minpwgt[1] = (1.0/ubfactor)*tpwgts[1];
108
109  nbfs = (nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);
110  bestcut = idxsum(nvtxs, graph->adjwgtsum)+1;  /* The +1 is for the 0 edges case */
111  for (; nbfs>0; nbfs--) {
112    idxset(nvtxs, 0, touched);
113
114    pwgts[1] = tpwgts[0]+tpwgts[1];
115    pwgts[0] = 0;
116
117    idxset(nvtxs, 1, where);
118
119    queue[0] = RandomInRange(nvtxs);
120    touched[queue[0]] = 1;
121    first = 0; last = 1;
122    nleft = nvtxs-1;
123    drain = 0;
124
125    /* Start the BFS from queue to get a partition */
126    for (;;) {
127      if (first == last) { /* Empty. Disconnected graph! */
128        if (nleft == 0 || drain)
129          break;
130
131        k = RandomInRange(nleft);
132        for (i=0; i<nvtxs; i++) {
133          if (touched[i] == 0) {
134            if (k == 0)
135              break;
136            else
137              k--;
138          }
139        }
140
141        queue[0] = i;
142        touched[i] = 1;
143        first = 0; last = 1;;
144        nleft--;
145      }
146
147      i = queue[first++];
148      if (pwgts[0] > 0 && pwgts[1]-vwgt[i] < minpwgt[1]) {
149        drain = 1;
150        continue;
151      }
152
153      where[i] = 0;
154      INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
155      if (pwgts[1] <= maxpwgt[1])
156        break;
157
158      drain = 0;
159      for (j=xadj[i]; j<xadj[i+1]; j++) {
160        k = adjncy[j];
161        if (touched[k] == 0) {
162          queue[last++] = k;
163          touched[k] = 1;
164          nleft--;
165        }
166      }
167    }
168
169    /* Check to see if we hit any bad limiting cases */
170    if (pwgts[1] == 0) { 
171      i = RandomInRange(nvtxs);
172      where[i] = 1;
173      INC_DEC(pwgts[1], pwgts[0], vwgt[i]);
174    }
175
176    /*************************************************************
177    * Do some partition refinement
178    **************************************************************/
179    Compute2WayPartitionParams(ctrl, graph);
180    /*printf("IPART: %3d [%5d %5d] [%5d %5d] %5d\n", graph->nvtxs, pwgts[0], pwgts[1], graph->pwgts[0], graph->pwgts[1], graph->mincut); */
181
182    Balance2Way(ctrl, graph, tpwgts, ubfactor);
183    /*printf("BPART: [%5d %5d] %5d\n", graph->pwgts[0], graph->pwgts[1], graph->mincut);*/
184
185    FM_2WayEdgeRefine(ctrl, graph, tpwgts, 4);
186    /*printf("RPART: [%5d %5d] %5d\n", graph->pwgts[0], graph->pwgts[1], graph->mincut);*/
187
188    if (bestcut > graph->mincut) {
189      bestcut = graph->mincut;
190      idxcopy(nvtxs, where, bestwhere);
191      if (bestcut == 0)
192        break;
193    }
194  }
195
196  graph->mincut = bestcut;
197  idxcopy(nvtxs, bestwhere, where);
198
199  GKfree(&bestwhere, &queue, &touched, LTERM);
200}
201
202
203
204
205/*************************************************************************
206* This function takes a graph and produces a bisection by using a region
207* growing algorithm. The resulting partition is returned in
208* graph->where
209**************************************************************************/
210void GrowBisectionNode(CtrlType *ctrl, GraphType *graph, float ubfactor)
211{
212  int i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], tpwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;
213  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where, *bndind;
214  idxtype *queue, *touched, *gain, *bestwhere;
215
216  nvtxs = graph->nvtxs;
217  xadj = graph->xadj;
218  vwgt = graph->vwgt;
219  adjncy = graph->adjncy;
220  adjwgt = graph->adjwgt;
221
222  bestwhere = idxmalloc(nvtxs, "BisectGraph: bestwhere");
223  queue = idxmalloc(nvtxs, "BisectGraph: queue");
224  touched = idxmalloc(nvtxs, "BisectGraph: touched");
225
226  tpwgts[0] = idxsum(nvtxs, vwgt);
227  tpwgts[1] = tpwgts[0]/2;
228  tpwgts[0] -= tpwgts[1];
229
230  maxpwgt[0] = ubfactor*tpwgts[0];
231  maxpwgt[1] = ubfactor*tpwgts[1];
232  minpwgt[0] = (1.0/ubfactor)*tpwgts[0];
233  minpwgt[1] = (1.0/ubfactor)*tpwgts[1];
234
235  /* Allocate memory for graph->rdata. Allocate sufficient memory for both edge and node */
236  graph->rdata = idxmalloc(5*nvtxs+3, "GrowBisectionNode: graph->rdata");
237  graph->pwgts    = graph->rdata;
238  graph->where    = graph->rdata + 3;
239  graph->bndptr   = graph->rdata + nvtxs + 3;
240  graph->bndind   = graph->rdata + 2*nvtxs + 3;
241  graph->nrinfo   = (NRInfoType *)(graph->rdata + 3*nvtxs + 3);
242  graph->id       = graph->rdata + 3*nvtxs + 3;
243  graph->ed       = graph->rdata + 4*nvtxs + 3;
244 
245  where = graph->where;
246  bndind = graph->bndind;
247
248  nbfs = (nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);
249  bestcut = tpwgts[0]+tpwgts[1];
250  for (nbfs++; nbfs>0; nbfs--) {
251    idxset(nvtxs, 0, touched);
252
253    pwgts[1] = tpwgts[0]+tpwgts[1];
254    pwgts[0] = 0;
255
256    idxset(nvtxs, 1, where);
257
258    queue[0] = RandomInRange(nvtxs);
259    touched[queue[0]] = 1;
260    first = 0; last = 1;
261    nleft = nvtxs-1;
262    drain = 0;
263
264    /* Start the BFS from queue to get a partition */
265    if (nbfs >= 1) {
266      for (;;) {
267        if (first == last) { /* Empty. Disconnected graph! */
268          if (nleft == 0 || drain)
269            break;
270 
271          k = RandomInRange(nleft);
272          for (i=0; i<nvtxs; i++) {
273            if (touched[i] == 0) {
274              if (k == 0)
275                break;
276              else
277                k--;
278            }
279          }
280
281          queue[0] = i;
282          touched[i] = 1;
283          first = 0; last = 1;;
284          nleft--;
285        }
286
287        i = queue[first++];
288        if (pwgts[1]-vwgt[i] < minpwgt[1]) {
289          drain = 1;
290          continue;
291        }
292
293        where[i] = 0;
294        INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
295        if (pwgts[1] <= maxpwgt[1])
296          break;
297
298        drain = 0;
299        for (j=xadj[i]; j<xadj[i+1]; j++) {
300          k = adjncy[j];
301          if (touched[k] == 0) {
302            queue[last++] = k;
303            touched[k] = 1;
304            nleft--;
305          }
306        }
307      }
308    }
309
310    /*************************************************************
311    * Do some partition refinement
312    **************************************************************/
313    Compute2WayPartitionParams(ctrl, graph);
314    Balance2Way(ctrl, graph, tpwgts, ubfactor);
315    FM_2WayEdgeRefine(ctrl, graph, tpwgts, 4);
316
317    /* Construct and refine the vertex separator */
318    for (i=0; i<graph->nbnd; i++) 
319      where[bndind[i]] = 2;
320
321    Compute2WayNodePartitionParams(ctrl, graph); 
322    FM_2WayNodeRefine(ctrl, graph, ubfactor, 6);
323
324    /* printf("ISep: [%d %d %d] %d\n", graph->pwgts[0], graph->pwgts[1], graph->pwgts[2], bestcut); */
325
326    if (bestcut > graph->mincut) {
327      bestcut = graph->mincut;
328      idxcopy(nvtxs, where, bestwhere);
329    }
330  }
331
332  graph->mincut = bestcut;
333  idxcopy(nvtxs, bestwhere, where);
334
335  Compute2WayNodePartitionParams(ctrl, graph); 
336
337  GKfree(&bestwhere, &queue, &touched, LTERM);
338}
339
340
341/*************************************************************************
342* This function takes a graph and produces a bisection by using a region
343* growing algorithm. The resulting partition is returned in
344* graph->where
345**************************************************************************/
346void RandomBisection(CtrlType *ctrl, GraphType *graph, int *tpwgts, float ubfactor)
347{
348  int i, ii, j, k, nvtxs, pwgts[2], minpwgt[2], maxpwgt[2], from, bestcut, icut, mincut, me, pass, nbfs;
349  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *where;
350  idxtype *perm, *bestwhere;
351
352  nvtxs = graph->nvtxs;
353  xadj = graph->xadj;
354  vwgt = graph->vwgt;
355  adjncy = graph->adjncy;
356  adjwgt = graph->adjwgt;
357
358  Allocate2WayPartitionMemory(ctrl, graph);
359  where = graph->where;
360
361  bestwhere = idxmalloc(nvtxs, "BisectGraph: bestwhere");
362  perm = idxmalloc(nvtxs, "BisectGraph: queue");
363
364  ASSERTP(tpwgts[0]+tpwgts[1] == idxsum(nvtxs, vwgt), ("%d %d\n", tpwgts[0]+tpwgts[1], idxsum(nvtxs, vwgt)));
365
366  maxpwgt[0] = ubfactor*tpwgts[0];
367  maxpwgt[1] = ubfactor*tpwgts[1];
368  minpwgt[0] = (1.0/ubfactor)*tpwgts[0];
369  minpwgt[1] = (1.0/ubfactor)*tpwgts[1];
370
371  nbfs = (nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);
372  bestcut = idxsum(nvtxs, graph->adjwgtsum)+1;  /* The +1 is for the 0 edges case */
373  for (; nbfs>0; nbfs--) {
374    RandomPermute(nvtxs, perm, 1);
375
376    idxset(nvtxs, 1, where);
377    pwgts[1] = tpwgts[0]+tpwgts[1];
378    pwgts[0] = 0;
379
380
381    if (nbfs != 1) {
382      for (ii=0; ii<nvtxs; ii++) {
383        i = perm[ii];
384        if (pwgts[0]+vwgt[i] < maxpwgt[0]) {
385          where[i] = 0;
386          pwgts[0] += vwgt[i];
387          pwgts[1] -= vwgt[i];
388          if (pwgts[0] > minpwgt[0])
389            break;
390        }
391      }
392    }
393
394    /*************************************************************
395    * Do some partition refinement
396    **************************************************************/
397    Compute2WayPartitionParams(ctrl, graph);
398    /* printf("IPART: %3d [%5d %5d] [%5d %5d] %5d\n", graph->nvtxs, pwgts[0], pwgts[1], graph->pwgts[0], graph->pwgts[1], graph->mincut); */
399
400    Balance2Way(ctrl, graph, tpwgts, ubfactor);
401    /* printf("BPART: [%5d %5d] %5d\n", graph->pwgts[0], graph->pwgts[1], graph->mincut); */
402
403    FM_2WayEdgeRefine(ctrl, graph, tpwgts, 4);
404    /* printf("RPART: [%5d %5d] %5d\n", graph->pwgts[0], graph->pwgts[1], graph->mincut); */
405
406    if (bestcut > graph->mincut) {
407      bestcut = graph->mincut;
408      idxcopy(nvtxs, where, bestwhere);
409      if (bestcut == 0)
410        break;
411    }
412  }
413
414  graph->mincut = bestcut;
415  idxcopy(nvtxs, bestwhere, where);
416
417  GKfree(&bestwhere, &perm, LTERM);
418}
419
420
421
422
Note: See TracBrowser for help on using the repository browser.