Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
initpart.c
Go to the documentation of this file.
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 **************************************************************************/
21 void 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 **************************************************************************/
55 void 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 **************************************************************************/
82 void 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 **************************************************************************/
210 void 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 **************************************************************************/
346 void 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 
NRInfoType * nrinfo
Definition: struct.h:190
#define Compute2WayNodePartitionParams
Definition: rename.h:351
#define Balance2Way
Definition: rename.h:16
idxtype * pwgts
Definition: struct.h:176
idxtype * adjwgtsum
Definition: struct.h:168
#define DBG_REFINE
Definition: defs.h:157
int nbnd
Definition: struct.h:177
idxtype * ed
Definition: struct.h:181
#define RandomInRange(u)
Definition: macros.h:23
idxtype * id
Definition: struct.h:181
#define RandomBisection
Definition: rename.h:88
int IType
Definition: struct.h:218
int mincut
Definition: struct.h:175
#define DBG_MOVEINFO
Definition: defs.h:159
idxtype * bndptr
Definition: struct.h:178
idxtype * rdata
Definition: struct.h:157
#define Compute2WayPartitionParams
Definition: rename.h:330
#define IPART_GGPKL
Definition: defs.h:108
#define idxsum
Definition: rename.h:399
#define stoptimer(tmr)
Definition: macros.h:54
HitTile_Vector graph
idxtype * where
Definition: struct.h:176
#define LTERM
Definition: defs.h:18
int idxtype
Definition: struct.h:19
#define SMALLNIPARTS
Definition: defs.h:139
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define GrowBisection
Definition: rename.h:86
#define DBG_IPART
Definition: defs.h:158
#define LARGENIPARTS
Definition: defs.h:138
#define InitSeparator
Definition: rename.h:85
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define idxcopy(n, a, b)
Definition: macros.h:44
#define GrowBisectionNode
Definition: rename.h:87
int CoarsenTo
Definition: struct.h:215
void GKfree(void **ptr1,...)
Definition: util.c:121
#define ASSERTP(expr, msg)
Definition: macros.h:142
idxtype * bndind
Definition: struct.h:178
#define errexit
Definition: rename.h:379
#define FM_2WayEdgeRefine
Definition: rename.h:58
timer InitPartTmr
Definition: struct.h:230
#define FM_2WayNodeRefine
Definition: rename.h:341
idxtype * vwgt
Definition: struct.h:163
#define INC_DEC(a, b, val)
Definition: macros.h:39
#define Allocate2WayPartitionMemory
Definition: rename.h:329
#define DBG_TIME
Definition: defs.h:154
#define idxmalloc
Definition: rename.h:383
int nvtxs
Definition: struct.h:161
#define RandomPermute
Definition: rename.h:410
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define starttimer(tmr)
Definition: macros.h:53
#define Init2WayPartition
Definition: rename.h:84