1 /*!
2 \file
3 \brief Driving routines for multilevel k-way refinement
4
5 \date Started 7/28/1997
6 \author George
7 \author Copyright 1997-2009, Regents of the University of Minnesota
8 \version $Id: kwayrefine.c 10737 2011-09-13 13:37:25Z karypis $
9 */
10
11 #include "metislib.h"
12
13
14 /*************************************************************************/
15 /*! This function is the entry point of cut-based refinement */
16 /*************************************************************************/
RefineKWay(ctrl_t * ctrl,graph_t * orggraph,graph_t * graph)17 void RefineKWay(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph)
18 {
19 idx_t i, nlevels, contig=ctrl->contig;
20 graph_t *ptr;
21
22 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->UncoarsenTmr));
23
24 /* Determine how many levels are there */
25 for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++);
26
27 /* Compute the parameters of the coarsest graph */
28 ComputeKWayPartitionParams(ctrl, graph);
29
30 /* Try to minimize the sub-domain connectivity */
31 if (ctrl->minconn)
32 EliminateSubDomainEdges(ctrl, graph);
33
34 /* Deal with contiguity constraints at the beginning */
35 if (contig && FindPartitionInducedComponents(graph, graph->where, NULL, NULL) > ctrl->nparts) {
36 EliminateComponents(ctrl, graph);
37
38 ComputeKWayBoundary(ctrl, graph, BNDTYPE_BALANCE);
39 Greedy_KWayOptimize(ctrl, graph, 5, 0, OMODE_BALANCE);
40
41 ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
42 Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 0, OMODE_REFINE);
43
44 ctrl->contig = 0;
45 }
46
47 /* Refine each successively finer graph */
48 for (i=0; ;i++) {
49 if (ctrl->minconn && i == nlevels/2)
50 EliminateSubDomainEdges(ctrl, graph);
51
52 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->RefTmr));
53
54 if (2*i >= nlevels && !IsBalanced(ctrl, graph, .02)) {
55 ComputeKWayBoundary(ctrl, graph, BNDTYPE_BALANCE);
56 Greedy_KWayOptimize(ctrl, graph, 1, 0, OMODE_BALANCE);
57 ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
58 }
59
60 Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 5.0, OMODE_REFINE);
61
62 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->RefTmr));
63
64 /* Deal with contiguity constraints in the middle */
65 if (contig && i == nlevels/2) {
66 if (FindPartitionInducedComponents(graph, graph->where, NULL, NULL) > ctrl->nparts) {
67 EliminateComponents(ctrl, graph);
68
69 if (!IsBalanced(ctrl, graph, .02)) {
70 ctrl->contig = 1;
71 ComputeKWayBoundary(ctrl, graph, BNDTYPE_BALANCE);
72 Greedy_KWayOptimize(ctrl, graph, 5, 0, OMODE_BALANCE);
73
74 ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
75 Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 0, OMODE_REFINE);
76 ctrl->contig = 0;
77 }
78 }
79 }
80
81 if (graph == orggraph)
82 break;
83
84 graph = graph->finer;
85
86 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->ProjectTmr));
87 ASSERT(graph->vwgt != NULL);
88
89 ProjectKWayPartition(ctrl, graph);
90 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->ProjectTmr));
91 }
92
93 /* Deal with contiguity requirement at the end */
94 ctrl->contig = contig;
95 if (contig && FindPartitionInducedComponents(graph, graph->where, NULL, NULL) > ctrl->nparts)
96 EliminateComponents(ctrl, graph);
97
98 if (!IsBalanced(ctrl, graph, 0.0)) {
99 ComputeKWayBoundary(ctrl, graph, BNDTYPE_BALANCE);
100 Greedy_KWayOptimize(ctrl, graph, 10, 0, OMODE_BALANCE);
101
102 ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
103 Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 0, OMODE_REFINE);
104 }
105
106 if (ctrl->contig)
107 ASSERT(FindPartitionInducedComponents(graph, graph->where, NULL, NULL) == ctrl->nparts);
108
109 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->UncoarsenTmr));
110 }
111
112
113 /*************************************************************************/
114 /*! This function allocates memory for the k-way cut-based refinement */
115 /*************************************************************************/
AllocateKWayPartitionMemory(ctrl_t * ctrl,graph_t * graph)116 void AllocateKWayPartitionMemory(ctrl_t *ctrl, graph_t *graph)
117 {
118
119 graph->pwgts = imalloc(ctrl->nparts*graph->ncon, "AllocateKWayPartitionMemory: pwgts");
120 graph->where = imalloc(graph->nvtxs, "AllocateKWayPartitionMemory: where");
121 graph->bndptr = imalloc(graph->nvtxs, "AllocateKWayPartitionMemory: bndptr");
122 graph->bndind = imalloc(graph->nvtxs, "AllocateKWayPartitionMemory: bndind");
123
124 switch (ctrl->objtype) {
125 case METIS_OBJTYPE_CUT:
126 graph->ckrinfo = (ckrinfo_t *)gk_malloc(graph->nvtxs*sizeof(ckrinfo_t),
127 "AllocateKWayPartitionMemory: ckrinfo");
128 break;
129
130 case METIS_OBJTYPE_VOL:
131 graph->vkrinfo = (vkrinfo_t *)gk_malloc(graph->nvtxs*sizeof(vkrinfo_t),
132 "AllocateKWayVolPartitionMemory: vkrinfo");
133
134 /* This is to let the cut-based -minconn and -contig large-scale graph
135 changes to go through */
136 graph->ckrinfo = (ckrinfo_t *)graph->vkrinfo;
137 break;
138
139 default:
140 gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
141 }
142
143 }
144
145
146 /*************************************************************************/
147 /*! This function computes the initial id/ed for cut-based partitioning */
148 /**************************************************************************/
ComputeKWayPartitionParams(ctrl_t * ctrl,graph_t * graph)149 void ComputeKWayPartitionParams(ctrl_t *ctrl, graph_t *graph)
150 {
151 idx_t i, j, k, l, nvtxs, ncon, nparts, nbnd, mincut, me, other;
152 idx_t *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
153
154 nparts = ctrl->nparts;
155
156 nvtxs = graph->nvtxs;
157 ncon = graph->ncon;
158 xadj = graph->xadj;
159 vwgt = graph->vwgt;
160 adjncy = graph->adjncy;
161 adjwgt = graph->adjwgt;
162
163 where = graph->where;
164 pwgts = iset(nparts*ncon, 0, graph->pwgts);
165 bndind = graph->bndind;
166 bndptr = iset(nvtxs, -1, graph->bndptr);
167
168 nbnd = mincut = 0;
169
170 /* Compute pwgts */
171 if (ncon == 1) {
172 for (i=0; i<nvtxs; i++) {
173 ASSERT(where[i] >= 0 && where[i] < nparts);
174 pwgts[where[i]] += vwgt[i];
175 }
176 }
177 else {
178 for (i=0; i<nvtxs; i++) {
179 me = where[i];
180 for (j=0; j<ncon; j++)
181 pwgts[me*ncon+j] += vwgt[i*ncon+j];
182 }
183 }
184
185 /* Compute the required info for refinement */
186 switch (ctrl->objtype) {
187 case METIS_OBJTYPE_CUT:
188 {
189 ckrinfo_t *myrinfo;
190 cnbr_t *mynbrs;
191
192 memset(graph->ckrinfo, 0, sizeof(ckrinfo_t)*nvtxs);
193 cnbrpoolReset(ctrl);
194
195 for (i=0; i<nvtxs; i++) {
196 me = where[i];
197 myrinfo = graph->ckrinfo+i;
198
199 for (j=xadj[i]; j<xadj[i+1]; j++) {
200 if (me == where[adjncy[j]])
201 myrinfo->id += adjwgt[j];
202 else
203 myrinfo->ed += adjwgt[j];
204 }
205
206 /* Time to compute the particular external degrees */
207 if (myrinfo->ed > 0) {
208 mincut += myrinfo->ed;
209
210 myrinfo->inbr = cnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
211 mynbrs = ctrl->cnbrpool + myrinfo->inbr;
212
213 for (j=xadj[i]; j<xadj[i+1]; j++) {
214 other = where[adjncy[j]];
215 if (me != other) {
216 for (k=0; k<myrinfo->nnbrs; k++) {
217 if (mynbrs[k].pid == other) {
218 mynbrs[k].ed += adjwgt[j];
219 break;
220 }
221 }
222 if (k == myrinfo->nnbrs) {
223 mynbrs[k].pid = other;
224 mynbrs[k].ed = adjwgt[j];
225 myrinfo->nnbrs++;
226 }
227 }
228 }
229
230 ASSERT(myrinfo->nnbrs <= xadj[i+1]-xadj[i]);
231
232 /* Only ed-id>=0 nodes are considered to be in the boundary */
233 if (myrinfo->ed-myrinfo->id >= 0)
234 BNDInsert(nbnd, bndind, bndptr, i);
235 }
236 else {
237 myrinfo->inbr = -1;
238 }
239 }
240
241 graph->mincut = mincut/2;
242 graph->nbnd = nbnd;
243
244 }
245 ASSERT(CheckBnd2(graph));
246 break;
247
248 case METIS_OBJTYPE_VOL:
249 {
250 vkrinfo_t *myrinfo;
251 vnbr_t *mynbrs;
252
253 memset(graph->vkrinfo, 0, sizeof(vkrinfo_t)*nvtxs);
254 vnbrpoolReset(ctrl);
255
256 /* Compute now the id/ed degrees */
257 for (i=0; i<nvtxs; i++) {
258 me = where[i];
259 myrinfo = graph->vkrinfo+i;
260
261 for (j=xadj[i]; j<xadj[i+1]; j++) {
262 if (me == where[adjncy[j]])
263 myrinfo->nid++;
264 else
265 myrinfo->ned++;
266 }
267
268 /* Time to compute the particular external degrees */
269 if (myrinfo->ned > 0) {
270 mincut += myrinfo->ned;
271
272 myrinfo->inbr = vnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
273 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
274
275 for (j=xadj[i]; j<xadj[i+1]; j++) {
276 other = where[adjncy[j]];
277 if (me != other) {
278 for (k=0; k<myrinfo->nnbrs; k++) {
279 if (mynbrs[k].pid == other) {
280 mynbrs[k].ned++;
281 break;
282 }
283 }
284 if (k == myrinfo->nnbrs) {
285 mynbrs[k].gv = 0;
286 mynbrs[k].pid = other;
287 mynbrs[k].ned = 1;
288 myrinfo->nnbrs++;
289 }
290 }
291 }
292 ASSERT(myrinfo->nnbrs <= xadj[i+1]-xadj[i]);
293 }
294 else {
295 myrinfo->inbr = -1;
296 }
297 }
298 graph->mincut = mincut/2;
299
300 ComputeKWayVolGains(ctrl, graph);
301 }
302 ASSERT(graph->minvol == ComputeVolume(graph, graph->where));
303 break;
304 default:
305 gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
306 }
307
308 }
309
310
311 /*************************************************************************/
312 /*! This function projects a partition, and at the same time computes the
313 parameters for refinement. */
314 /*************************************************************************/
ProjectKWayPartition(ctrl_t * ctrl,graph_t * graph)315 void ProjectKWayPartition(ctrl_t *ctrl, graph_t *graph)
316 {
317 idx_t i, j, k, nvtxs, nbnd, nparts, me, other, istart, iend, tid, ted;
318 idx_t *xadj, *adjncy, *adjwgt;
319 idx_t *cmap, *where, *bndptr, *bndind, *cwhere, *htable;
320 graph_t *cgraph;
321
322 WCOREPUSH;
323
324 nparts = ctrl->nparts;
325
326 cgraph = graph->coarser;
327 cwhere = cgraph->where;
328
329 nvtxs = graph->nvtxs;
330 cmap = graph->cmap;
331 xadj = graph->xadj;
332 adjncy = graph->adjncy;
333 adjwgt = graph->adjwgt;
334
335 AllocateKWayPartitionMemory(ctrl, graph);
336
337 where = graph->where;
338 bndind = graph->bndind;
339 bndptr = iset(nvtxs, -1, graph->bndptr);
340
341 htable = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
342
343 /* Compute the required info for refinement */
344 switch (ctrl->objtype) {
345 case METIS_OBJTYPE_CUT:
346 ASSERT(CheckBnd2(cgraph));
347 {
348 ckrinfo_t *myrinfo;
349 cnbr_t *mynbrs;
350
351 /* go through and project partition and compute id/ed for the nodes */
352 for (i=0; i<nvtxs; i++) {
353 k = cmap[i];
354 where[i] = cwhere[k];
355 cmap[i] = cgraph->ckrinfo[k].ed; /* For optimization */
356 }
357
358 memset(graph->ckrinfo, 0, sizeof(ckrinfo_t)*nvtxs);
359 cnbrpoolReset(ctrl);
360
361 for (nbnd=0, i=0; i<nvtxs; i++) {
362 istart = xadj[i];
363 iend = xadj[i+1];
364
365 myrinfo = graph->ckrinfo+i;
366
367 if (cmap[i] == 0) { /* Interior node. Note that cmap[i] = crinfo[cmap[i]].ed */
368 for (tid=0, j=istart; j<iend; j++)
369 tid += adjwgt[j];
370
371 myrinfo->id = tid;
372 myrinfo->inbr = -1;
373 }
374 else { /* Potentially an interface node */
375 myrinfo->inbr = cnbrpoolGetNext(ctrl, iend-istart+1);
376 mynbrs = ctrl->cnbrpool + myrinfo->inbr;
377
378 me = where[i];
379 for (tid=0, ted=0, j=istart; j<iend; j++) {
380 other = where[adjncy[j]];
381 if (me == other) {
382 tid += adjwgt[j];
383 }
384 else {
385 ted += adjwgt[j];
386 if ((k = htable[other]) == -1) {
387 htable[other] = myrinfo->nnbrs;
388 mynbrs[myrinfo->nnbrs].pid = other;
389 mynbrs[myrinfo->nnbrs++].ed = adjwgt[j];
390 }
391 else {
392 mynbrs[k].ed += adjwgt[j];
393 }
394 }
395 }
396 myrinfo->id = tid;
397 myrinfo->ed = ted;
398
399 /* Remove space for edegrees if it was interior */
400 if (ted == 0) {
401 ctrl->nbrpoolcpos -= iend-istart+1;
402 myrinfo->inbr = -1;
403 }
404 else {
405 if (ted-tid >= 0)
406 BNDInsert(nbnd, bndind, bndptr, i);
407
408 for (j=0; j<myrinfo->nnbrs; j++)
409 htable[mynbrs[j].pid] = -1;
410 }
411 }
412 }
413
414 graph->nbnd = nbnd;
415
416 }
417 ASSERT(CheckBnd2(graph));
418 break;
419
420 case METIS_OBJTYPE_VOL:
421 {
422 vkrinfo_t *myrinfo;
423 vnbr_t *mynbrs;
424
425 ASSERT(cgraph->minvol == ComputeVolume(cgraph, cgraph->where));
426
427 /* go through and project partition and compute id/ed for the nodes */
428 for (i=0; i<nvtxs; i++) {
429 k = cmap[i];
430 where[i] = cwhere[k];
431 cmap[i] = cgraph->vkrinfo[k].ned; /* For optimization */
432 }
433
434 memset(graph->vkrinfo, 0, sizeof(vkrinfo_t)*nvtxs);
435 vnbrpoolReset(ctrl);
436
437 for (i=0; i<nvtxs; i++) {
438 istart = xadj[i];
439 iend = xadj[i+1];
440 myrinfo = graph->vkrinfo+i;
441
442 if (cmap[i] == 0) { /* Note that cmap[i] = crinfo[cmap[i]].ed */
443 myrinfo->nid = iend-istart;
444 myrinfo->inbr = -1;
445 }
446 else { /* Potentially an interface node */
447 myrinfo->inbr = vnbrpoolGetNext(ctrl, iend-istart+1);
448 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
449
450 me = where[i];
451 for (tid=0, ted=0, j=istart; j<iend; j++) {
452 other = where[adjncy[j]];
453 if (me == other) {
454 tid++;
455 }
456 else {
457 ted++;
458 if ((k = htable[other]) == -1) {
459 htable[other] = myrinfo->nnbrs;
460 mynbrs[myrinfo->nnbrs].gv = 0;
461 mynbrs[myrinfo->nnbrs].pid = other;
462 mynbrs[myrinfo->nnbrs++].ned = 1;
463 }
464 else {
465 mynbrs[k].ned++;
466 }
467 }
468 }
469 myrinfo->nid = tid;
470 myrinfo->ned = ted;
471
472 /* Remove space for edegrees if it was interior */
473 if (ted == 0) {
474 ctrl->nbrpoolcpos -= iend-istart+1;
475 myrinfo->inbr = -1;
476 }
477 else {
478 for (j=0; j<myrinfo->nnbrs; j++)
479 htable[mynbrs[j].pid] = -1;
480 }
481 }
482 }
483
484 ComputeKWayVolGains(ctrl, graph);
485
486 ASSERT(graph->minvol == ComputeVolume(graph, graph->where));
487 }
488 break;
489
490 default:
491 gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
492 }
493
494 graph->mincut = cgraph->mincut;
495 icopy(nparts*graph->ncon, cgraph->pwgts, graph->pwgts);
496
497 FreeGraph(&graph->coarser);
498 graph->coarser = NULL;
499
500 WCOREPOP;
501 }
502
503
504 /*************************************************************************/
505 /*! This function computes the boundary definition for balancing. */
506 /*************************************************************************/
ComputeKWayBoundary(ctrl_t * ctrl,graph_t * graph,idx_t bndtype)507 void ComputeKWayBoundary(ctrl_t *ctrl, graph_t *graph, idx_t bndtype)
508 {
509 idx_t i, nvtxs, nbnd;
510 idx_t *bndind, *bndptr;
511
512 nvtxs = graph->nvtxs;
513 bndind = graph->bndind;
514 bndptr = iset(nvtxs, -1, graph->bndptr);
515
516 nbnd = 0;
517
518 switch (ctrl->objtype) {
519 case METIS_OBJTYPE_CUT:
520 /* Compute the boundary */
521 if (bndtype == BNDTYPE_REFINE) {
522 for (i=0; i<nvtxs; i++) {
523 if (graph->ckrinfo[i].ed-graph->ckrinfo[i].id >= 0)
524 BNDInsert(nbnd, bndind, bndptr, i);
525 }
526 }
527 else { /* BNDTYPE_BALANCE */
528 for (i=0; i<nvtxs; i++) {
529 if (graph->ckrinfo[i].ed > 0)
530 BNDInsert(nbnd, bndind, bndptr, i);
531 }
532 }
533 break;
534
535 case METIS_OBJTYPE_VOL:
536 /* Compute the boundary */
537 if (bndtype == BNDTYPE_REFINE) {
538 for (i=0; i<nvtxs; i++) {
539 if (graph->vkrinfo[i].gv >= 0)
540 BNDInsert(nbnd, bndind, bndptr, i);
541 }
542 }
543 else { /* BNDTYPE_BALANCE */
544 for (i=0; i<nvtxs; i++) {
545 if (graph->vkrinfo[i].ned > 0)
546 BNDInsert(nbnd, bndind, bndptr, i);
547 }
548 }
549 break;
550
551 default:
552 gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
553 }
554
555 graph->nbnd = nbnd;
556 }
557
558
559 /*************************************************************************/
560 /*! This function computes the initial gains in the communication volume */
561 /*************************************************************************/
ComputeKWayVolGains(ctrl_t * ctrl,graph_t * graph)562 void ComputeKWayVolGains(ctrl_t *ctrl, graph_t *graph)
563 {
564 idx_t i, ii, j, k, l, nvtxs, nparts, me, other, pid;
565 idx_t *xadj, *vsize, *adjncy, *adjwgt, *where,
566 *bndind, *bndptr, *ophtable;
567 vkrinfo_t *myrinfo, *orinfo;
568 vnbr_t *mynbrs, *onbrs;
569
570 WCOREPUSH;
571
572 nparts = ctrl->nparts;
573
574 nvtxs = graph->nvtxs;
575 xadj = graph->xadj;
576 vsize = graph->vsize;
577 adjncy = graph->adjncy;
578 adjwgt = graph->adjwgt;
579
580 where = graph->where;
581 bndind = graph->bndind;
582 bndptr = iset(nvtxs, -1, graph->bndptr);
583
584 ophtable = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
585
586 /* Compute the volume gains */
587 graph->minvol = graph->nbnd = 0;
588 for (i=0; i<nvtxs; i++) {
589 myrinfo = graph->vkrinfo+i;
590 myrinfo->gv = IDX_MIN;
591
592 if (myrinfo->nnbrs > 0) {
593 me = where[i];
594 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
595
596 graph->minvol += myrinfo->nnbrs*vsize[i];
597
598 for (j=xadj[i]; j<xadj[i+1]; j++) {
599 ii = adjncy[j];
600 other = where[ii];
601 orinfo = graph->vkrinfo+ii;
602 onbrs = ctrl->vnbrpool + orinfo->inbr;
603
604 for (k=0; k<orinfo->nnbrs; k++)
605 ophtable[onbrs[k].pid] = k;
606 ophtable[other] = 1; /* this is to simplify coding */
607
608 if (me == other) {
609 /* Find which domains 'i' is connected to but 'ii' is not
610 and update their gain */
611 for (k=0; k<myrinfo->nnbrs; k++) {
612 if (ophtable[mynbrs[k].pid] == -1)
613 mynbrs[k].gv -= vsize[ii];
614 }
615 }
616 else {
617 ASSERT(ophtable[me] != -1);
618
619 if (onbrs[ophtable[me]].ned == 1) {
620 /* I'm the only connection of 'ii' in 'me' */
621 /* Increase the gains for all the common domains between 'i' and 'ii' */
622 for (k=0; k<myrinfo->nnbrs; k++) {
623 if (ophtable[mynbrs[k].pid] != -1)
624 mynbrs[k].gv += vsize[ii];
625 }
626 }
627 else {
628 /* Find which domains 'i' is connected to and 'ii' is not
629 and update their gain */
630 for (k=0; k<myrinfo->nnbrs; k++) {
631 if (ophtable[mynbrs[k].pid] == -1)
632 mynbrs[k].gv -= vsize[ii];
633 }
634 }
635 }
636
637 /* Reset the marker vector */
638 for (k=0; k<orinfo->nnbrs; k++)
639 ophtable[onbrs[k].pid] = -1;
640 ophtable[other] = -1;
641 }
642
643 /* Compute the max vgain */
644 for (k=0; k<myrinfo->nnbrs; k++) {
645 if (mynbrs[k].gv > myrinfo->gv)
646 myrinfo->gv = mynbrs[k].gv;
647 }
648
649 /* Add the extra gain due to id == 0 */
650 if (myrinfo->ned > 0 && myrinfo->nid == 0)
651 myrinfo->gv += vsize[i];
652 }
653
654 if (myrinfo->gv >= 0)
655 BNDInsert(graph->nbnd, bndind, bndptr, i);
656 }
657
658 WCOREPOP;
659 }
660
661
662 /*************************************************************************/
663 /*! This function checks if the partition weights are within the balance
664 contraints */
665 /*************************************************************************/
IsBalanced(ctrl_t * ctrl,graph_t * graph,real_t ffactor)666 int IsBalanced(ctrl_t *ctrl, graph_t *graph, real_t ffactor)
667 {
668 return
669 (ComputeLoadImbalanceDiff(graph, ctrl->nparts, ctrl->pijbm, ctrl->ubfactors)
670 <= ffactor);
671 }
672
673