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 **************************************************************************/
Init2WayPartition(CtrlType * ctrl,GraphType * graph,int * tpwgts,float ubfactor)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 graclus_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 **************************************************************************/
InitSeparator(CtrlType * ctrl,GraphType * graph,float ubfactor)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 **************************************************************************/
GrowBisection(CtrlType * ctrl,GraphType * graph,int * tpwgts,float ubfactor)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] = (int) ubfactor*tpwgts[0];
105 maxpwgt[1] = (int) ubfactor*tpwgts[1];
106 minpwgt[0] = (int) (1.0/ubfactor)*tpwgts[0];
107 minpwgt[1] = (int) (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((void **) &bestwhere, (void **) &queue, (void **) &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 **************************************************************************/
GrowBisectionNode(CtrlType * ctrl,GraphType * graph,float ubfactor)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] = (int) ubfactor*tpwgts[0];
231 maxpwgt[1] = (int) ubfactor*tpwgts[1];
232 minpwgt[0] = (int) (1.0/ubfactor)*tpwgts[0];
233 minpwgt[1] = (int) (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((void **) &bestwhere, (void **) &queue, (void **) &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 **************************************************************************/
RandomBisection(CtrlType * ctrl,GraphType * graph,int * tpwgts,float ubfactor)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] = (int) ubfactor*tpwgts[0];
367 maxpwgt[1] = (int) ubfactor*tpwgts[1];
368 minpwgt[0] = (int) (1.0/ubfactor)*tpwgts[0];
369 minpwgt[1] = (int) (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((void **) &bestwhere, (void **) &perm, LTERM);
418 }
419
420
421
422
423