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 */
13
14 #include "metislib.h"
15
16 /*************************************************************************/
17 /*! This function computes the initial bisection of the coarsest graph */
18 /*************************************************************************/
Init2WayPartition(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts,idx_t niparts)19 void Init2WayPartition(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
20 idx_t niparts)
21 {
22 mdbglvl_et dbglvl;
23
24 ASSERT(graph->tvwgt[0] >= 0);
25
26 dbglvl = ctrl->dbglvl;
27 IFSET(ctrl->dbglvl, METIS_DBG_REFINE, ctrl->dbglvl -= METIS_DBG_REFINE);
28 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, ctrl->dbglvl -= METIS_DBG_MOVEINFO);
29
30 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->InitPartTmr));
31
32 switch (ctrl->iptype) {
33 case METIS_IPTYPE_RANDOM:
34 if (graph->ncon == 1)
35 RandomBisection(ctrl, graph, ntpwgts, niparts);
36 else
37 McRandomBisection(ctrl, graph, ntpwgts, niparts);
38 break;
39
40 case METIS_IPTYPE_GROW:
41 if (graph->nedges == 0)
42 if (graph->ncon == 1)
43 RandomBisection(ctrl, graph, ntpwgts, niparts);
44 else
45 McRandomBisection(ctrl, graph, ntpwgts, niparts);
46 else
47 if (graph->ncon == 1)
48 GrowBisection(ctrl, graph, ntpwgts, niparts);
49 else
50 McGrowBisection(ctrl, graph, ntpwgts, niparts);
51 break;
52
53 default:
54 gk_errexit(SIGERR, "Unknown initial partition type: %d\n", ctrl->iptype);
55 }
56
57 IFSET(ctrl->dbglvl, METIS_DBG_IPART, printf("Initial Cut: %"PRIDX"\n", graph->mincut));
58 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->InitPartTmr));
59 ctrl->dbglvl = dbglvl;
60
61 }
62
63
64 /*************************************************************************/
65 /*! This function computes the initial separator of the coarsest graph */
66 /*************************************************************************/
InitSeparator(ctrl_t * ctrl,graph_t * graph,idx_t niparts)67 void InitSeparator(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
68 {
69 real_t ntpwgts[2] = {0.5, 0.5};
70 mdbglvl_et dbglvl;
71
72 dbglvl = ctrl->dbglvl;
73 IFSET(ctrl->dbglvl, METIS_DBG_REFINE, ctrl->dbglvl -= METIS_DBG_REFINE);
74 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, ctrl->dbglvl -= METIS_DBG_MOVEINFO);
75
76 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->InitPartTmr));
77
78 /* this is required for the cut-based part of the refinement */
79 Setup2WayBalMultipliers(ctrl, graph, ntpwgts);
80
81 switch (ctrl->iptype) {
82 case METIS_IPTYPE_EDGE:
83 if (graph->nedges == 0)
84 RandomBisection(ctrl, graph, ntpwgts, niparts);
85 else
86 GrowBisection(ctrl, graph, ntpwgts, niparts);
87
88 Compute2WayPartitionParams(ctrl, graph);
89 ConstructSeparator(ctrl, graph);
90 break;
91
92 case METIS_IPTYPE_NODE:
93 GrowBisectionNode(ctrl, graph, ntpwgts, niparts);
94 break;
95
96 default:
97 gk_errexit(SIGERR, "Unkown iptype of %"PRIDX"\n", ctrl->iptype);
98 }
99
100 IFSET(ctrl->dbglvl, METIS_DBG_IPART, printf("Initial Sep: %"PRIDX"\n", graph->mincut));
101 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->InitPartTmr));
102
103 ctrl->dbglvl = dbglvl;
104
105 }
106
107
108 /*************************************************************************/
109 /*! This function computes a bisection of a graph by randomly assigning
110 the vertices followed by a bisection refinement.
111 The resulting partition is returned in graph->where.
112 */
113 /*************************************************************************/
RandomBisection(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts,idx_t niparts)114 void RandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
115 idx_t niparts)
116 {
117 idx_t i, ii, j, k, nvtxs, pwgts[2], zeromaxpwgt, from, me,
118 bestcut=0, icut, mincut, inbfs;
119 idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where;
120 idx_t *perm, *bestwhere;
121
122 WCOREPUSH;
123
124 nvtxs = graph->nvtxs;
125 xadj = graph->xadj;
126 vwgt = graph->vwgt;
127 adjncy = graph->adjncy;
128 adjwgt = graph->adjwgt;
129
130 Allocate2WayPartitionMemory(ctrl, graph);
131 where = graph->where;
132
133 bestwhere = iwspacemalloc(ctrl, nvtxs);
134 perm = iwspacemalloc(ctrl, nvtxs);
135
136 zeromaxpwgt = ctrl->ubfactors[0]*graph->tvwgt[0]*ntpwgts[0];
137
138 for (inbfs=0; inbfs<niparts; inbfs++) {
139 iset(nvtxs, 1, where);
140
141 if (inbfs > 0) {
142 irandArrayPermute(nvtxs, perm, nvtxs/2, 1);
143 pwgts[1] = graph->tvwgt[0];
144 pwgts[0] = 0;
145
146 for (ii=0; ii<nvtxs; ii++) {
147 i = perm[ii];
148 if (pwgts[0]+vwgt[i] < zeromaxpwgt) {
149 where[i] = 0;
150 pwgts[0] += vwgt[i];
151 pwgts[1] -= vwgt[i];
152 if (pwgts[0] > zeromaxpwgt)
153 break;
154 }
155 }
156 }
157
158 /* Do some partition refinement */
159 Compute2WayPartitionParams(ctrl, graph);
160 /* printf("IPART: %3"PRIDX" [%5"PRIDX" %5"PRIDX"] [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->nvtxs, pwgts[0], pwgts[1], graph->pwgts[0], graph->pwgts[1], graph->mincut); */
161
162 Balance2Way(ctrl, graph, ntpwgts);
163 /* printf("BPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0], graph->pwgts[1], graph->mincut); */
164
165 FM_2WayRefine(ctrl, graph, ntpwgts, 4);
166 /* printf("RPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0], graph->pwgts[1], graph->mincut); */
167
168 if (inbfs==0 || bestcut > graph->mincut) {
169 bestcut = graph->mincut;
170 icopy(nvtxs, where, bestwhere);
171 if (bestcut == 0)
172 break;
173 }
174 }
175
176 graph->mincut = bestcut;
177 icopy(nvtxs, bestwhere, where);
178
179 WCOREPOP;
180 }
181
182
183 /*************************************************************************/
184 /*! This function takes a graph and produces a bisection by using a region
185 growing algorithm. The resulting bisection is refined using FM.
186 The resulting partition is returned in graph->where.
187 */
188 /*************************************************************************/
GrowBisection(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts,idx_t niparts)189 void GrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
190 idx_t niparts)
191 {
192 idx_t i, j, k, nvtxs, drain, nleft, first, last,
193 pwgts[2], oneminpwgt, onemaxpwgt,
194 from, me, bestcut=0, icut, mincut, inbfs;
195 idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where;
196 idx_t *queue, *touched, *gain, *bestwhere;
197
198 WCOREPUSH;
199
200 nvtxs = graph->nvtxs;
201 xadj = graph->xadj;
202 vwgt = graph->vwgt;
203 adjncy = graph->adjncy;
204 adjwgt = graph->adjwgt;
205
206 Allocate2WayPartitionMemory(ctrl, graph);
207 where = graph->where;
208
209 bestwhere = iwspacemalloc(ctrl, nvtxs);
210 queue = iwspacemalloc(ctrl, nvtxs);
211 touched = iwspacemalloc(ctrl, nvtxs);
212
213 onemaxpwgt = ctrl->ubfactors[0]*graph->tvwgt[0]*ntpwgts[1];
214 oneminpwgt = (1.0/ctrl->ubfactors[0])*graph->tvwgt[0]*ntpwgts[1];
215
216 for (inbfs=0; inbfs<niparts; inbfs++) {
217 iset(nvtxs, 1, where);
218
219 iset(nvtxs, 0, touched);
220
221 pwgts[1] = graph->tvwgt[0];
222 pwgts[0] = 0;
223
224
225 queue[0] = irandInRange(nvtxs);
226 touched[queue[0]] = 1;
227 first = 0;
228 last = 1;
229 nleft = nvtxs-1;
230 drain = 0;
231
232 /* Start the BFS from queue to get a partition */
233 for (;;) {
234 if (first == last) { /* Empty. Disconnected graph! */
235 if (nleft == 0 || drain)
236 break;
237
238 k = irandInRange(nleft);
239 for (i=0; i<nvtxs; i++) {
240 if (touched[i] == 0) {
241 if (k == 0)
242 break;
243 else
244 k--;
245 }
246 }
247
248 queue[0] = i;
249 touched[i] = 1;
250 first = 0;
251 last = 1;
252 nleft--;
253 }
254
255 i = queue[first++];
256 if (pwgts[0] > 0 && pwgts[1]-vwgt[i] < oneminpwgt) {
257 drain = 1;
258 continue;
259 }
260
261 where[i] = 0;
262 INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
263 if (pwgts[1] <= onemaxpwgt)
264 break;
265
266 drain = 0;
267 for (j=xadj[i]; j<xadj[i+1]; j++) {
268 k = adjncy[j];
269 if (touched[k] == 0) {
270 queue[last++] = k;
271 touched[k] = 1;
272 nleft--;
273 }
274 }
275 }
276
277 /* Check to see if we hit any bad limiting cases */
278 if (pwgts[1] == 0)
279 where[irandInRange(nvtxs)] = 1;
280 if (pwgts[0] == 0)
281 where[irandInRange(nvtxs)] = 0;
282
283 /*************************************************************
284 * Do some partition refinement
285 **************************************************************/
286 Compute2WayPartitionParams(ctrl, graph);
287 /*
288 printf("IPART: %3"PRIDX" [%5"PRIDX" %5"PRIDX"] [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n",
289 graph->nvtxs, pwgts[0], pwgts[1], graph->pwgts[0], graph->pwgts[1], graph->mincut);
290 */
291
292 Balance2Way(ctrl, graph, ntpwgts);
293 /*
294 printf("BPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0],
295 graph->pwgts[1], graph->mincut);
296 */
297
298 FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
299 /*
300 printf("RPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0],
301 graph->pwgts[1], graph->mincut);
302 */
303
304 if (inbfs == 0 || bestcut > graph->mincut) {
305 bestcut = graph->mincut;
306 icopy(nvtxs, where, bestwhere);
307 if (bestcut == 0)
308 break;
309 }
310 }
311
312 graph->mincut = bestcut;
313 icopy(nvtxs, bestwhere, where);
314
315 WCOREPOP;
316 }
317
318
319 /*************************************************************************/
320 /*! This function takes a multi-constraint graph and computes a bisection
321 by randomly assigning the vertices and then refining it. The resulting
322 partition is returned in graph->where.
323 */
324 /**************************************************************************/
McRandomBisection(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts,idx_t niparts)325 void McRandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
326 idx_t niparts)
327 {
328 idx_t i, ii, j, k, nvtxs, ncon, from, bestcut=0, mincut, inbfs, qnum;
329 idx_t *bestwhere, *where, *perm, *counts;
330 idx_t *vwgt;
331
332 WCOREPUSH;
333
334 nvtxs = graph->nvtxs;
335 ncon = graph->ncon;
336 vwgt = graph->vwgt;
337
338 Allocate2WayPartitionMemory(ctrl, graph);
339 where = graph->where;
340
341 bestwhere = iwspacemalloc(ctrl, nvtxs);
342 perm = iwspacemalloc(ctrl, nvtxs);
343 counts = iwspacemalloc(ctrl, ncon);
344
345 for (inbfs=0; inbfs<2*niparts; inbfs++) {
346 irandArrayPermute(nvtxs, perm, nvtxs/2, 1);
347 iset(ncon, 0, counts);
348
349 /* partition by spliting the queues randomly */
350 for (ii=0; ii<nvtxs; ii++) {
351 i = perm[ii];
352 qnum = iargmax(ncon, vwgt+i*ncon);
353 where[i] = (counts[qnum]++)%2;
354 }
355
356 Compute2WayPartitionParams(ctrl, graph);
357
358 FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
359 Balance2Way(ctrl, graph, ntpwgts);
360 FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
361 Balance2Way(ctrl, graph, ntpwgts);
362 FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
363
364 if (inbfs == 0 || bestcut >= graph->mincut) {
365 bestcut = graph->mincut;
366 icopy(nvtxs, where, bestwhere);
367 if (bestcut == 0)
368 break;
369 }
370 }
371
372 graph->mincut = bestcut;
373 icopy(nvtxs, bestwhere, where);
374
375 WCOREPOP;
376 }
377
378
379 /*************************************************************************/
380 /*! This function takes a multi-constraint graph and produces a bisection
381 by using a region growing algorithm. The resulting partition is
382 returned in graph->where.
383 */
384 /*************************************************************************/
McGrowBisection(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts,idx_t niparts)385 void McGrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
386 idx_t niparts)
387 {
388 idx_t i, j, k, nvtxs, ncon, from, bestcut=0, mincut, inbfs;
389 idx_t *bestwhere, *where;
390
391 WCOREPUSH;
392
393 nvtxs = graph->nvtxs;
394
395 Allocate2WayPartitionMemory(ctrl, graph);
396 where = graph->where;
397
398 bestwhere = iwspacemalloc(ctrl, nvtxs);
399
400 for (inbfs=0; inbfs<2*niparts; inbfs++) {
401 iset(nvtxs, 1, where);
402 where[irandInRange(nvtxs)] = 0;
403
404 Compute2WayPartitionParams(ctrl, graph);
405
406 Balance2Way(ctrl, graph, ntpwgts);
407 FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
408 Balance2Way(ctrl, graph, ntpwgts);
409 FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
410
411 if (inbfs == 0 || bestcut >= graph->mincut) {
412 bestcut = graph->mincut;
413 icopy(nvtxs, where, bestwhere);
414 if (bestcut == 0)
415 break;
416 }
417 }
418
419 graph->mincut = bestcut;
420 icopy(nvtxs, bestwhere, where);
421
422 WCOREPOP;
423 }
424
425
426 /*************************************************************************/
427 /* This function takes a graph and produces a tri-section into left, right,
428 and separator using a region growing algorithm. The resulting separator
429 is refined using node FM.
430 The resulting partition is returned in graph->where.
431 */
432 /**************************************************************************/
GrowBisectionNode(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts,idx_t niparts)433 void GrowBisectionNode(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
434 idx_t niparts)
435 {
436 idx_t i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], oneminpwgt,
437 onemaxpwgt, from, me, bestcut=0, icut, mincut, inbfs;
438 idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *bndind;
439 idx_t *queue, *touched, *gain, *bestwhere;
440
441 WCOREPUSH;
442
443 nvtxs = graph->nvtxs;
444 xadj = graph->xadj;
445 vwgt = graph->vwgt;
446 adjncy = graph->adjncy;
447 adjwgt = graph->adjwgt;
448
449 bestwhere = iwspacemalloc(ctrl, nvtxs);
450 queue = iwspacemalloc(ctrl, nvtxs);
451 touched = iwspacemalloc(ctrl, nvtxs);
452
453 onemaxpwgt = ctrl->ubfactors[0]*graph->tvwgt[0]*0.5;
454 oneminpwgt = (1.0/ctrl->ubfactors[0])*graph->tvwgt[0]*0.5;
455
456
457 /* Allocate refinement memory. Allocate sufficient memory for both edge and node */
458 graph->pwgts = imalloc(3, "GrowBisectionNode: pwgts");
459 graph->where = imalloc(nvtxs, "GrowBisectionNode: where");
460 graph->bndptr = imalloc(nvtxs, "GrowBisectionNode: bndptr");
461 graph->bndind = imalloc(nvtxs, "GrowBisectionNode: bndind");
462 graph->id = imalloc(nvtxs, "GrowBisectionNode: id");
463 graph->ed = imalloc(nvtxs, "GrowBisectionNode: ed");
464 graph->nrinfo = (nrinfo_t *)gk_malloc(nvtxs*sizeof(nrinfo_t), "GrowBisectionNode: nrinfo");
465
466 where = graph->where;
467 bndind = graph->bndind;
468
469 for (inbfs=0; inbfs<niparts; inbfs++) {
470 iset(nvtxs, 1, where);
471 iset(nvtxs, 0, touched);
472
473 pwgts[1] = graph->tvwgt[0];
474 pwgts[0] = 0;
475
476 queue[0] = irandInRange(nvtxs);
477 touched[queue[0]] = 1;
478 first = 0; last = 1;
479 nleft = nvtxs-1;
480 drain = 0;
481
482 /* Start the BFS from queue to get a partition */
483 for (;;) {
484 if (first == last) { /* Empty. Disconnected graph! */
485 if (nleft == 0 || drain)
486 break;
487
488 k = irandInRange(nleft);
489 for (i=0; i<nvtxs; i++) { /* select the kth untouched vertex */
490 if (touched[i] == 0) {
491 if (k == 0)
492 break;
493 else
494 k--;
495 }
496 }
497
498 queue[0] = i;
499 touched[i] = 1;
500 first = 0;
501 last = 1;
502 nleft--;
503 }
504
505 i = queue[first++];
506 if (pwgts[1]-vwgt[i] < oneminpwgt) {
507 drain = 1;
508 continue;
509 }
510
511 where[i] = 0;
512 INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
513 if (pwgts[1] <= onemaxpwgt)
514 break;
515
516 drain = 0;
517 for (j=xadj[i]; j<xadj[i+1]; j++) {
518 k = adjncy[j];
519 if (touched[k] == 0) {
520 queue[last++] = k;
521 touched[k] = 1;
522 nleft--;
523 }
524 }
525 }
526
527 /*************************************************************
528 * Do some partition refinement
529 **************************************************************/
530 Compute2WayPartitionParams(ctrl, graph);
531 Balance2Way(ctrl, graph, ntpwgts);
532 FM_2WayRefine(ctrl, graph, ntpwgts, 4);
533
534 /* Construct and refine the vertex separator */
535 for (i=0; i<graph->nbnd; i++) {
536 j = bndind[i];
537 if (xadj[j+1]-xadj[j] > 0) /* ignore islands */
538 where[j] = 2;
539 }
540
541 Compute2WayNodePartitionParams(ctrl, graph);
542 FM_2WayNodeRefine2Sided(ctrl, graph, 1);
543 FM_2WayNodeRefine1Sided(ctrl, graph, 4);
544
545 /*
546 printf("ISep: [%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"] %"PRIDX"\n",
547 inbfs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2], bestcut);
548 */
549
550 if (inbfs == 0 || bestcut > graph->mincut) {
551 bestcut = graph->mincut;
552 icopy(nvtxs, where, bestwhere);
553 }
554 }
555
556 graph->mincut = bestcut;
557 icopy(nvtxs, bestwhere, where);
558
559 WCOREPOP;
560 }
561
562
563 /*************************************************************************/
564 /* This function takes a graph and produces a tri-section into left, right,
565 and separator using a region growing algorithm. The resulting separator
566 is refined using node FM.
567 The resulting partition is returned in graph->where.
568 */
569 /**************************************************************************/
GrowBisectionNode2(ctrl_t * ctrl,graph_t * graph,real_t * ntpwgts,idx_t niparts)570 void GrowBisectionNode2(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
571 idx_t niparts)
572 {
573 idx_t i, j, k, nvtxs, bestcut=0, mincut, inbfs;
574 idx_t *xadj, *where, *bndind, *bestwhere;
575
576 WCOREPUSH;
577
578 nvtxs = graph->nvtxs;
579 xadj = graph->xadj;
580
581 /* Allocate refinement memory. Allocate sufficient memory for both edge and node */
582 graph->pwgts = imalloc(3, "GrowBisectionNode: pwgts");
583 graph->where = imalloc(nvtxs, "GrowBisectionNode: where");
584 graph->bndptr = imalloc(nvtxs, "GrowBisectionNode: bndptr");
585 graph->bndind = imalloc(nvtxs, "GrowBisectionNode: bndind");
586 graph->id = imalloc(nvtxs, "GrowBisectionNode: id");
587 graph->ed = imalloc(nvtxs, "GrowBisectionNode: ed");
588 graph->nrinfo = (nrinfo_t *)gk_malloc(nvtxs*sizeof(nrinfo_t), "GrowBisectionNode: nrinfo");
589
590 bestwhere = iwspacemalloc(ctrl, nvtxs);
591
592 where = graph->where;
593 bndind = graph->bndind;
594
595 for (inbfs=0; inbfs<niparts; inbfs++) {
596 iset(nvtxs, 1, where);
597 if (inbfs > 0)
598 where[irandInRange(nvtxs)] = 0;
599
600 Compute2WayPartitionParams(ctrl, graph);
601 General2WayBalance(ctrl, graph, ntpwgts);
602 FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
603
604 /* Construct and refine the vertex separator */
605 for (i=0; i<graph->nbnd; i++) {
606 j = bndind[i];
607 if (xadj[j+1]-xadj[j] > 0) /* ignore islands */
608 where[j] = 2;
609 }
610
611 Compute2WayNodePartitionParams(ctrl, graph);
612 FM_2WayNodeRefine2Sided(ctrl, graph, 4);
613
614 /*
615 printf("ISep: [%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"] %"PRIDX"\n",
616 inbfs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2], bestcut);
617 */
618
619 if (inbfs == 0 || bestcut > graph->mincut) {
620 bestcut = graph->mincut;
621 icopy(nvtxs, where, bestwhere);
622 }
623 }
624
625 graph->mincut = bestcut;
626 icopy(nvtxs, bestwhere, where);
627
628 WCOREPOP;
629 }
630
631