1 /*
2 * serial.c
3 *
4 * This file contains code that implements k-way refinement
5 *
6 * Started 7/28/97
7 * George
8 *
9 * $Id: serial.c 13927 2013-03-27 22:42:41Z karypis $
10 *
11 */
12
13 #include <parmetislib.h>
14
15
16 /*************************************************************************
17 * This function computes the initial id/ed
18 **************************************************************************/
Mc_ComputeSerialPartitionParams(ctrl_t * ctrl,graph_t * graph,idx_t nparts)19 void Mc_ComputeSerialPartitionParams(ctrl_t *ctrl, graph_t *graph, idx_t nparts)
20 {
21 idx_t i, j, k;
22 idx_t nvtxs, nedges, ncon, mincut, me, other;
23 idx_t *xadj, *adjncy, *adjwgt, *where;
24 ckrinfo_t *myrinfo;
25 cnbr_t *mynbrs;
26 real_t *nvwgt, *npwgts;
27 idx_t mype;
28
29 gkMPI_Comm_rank(MPI_COMM_WORLD, &mype);
30
31 nvtxs = graph->nvtxs;
32 ncon = graph->ncon;
33 xadj = graph->xadj;
34 nvwgt = graph->nvwgt;
35 adjncy = graph->adjncy;
36 adjwgt = graph->adjwgt;
37 where = graph->where;
38
39 npwgts = rset(ncon*nparts, 0.0, graph->gnpwgts);
40
41 PASSERT(ctrl, graph->ckrinfo != NULL);
42 PASSERT(ctrl, ctrl->cnbrpool != NULL);
43
44 memset(graph->ckrinfo, 0, sizeof(ckrinfo_t)*nvtxs);
45 cnbrpoolReset(ctrl);
46
47 /*------------------------------------------------------------
48 / Compute now the id/ed degrees
49 /------------------------------------------------------------*/
50 nedges = mincut = 0;
51 for (i=0; i<nvtxs; i++) {
52 me = where[i];
53 raxpy(ncon, 1.0, nvwgt+i*ncon, 1, npwgts+me*ncon, 1);
54
55 myrinfo = graph->ckrinfo+i;
56
57 for (j=xadj[i]; j<xadj[i+1]; j++) {
58 if (me == where[adjncy[j]]) {
59 myrinfo->id += adjwgt[j];
60 }
61 else {
62 myrinfo->ed += adjwgt[j];
63 }
64 }
65
66 mincut += myrinfo->ed;
67
68 /* Time to compute the particular external degrees */
69 if (myrinfo->ed > 0) {
70 myrinfo->inbr = cnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
71 mynbrs = ctrl->cnbrpool + myrinfo->inbr;
72
73 for (j=xadj[i]; j<xadj[i+1]; j++) {
74 other = where[adjncy[j]];
75 if (me != other) {
76 for (k=0; k<myrinfo->nnbrs; k++) {
77 if (mynbrs[k].pid == other) {
78 mynbrs[k].ed += adjwgt[j];
79 break;
80 }
81 }
82 if (k == myrinfo->nnbrs) {
83 mynbrs[k].pid = other;
84 mynbrs[k].ed = adjwgt[j];
85 myrinfo->nnbrs++;
86 }
87 }
88 }
89 }
90 else {
91 myrinfo->inbr = -1;
92 }
93 }
94
95 graph->mincut = mincut/2;
96
97 return;
98 }
99
100
101 /*************************************************************************
102 * This function performs k-way refinement
103 **************************************************************************/
Mc_SerialKWayAdaptRefine(ctrl_t * ctrl,graph_t * graph,idx_t nparts,idx_t * home,real_t * orgubvec,idx_t npasses)104 void Mc_SerialKWayAdaptRefine(ctrl_t *ctrl, graph_t *graph, idx_t nparts,
105 idx_t *home, real_t *orgubvec, idx_t npasses)
106 {
107 idx_t i, ii, iii, j, k;
108 idx_t nvtxs, ncon, pass, nmoves;
109 idx_t from, me, myhome, to, oldcut, gain, tmp;
110 idx_t *xadj, *adjncy, *adjwgt;
111 idx_t *where;
112 real_t *npwgts, *nvwgt, *minwgt, *maxwgt, *ubvec;
113 idx_t gain_is_greater, gain_is_same, fit_in_to, fit_in_from, going_home;
114 idx_t zero_gain, better_balance_ft, better_balance_tt;
115 ikv_t *cand;
116 idx_t mype;
117 ckrinfo_t *myrinfo;
118 cnbr_t *mynbrs;
119
120 WCOREPUSH;
121
122 gkMPI_Comm_rank(MPI_COMM_WORLD, &mype);
123
124 nvtxs = graph->nvtxs;
125 ncon = graph->ncon;
126 xadj = graph->xadj;
127 adjncy = graph->adjncy;
128 adjwgt = graph->adjwgt;
129 where = graph->where;
130 npwgts = graph->gnpwgts;
131
132 /* Setup the weight intervals of the various subdomains */
133 cand = ikvwspacemalloc(ctrl, nvtxs);
134 minwgt = rwspacemalloc(ctrl, nparts*ncon);
135 maxwgt = rwspacemalloc(ctrl, nparts*ncon);
136 ubvec = rwspacemalloc(ctrl, ncon);
137
138 ComputeHKWayLoadImbalance(ncon, nparts, npwgts, ubvec);
139 for (i=0; i<ncon; i++)
140 ubvec[i] =gk_max(ubvec[i], orgubvec[i]);
141
142 for (i=0; i<nparts; i++) {
143 for (j=0; j<ncon; j++) {
144 maxwgt[i*ncon+j] = ubvec[j]/(real_t)nparts;
145 minwgt[i*ncon+j] = ubvec[j]*(real_t)nparts;
146 }
147 }
148
149 for (pass=0; pass<npasses; pass++) {
150 oldcut = graph->mincut;
151
152 for (i=0; i<nvtxs; i++) {
153 cand[i].key = graph->ckrinfo[i].ed-graph->ckrinfo[i].id;
154 cand[i].val = i;
155 }
156 ikvsortd(nvtxs, cand);
157
158 nmoves = 0;
159 for (iii=0; iii<nvtxs; iii++) {
160 i = cand[iii].val;
161
162 myrinfo = graph->ckrinfo+i;
163
164 if (myrinfo->ed >= myrinfo->id) {
165 from = where[i];
166 myhome = home[i];
167 nvwgt = graph->nvwgt+i*ncon;
168
169 if (myrinfo->id > 0 &&
170 AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, -1.0, nvwgt, minwgt+from*ncon))
171 continue;
172
173 mynbrs = ctrl->cnbrpool + myrinfo->inbr;
174
175 for (k=myrinfo->nnbrs-1; k>=0; k--) {
176 to = mynbrs[k].pid;
177 gain = mynbrs[k].ed - myrinfo->id;
178 if (gain >= 0 &&
179 (AreAllHVwgtsBelow(ncon, 1.0, npwgts+to*ncon, 1.0, nvwgt, maxwgt+to*ncon) ||
180 IsHBalanceBetterFT(ncon,npwgts+from*ncon,npwgts+to*ncon,nvwgt,ubvec))) {
181 break;
182 }
183 }
184
185 /* break out if you did not find a candidate */
186 if (k < 0)
187 continue;
188
189 for (j=k-1; j>=0; j--) {
190 to = mynbrs[j].pid;
191 going_home = (myhome == to);
192 gain_is_same = (mynbrs[j].ed == mynbrs[k].ed);
193 gain_is_greater = (mynbrs[j].ed > mynbrs[k].ed);
194 fit_in_to = AreAllHVwgtsBelow(ncon, 1.0, npwgts+to*ncon, 1.0, nvwgt,
195 maxwgt+to*ncon);
196 better_balance_ft = IsHBalanceBetterFT(ncon, npwgts+from*ncon,
197 npwgts+to*ncon, nvwgt, ubvec);
198 better_balance_tt = IsHBalanceBetterTT(ncon, npwgts+mynbrs[k].pid*ncon,
199 npwgts+to*ncon,nvwgt,ubvec);
200
201 if (
202 (gain_is_greater &&
203 (fit_in_to ||
204 better_balance_ft)
205 )
206 ||
207 (gain_is_same &&
208 (
209 (fit_in_to &&
210 going_home)
211 ||
212 better_balance_tt
213 )
214 )
215 ) {
216 k = j;
217 }
218 }
219
220 to = mynbrs[k].pid;
221 going_home = (myhome == to);
222 zero_gain = (mynbrs[k].ed == myrinfo->id);
223
224 fit_in_from = AreAllHVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0,
225 npwgts+from*ncon, maxwgt+from*ncon);
226 better_balance_ft = IsHBalanceBetterFT(ncon, npwgts+from*ncon,
227 npwgts+to*ncon, nvwgt, ubvec);
228
229 if (zero_gain &&
230 !going_home &&
231 !better_balance_ft &&
232 fit_in_from)
233 continue;
234
235 /*=====================================================================
236 * If we got here, we can now move the vertex from 'from' to 'to'
237 *======================================================================*/
238 graph->mincut -= mynbrs[k].ed-myrinfo->id;
239
240 /* Update where, weight, and ID/ED information of the vertex you moved */
241 raxpy(ncon, 1.0, nvwgt, 1, npwgts+to*ncon, 1);
242 raxpy(ncon, -1.0, nvwgt, 1, npwgts+from*ncon, 1);
243 where[i] = to;
244 myrinfo->ed += myrinfo->id-mynbrs[k].ed;
245 gk_SWAP(myrinfo->id, mynbrs[k].ed, tmp);
246
247 if (mynbrs[k].ed == 0)
248 mynbrs[k] = mynbrs[--myrinfo->nnbrs];
249 else
250 mynbrs[k].pid = from;
251
252 /* Update the degrees of adjacent vertices */
253 for (j=xadj[i]; j<xadj[i+1]; j++) {
254 ii = adjncy[j];
255 me = where[ii];
256
257 myrinfo = graph->ckrinfo+ii;
258 if (myrinfo->inbr == -1) {
259 myrinfo->inbr = cnbrpoolGetNext(ctrl, xadj[ii+1]-xadj[ii]+1);
260 myrinfo->nnbrs = 0;
261 }
262 mynbrs = ctrl->cnbrpool + myrinfo->inbr;
263
264 if (me == from) {
265 INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
266 }
267 else {
268 if (me == to) {
269 INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
270 }
271 }
272
273 /* Remove contribution of the ed from 'from' */
274 if (me != from) {
275 for (k=0; k<myrinfo->nnbrs; k++) {
276 if (mynbrs[k].pid == from) {
277 if (mynbrs[k].ed == adjwgt[j])
278 mynbrs[k] = mynbrs[--myrinfo->nnbrs];
279 else
280 mynbrs[k].ed -= adjwgt[j];
281 break;
282 }
283 }
284 }
285
286 /* Add contribution of the ed to 'to' */
287 if (me != to) {
288 for (k=0; k<myrinfo->nnbrs; k++) {
289 if (mynbrs[k].pid == to) {
290 mynbrs[k].ed += adjwgt[j];
291 break;
292 }
293 }
294 if (k == myrinfo->nnbrs) {
295 mynbrs[k].pid = to;
296 mynbrs[k].ed = adjwgt[j];
297 myrinfo->nnbrs++;
298 }
299 }
300 }
301 nmoves++;
302 }
303 }
304
305 if (graph->mincut == oldcut)
306 break;
307 }
308
309 WCOREPOP;
310
311 return;
312 }
313
314
315
316 /*************************************************************************
317 * This function checks if the vertex weights of two vertices are below
318 * a given set of values
319 **************************************************************************/
AreAllHVwgtsBelow(idx_t ncon,real_t alpha,real_t * vwgt1,real_t beta,real_t * vwgt2,real_t * limit)320 idx_t AreAllHVwgtsBelow(idx_t ncon, real_t alpha, real_t *vwgt1, real_t beta,
321 real_t *vwgt2, real_t *limit)
322 {
323 idx_t i;
324
325 for (i=0; i<ncon; i++)
326 if (alpha*vwgt1[i] + beta*vwgt2[i] > limit[i])
327 return 0;
328
329 return 1;
330 }
331
332
333 /*************************************************************************
334 * This function computes the load imbalance over all the constrains
335 * For now assume that we just want balanced partitionings
336 **************************************************************************/
ComputeHKWayLoadImbalance(idx_t ncon,idx_t nparts,real_t * npwgts,real_t * lbvec)337 void ComputeHKWayLoadImbalance(idx_t ncon, idx_t nparts, real_t *npwgts, real_t *lbvec)
338 {
339 idx_t i, j;
340 real_t max;
341
342 for (i=0; i<ncon; i++) {
343 max = 0.0;
344 for (j=0; j<nparts; j++) {
345 if (npwgts[j*ncon+i] > max)
346 max = npwgts[j*ncon+i];
347 }
348
349 lbvec[i] = max*nparts;
350 }
351 }
352
353
354 /**************************************************************
355 * This subroutine remaps a partitioning on a single processor
356 **************************************************************/
SerialRemap(ctrl_t * ctrl,graph_t * graph,idx_t nparts,idx_t * base,idx_t * scratch,idx_t * remap,real_t * tpwgts)357 void SerialRemap(ctrl_t *ctrl, graph_t *graph, idx_t nparts,
358 idx_t *base, idx_t *scratch, idx_t *remap, real_t *tpwgts)
359 {
360 idx_t i, ii, j, k;
361 idx_t nvtxs, nmapped, max_mult;
362 idx_t from, to, current_from, smallcount, bigcount;
363 ikv_t *flowto, *bestflow;
364 i2kv_t *sortvtx;
365 idx_t *vsize, *htable, *map, *rowmap;
366
367 WCOREPUSH;
368
369 nvtxs = graph->nvtxs;
370 vsize = graph->vsize;
371 max_mult = gk_min(MAX_NPARTS_MULTIPLIER, nparts);
372
373 sortvtx = (i2kv_t *)wspacemalloc(ctrl, nvtxs*sizeof(i2kv_t));
374 flowto = ikvwspacemalloc(ctrl, nparts);
375 bestflow = ikvwspacemalloc(ctrl, nparts*max_mult);
376 map = htable = iset(2*nparts, -1, iwspacemalloc(ctrl, 2*nparts));
377 rowmap = map+nparts;
378
379 for (i=0; i<nvtxs; i++) {
380 sortvtx[i].key1 = base[i];
381 sortvtx[i].key2 = vsize[i];
382 sortvtx[i].val = i;
383 }
384
385 qsort((void *)sortvtx, (size_t)nvtxs, (size_t)sizeof(i2kv_t), SSMIncKeyCmp);
386
387 for (j=0; j<nparts; j++) {
388 flowto[j].key = 0;
389 flowto[j].val = j;
390 }
391
392 /* this step has nparts*nparts*log(nparts) computational complexity */
393 bigcount = smallcount = current_from = 0;
394 for (ii=0; ii<nvtxs; ii++) {
395 i = sortvtx[ii].val;
396 from = base[i];
397 to = scratch[i];
398
399 if (from > current_from) {
400 /* reset the hash table */
401 for (j=0; j<smallcount; j++)
402 htable[flowto[j].val] = -1;
403 ASSERT(isum(nparts, htable, 1) == -nparts);
404
405 ikvsorti(smallcount, flowto);
406
407 for (j=0; j<gk_min(smallcount, max_mult); j++, bigcount++) {
408 bestflow[bigcount].key = flowto[j].key;
409 bestflow[bigcount].val = current_from*nparts+flowto[j].val;
410 }
411
412 smallcount = 0;
413 current_from = from;
414 }
415
416 if (htable[to] == -1) {
417 htable[to] = smallcount;
418 flowto[smallcount].key = -vsize[i];
419 flowto[smallcount].val = to;
420 smallcount++;
421 }
422 else {
423 flowto[htable[to]].key += -vsize[i];
424 }
425 }
426
427 /* reset the hash table */
428 for (j=0; j<smallcount; j++)
429 htable[flowto[j].val] = -1;
430 ASSERT(isum(nparts, htable, 1) == -nparts);
431
432 ikvsorti(smallcount, flowto);
433
434 for (j=0; j<gk_min(smallcount, max_mult); j++, bigcount++) {
435 bestflow[bigcount].key = flowto[j].key;
436 bestflow[bigcount].val = current_from*nparts+flowto[j].val;
437 }
438 ikvsorti(bigcount, bestflow);
439
440 ASSERT(isum(nparts, map, 1) == -nparts);
441 ASSERT(isum(nparts, rowmap, 1) == -nparts);
442 nmapped = 0;
443
444 /* now make as many assignments as possible */
445 for (ii=0; ii<bigcount; ii++) {
446 i = bestflow[ii].val;
447 j = i % nparts; /* to */
448 k = i / nparts; /* from */
449
450 if (map[j] == -1 && rowmap[k] == -1 && SimilarTpwgts(tpwgts, graph->ncon, j, k)) {
451 map[j] = k;
452 rowmap[k] = j;
453 nmapped++;
454 }
455
456 if (nmapped == nparts)
457 break;
458 }
459
460
461 /* remap the rest */
462 /* it may help try remapping to the same label first */
463 if (nmapped < nparts) {
464 for (j=0; j<nparts && nmapped<nparts; j++) {
465 if (map[j] == -1) {
466 for (ii=0; ii<nparts; ii++) {
467 i = (j+ii) % nparts;
468 if (rowmap[i] == -1 && SimilarTpwgts(tpwgts, graph->ncon, i, j)) {
469 map[j] = i;
470 rowmap[i] = j;
471 nmapped++;
472 break;
473 }
474 }
475 }
476 }
477 }
478
479 /* check to see if remapping fails (due to dis-similar tpwgts) */
480 /* if remapping fails, revert to original mapping */
481 if (nmapped < nparts)
482 for (i=0; i<nparts; i++)
483 map[i] = i;
484
485 for (i=0; i<nvtxs; i++)
486 remap[i] = map[remap[i]];
487
488 WCOREPOP;
489 }
490
491
492 /*************************************************************************
493 * This is a comparison function for Serial Remap
494 **************************************************************************/
SSMIncKeyCmp(const void * fptr,const void * sptr)495 int SSMIncKeyCmp(const void *fptr, const void *sptr)
496 {
497 i2kv_t *first, *second;
498
499 first = (i2kv_t *)(fptr);
500 second = (i2kv_t *)(sptr);
501
502 if (first->key1 > second->key1)
503 return 1;
504
505 if (first->key1 < second->key1)
506 return -1;
507
508 if (first->key2 < second->key2)
509 return 1;
510
511 if (first->key2 > second->key2)
512 return -1;
513
514 return 0;
515 }
516
517
518 /*************************************************************************
519 * This function performs an edge-based FM refinement
520 **************************************************************************/
Mc_Serial_FM_2WayRefine(ctrl_t * ctrl,graph_t * graph,real_t * tpwgts,idx_t npasses)521 void Mc_Serial_FM_2WayRefine(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts, idx_t npasses)
522 {
523 idx_t i, ii, j, k;
524 idx_t kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass, limit, tmp, cnum;
525 idx_t *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
526 idx_t *moved, *swaps, *qnum;
527 real_t *nvwgt, *npwgts, *mindiff, *tmpdiff, origbal, minbal, newbal;
528 rpq_t **parts[2];
529 idx_t higain, mincut, initcut, newcut, mincutorder;
530 real_t *rtpwgts;
531 idx_t mype;
532
533 WCOREPUSH;
534
535 gkMPI_Comm_rank(MPI_COMM_WORLD, &mype);
536
537 nvtxs = graph->nvtxs;
538 ncon = graph->ncon;
539 xadj = graph->xadj;
540 nvwgt = graph->nvwgt;
541 adjncy = graph->adjncy;
542 adjwgt = graph->adjwgt;
543 where = graph->where;
544 id = graph->sendind;
545 ed = graph->recvind;
546 npwgts = graph->gnpwgts;
547 bndptr = graph->sendptr;
548 bndind = graph->recvptr;
549
550 mindiff = rwspacemalloc(ctrl, ncon);
551 tmpdiff = rwspacemalloc(ctrl, ncon);
552 rtpwgts = rwspacemalloc(ctrl, 2*ncon);
553 parts[0] = (rpq_t **)wspacemalloc(ctrl, sizeof(rpq_t *)*ncon);
554 parts[1] = (rpq_t **)wspacemalloc(ctrl, sizeof(rpq_t *)*ncon);
555
556 moved = iwspacemalloc(ctrl, nvtxs);
557 swaps = iwspacemalloc(ctrl, nvtxs);
558 qnum = iwspacemalloc(ctrl, nvtxs);
559
560 limit = gk_min(gk_max(0.01*nvtxs, 25), 150);
561
562 /* Initialize the queues */
563 for (i=0; i<ncon; i++) {
564 parts[0][i] = rpqCreate(nvtxs);
565 parts[1][i] = rpqCreate(nvtxs);
566 }
567 for (i=0; i<nvtxs; i++)
568 qnum[i] = rargmax(ncon, nvwgt+i*ncon);
569
570 origbal = Serial_Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);
571
572 for (i=0; i<ncon; i++) {
573 rtpwgts[i] = origbal*tpwgts[i];
574 rtpwgts[ncon+i] = origbal*tpwgts[ncon+i];
575 }
576
577 iset(nvtxs, -1, moved);
578 for (pass=0; pass<npasses; pass++) { /* Do a number of passes */
579 for (i=0; i<ncon; i++) {
580 rpqReset(parts[0][i]);
581 rpqReset(parts[1][i]);
582 }
583
584 mincutorder = -1;
585 newcut = mincut = initcut = graph->mincut;
586 for (i=0; i<ncon; i++)
587 mindiff[i] = fabs(tpwgts[i]-npwgts[i]);
588 minbal = Serial_Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);
589
590 /* Insert boundary nodes in the priority queues */
591 nbnd = graph->gnvtxs;
592 for (ii=0; ii<nbnd; ii++) {
593 i = bndind[ii];
594 rpqInsert(parts[where[i]][qnum[i]], i, (real_t)(ed[i]-id[i]));
595 }
596
597 for (nswaps=0; nswaps<nvtxs; nswaps++) {
598 Serial_SelectQueue(ncon, npwgts, rtpwgts, &from, &cnum, parts);
599 to = (from+1)%2;
600
601 if (from == -1 || (higain = rpqGetTop(parts[from][cnum])) == -1)
602 break;
603
604 raxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
605 raxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
606
607 newcut -= (ed[higain]-id[higain]);
608 newbal = Serial_Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);
609
610 if ((newcut < mincut && newbal-origbal <= .00001) ||
611 (newcut == mincut && (newbal < minbal ||
612 (newbal == minbal &&
613 Serial_BetterBalance(ncon, npwgts, tpwgts, mindiff, tmpdiff))))) {
614 mincut = newcut;
615 minbal = newbal;
616 mincutorder = nswaps;
617 for (i=0; i<ncon; i++)
618 mindiff[i] = fabs(tpwgts[i]-npwgts[i]);
619 }
620 else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
621 newcut += (ed[higain]-id[higain]);
622 raxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
623 raxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
624 break;
625 }
626
627 where[higain] = to;
628 moved[higain] = nswaps;
629 swaps[nswaps] = higain;
630
631 /**************************************************************
632 * Update the id[i]/ed[i] values of the affected nodes
633 ***************************************************************/
634 gk_SWAP(id[higain], ed[higain], tmp);
635 if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])
636 BNDDelete(nbnd, bndind, bndptr, higain);
637
638 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
639 k = adjncy[j];
640
641 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
642 INC_DEC(id[k], ed[k], kwgt);
643
644 /* Update its boundary information and queue position */
645 if (bndptr[k] != -1) { /* If k was a boundary vertex */
646 if (ed[k] == 0) { /* Not a boundary vertex any more */
647 BNDDelete(nbnd, bndind, bndptr, k);
648 if (moved[k] == -1) /* Remove it if in the queues */
649 rpqDelete(parts[where[k]][qnum[k]], k);
650 }
651 else { /* If it has not been moved, update its position in the queue */
652 if (moved[k] == -1)
653 rpqUpdate(parts[where[k]][qnum[k]], k, (real_t)(ed[k]-id[k]));
654 }
655 }
656 else {
657 if (ed[k] > 0) { /* It will now become a boundary vertex */
658 BNDInsert(nbnd, bndind, bndptr, k);
659 if (moved[k] == -1)
660 rpqInsert(parts[where[k]][qnum[k]], k, (real_t)(ed[k]-id[k]));
661 }
662 }
663 }
664 }
665
666 /****************************************************************
667 * Roll back computations
668 *****************************************************************/
669 for (i=0; i<nswaps; i++)
670 moved[swaps[i]] = -1; /* reset moved array */
671 for (nswaps--; nswaps>mincutorder; nswaps--) {
672 higain = swaps[nswaps];
673
674 to = where[higain] = (where[higain]+1)%2;
675 gk_SWAP(id[higain], ed[higain], tmp);
676 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
677 BNDDelete(nbnd, bndind, bndptr, higain);
678 else if (ed[higain] > 0 && bndptr[higain] == -1)
679 BNDInsert(nbnd, bndind, bndptr, higain);
680
681 raxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
682 raxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);
683 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
684 k = adjncy[j];
685
686 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
687 INC_DEC(id[k], ed[k], kwgt);
688
689 if (bndptr[k] != -1 && ed[k] == 0)
690 BNDDelete(nbnd, bndind, bndptr, k);
691 if (bndptr[k] == -1 && ed[k] > 0)
692 BNDInsert(nbnd, bndind, bndptr, k);
693 }
694 }
695
696 graph->mincut = mincut;
697 graph->gnvtxs = nbnd;
698
699 if (mincutorder == -1 || mincut == initcut)
700 break;
701 }
702
703 for (i=0; i<ncon; i++) {
704 rpqDestroy(parts[0][i]);
705 rpqDestroy(parts[1][i]);
706 }
707
708 WCOREPOP;
709
710 return;
711 }
712
713
714 /*************************************************************************
715 * This function selects the partition number and the queue from which
716 * we will move vertices out
717 **************************************************************************/
Serial_SelectQueue(idx_t ncon,real_t * npwgts,real_t * tpwgts,idx_t * from,idx_t * cnum,rpq_t ** queues[2])718 void Serial_SelectQueue(idx_t ncon, real_t *npwgts, real_t *tpwgts, idx_t *from,
719 idx_t *cnum, rpq_t **queues[2])
720 {
721 idx_t i, part;
722 real_t maxgain=0.0;
723 real_t max = -1.0, maxdiff=0.0;
724 idx_t mype;
725 gkMPI_Comm_rank(MPI_COMM_WORLD, &mype);
726
727 *from = -1;
728 *cnum = -1;
729
730 /* First determine the side and the queue, irrespective of the presence of nodes */
731 for (part=0; part<2; part++) {
732 for (i=0; i<ncon; i++) {
733 if (npwgts[part*ncon+i]-tpwgts[part*ncon+i] >= maxdiff) {
734 maxdiff = npwgts[part*ncon+i]-tpwgts[part*ncon+i];
735 *from = part;
736 *cnum = i;
737 }
738 }
739 }
740
741 if (*from != -1 && rpqLength(queues[*from][*cnum]) == 0) {
742 /* The desired queue is empty, select a node from that side anyway */
743 for (i=0; i<ncon; i++) {
744 if (rpqLength(queues[*from][i]) > 0) {
745 max = npwgts[(*from)*ncon + i];
746 *cnum = i;
747 break;
748 }
749 }
750
751 for (i++; i<ncon; i++) {
752 if (npwgts[(*from)*ncon + i] > max && rpqLength(queues[*from][i]) > 0) {
753 max = npwgts[(*from)*ncon + i];
754 *cnum = i;
755 }
756 }
757 }
758
759
760 /* Check to see if you can focus on the cut */
761 if (maxdiff <= 0.0 || *from == -1) {
762 maxgain = -100000.0;
763
764 for (part=0; part<2; part++) {
765 for (i=0; i<ncon; i++) {
766 if (rpqLength(queues[part][i]) > 0 &&
767 rpqSeeTopKey(queues[part][i]) > maxgain) {
768 maxgain = rpqSeeTopKey(queues[part][i]);
769 *from = part;
770 *cnum = i;
771 }
772 }
773 }
774 }
775
776 return;
777 }
778
779
780 /*************************************************************************
781 * This function checks if the balance achieved is better than the diff
782 * For now, it uses a 2-norm measure
783 **************************************************************************/
Serial_BetterBalance(idx_t ncon,real_t * npwgts,real_t * tpwgts,real_t * diff,real_t * tmpdiff)784 idx_t Serial_BetterBalance(idx_t ncon, real_t *npwgts, real_t *tpwgts,
785 real_t *diff, real_t *tmpdiff)
786 {
787 idx_t i;
788
789 for (i=0; i<ncon; i++)
790 tmpdiff[i] = fabs(tpwgts[i]-npwgts[i]);
791
792 return rnorm2(ncon, tmpdiff, 1) < rnorm2(ncon, diff, 1);
793 }
794
795
796 /*************************************************************************
797 * This function computes the load imbalance over all the constrains
798 **************************************************************************/
Serial_Compute2WayHLoadImbalance(idx_t ncon,real_t * npwgts,real_t * tpwgts)799 real_t Serial_Compute2WayHLoadImbalance(idx_t ncon, real_t *npwgts, real_t *tpwgts)
800 {
801 idx_t i;
802 real_t max=0.0, temp;
803
804 for (i=0; i<ncon; i++) {
805 if (tpwgts[i] == 0.0)
806 temp = 0.0;
807 else
808 temp = fabs(tpwgts[i]-npwgts[i])/tpwgts[i];
809 max = (max < temp ? temp : max);
810 }
811 return 1.0+max;
812 }
813
814
815
816 /*************************************************************************
817 * This function performs an edge-based FM refinement
818 **************************************************************************/
Mc_Serial_Balance2Way(ctrl_t * ctrl,graph_t * graph,real_t * tpwgts,real_t lbfactor)819 void Mc_Serial_Balance2Way(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts, real_t lbfactor)
820 {
821 idx_t i, ii, j, k, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, limit, tmp, cnum;
822 idx_t *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
823 idx_t *moved, *swaps, *qnum;
824 real_t *nvwgt, *npwgts, *mindiff, *tmpdiff, origbal, minbal, newbal;
825 rpq_t **parts[2];
826 idx_t higain, mincut, newcut, mincutorder;
827 idx_t *qsizes[2];
828
829 WCOREPUSH;
830
831 nvtxs = graph->nvtxs;
832 ncon = graph->ncon;
833 xadj = graph->xadj;
834 nvwgt = graph->nvwgt;
835 adjncy = graph->adjncy;
836 adjwgt = graph->adjwgt;
837 where = graph->where;
838 id = graph->sendind;
839 ed = graph->recvind;
840 npwgts = graph->gnpwgts;
841 bndptr = graph->sendptr;
842 bndind = graph->recvptr;
843
844 mindiff = rwspacemalloc(ctrl, ncon);
845 tmpdiff = rwspacemalloc(ctrl, ncon);
846 parts[0] = (rpq_t **)wspacemalloc(ctrl, sizeof(rpq_t *)*ncon);
847 parts[1] = (rpq_t **)wspacemalloc(ctrl, sizeof(rpq_t *)*ncon);
848 qsizes[0] = iset(ncon, 0, iwspacemalloc(ctrl, ncon));
849 qsizes[1] = iset(ncon, 0, iwspacemalloc(ctrl, ncon));
850
851 moved = iwspacemalloc(ctrl, nvtxs);
852 swaps = iwspacemalloc(ctrl, nvtxs);
853 qnum = iwspacemalloc(ctrl, nvtxs);
854
855 limit = gk_min(gk_max(0.01*nvtxs, 15), 100);
856
857 /* Initialize the queues */
858 for (i=0; i<ncon; i++) {
859 parts[0][i] = rpqCreate(nvtxs);
860 parts[1][i] = rpqCreate(nvtxs);
861 }
862
863 for (i=0; i<nvtxs; i++) {
864 qnum[i] = rargmax(ncon, nvwgt+i*ncon);
865 qsizes[qnum[i]][where[i]]++;
866 }
867
868 for (from=0; from<2; from++) {
869 for (j=0; j<ncon; j++) {
870 if (qsizes[j][from] == 0) {
871 for (i=0; i<nvtxs; i++) {
872 if (where[i] != from)
873 continue;
874
875 k = rargmax2(ncon, nvwgt+i*ncon);
876 if (k == j &&
877 qsizes[qnum[i]][from] > qsizes[j][from] &&
878 nvwgt[i*ncon+qnum[i]] < 1.3*nvwgt[i*ncon+j]) {
879 qsizes[qnum[i]][from]--;
880 qsizes[j][from]++;
881 qnum[i] = j;
882 }
883 }
884 }
885 }
886 }
887
888
889 for (i=0; i<ncon; i++)
890 mindiff[i] = fabs(tpwgts[i]-npwgts[i]);
891 minbal = origbal = Serial_Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);
892 newcut = mincut = graph->mincut;
893 mincutorder = -1;
894
895 iset(nvtxs, -1, moved);
896
897 /* Insert all nodes in the priority queues */
898 nbnd = graph->gnvtxs;
899 for (i=0; i<nvtxs; i++)
900 rpqInsert(parts[where[i]][qnum[i]], i, (real_t)(ed[i]-id[i]));
901
902 for (nswaps=0; nswaps<nvtxs; nswaps++) {
903 if (minbal < lbfactor)
904 break;
905
906 Serial_SelectQueue(ncon, npwgts, tpwgts, &from, &cnum, parts);
907 to = (from+1)%2;
908
909 if (from == -1 || (higain = rpqGetTop(parts[from][cnum])) == -1)
910 break;
911
912 raxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
913 raxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
914 newcut -= (ed[higain]-id[higain]);
915 newbal = Serial_Compute2WayHLoadImbalance(ncon, npwgts, tpwgts);
916
917 if (newbal < minbal || (newbal == minbal &&
918 (newcut < mincut || (newcut == mincut &&
919 Serial_BetterBalance(ncon, npwgts, tpwgts, mindiff, tmpdiff))))) {
920 mincut = newcut;
921 minbal = newbal;
922 mincutorder = nswaps;
923 for (i=0; i<ncon; i++)
924 mindiff[i] = fabs(tpwgts[i]-npwgts[i]);
925 }
926 else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
927 newcut += (ed[higain]-id[higain]);
928 raxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
929 raxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
930 break;
931 }
932
933 where[higain] = to;
934 moved[higain] = nswaps;
935 swaps[nswaps] = higain;
936
937 /**************************************************************
938 * Update the id[i]/ed[i] values of the affected nodes
939 ***************************************************************/
940 gk_SWAP(id[higain], ed[higain], tmp);
941 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
942 BNDDelete(nbnd, bndind, bndptr, higain);
943 if (ed[higain] > 0 && bndptr[higain] == -1)
944 BNDInsert(nbnd, bndind, bndptr, higain);
945
946 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
947 k = adjncy[j];
948
949 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
950 INC_DEC(id[k], ed[k], kwgt);
951
952 /* Update the queue position */
953 if (moved[k] == -1)
954 rpqUpdate(parts[where[k]][qnum[k]], k, (real_t)(ed[k]-id[k]));
955
956 /* Update its boundary information */
957 if (ed[k] == 0 && bndptr[k] != -1)
958 BNDDelete(nbnd, bndind, bndptr, k);
959 else if (ed[k] > 0 && bndptr[k] == -1)
960 BNDInsert(nbnd, bndind, bndptr, k);
961 }
962 }
963
964
965 /****************************************************************
966 * Roll back computations
967 *****************************************************************/
968 for (nswaps--; nswaps>mincutorder; nswaps--) {
969 higain = swaps[nswaps];
970
971 to = where[higain] = (where[higain]+1)%2;
972 gk_SWAP(id[higain], ed[higain], tmp);
973 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
974 BNDDelete(nbnd, bndind, bndptr, higain);
975 else if (ed[higain] > 0 && bndptr[higain] == -1)
976 BNDInsert(nbnd, bndind, bndptr, higain);
977
978 raxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
979 raxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+((to+1)%2)*ncon, 1);
980 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
981 k = adjncy[j];
982
983 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
984 INC_DEC(id[k], ed[k], kwgt);
985
986 if (bndptr[k] != -1 && ed[k] == 0)
987 BNDDelete(nbnd, bndind, bndptr, k);
988 if (bndptr[k] == -1 && ed[k] > 0)
989 BNDInsert(nbnd, bndind, bndptr, k);
990 }
991 }
992
993 graph->mincut = mincut;
994 graph->gnvtxs = nbnd;
995
996
997 for (i=0; i<ncon; i++) {
998 rpqDestroy(parts[0][i]);
999 rpqDestroy(parts[1][i]);
1000 }
1001
1002 WCOREPOP;
1003
1004 return;
1005 }
1006
1007
1008
1009 /*************************************************************************
1010 * This function balances two partitions by moving the highest gain
1011 * (including negative gain) vertices to the other domain.
1012 * It is used only when tha unbalance is due to non contigous
1013 * subdomains. That is, the are no boundary vertices.
1014 * It moves vertices from the domain that is overweight to the one that
1015 * is underweight.
1016 **************************************************************************/
Mc_Serial_Init2WayBalance(ctrl_t * ctrl,graph_t * graph,real_t * tpwgts)1017 void Mc_Serial_Init2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *tpwgts)
1018 {
1019 idx_t i, ii, j, k;
1020 idx_t kwgt, nvtxs, nbnd, ncon, nswaps, from, to, cnum, tmp;
1021 idx_t *xadj, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind;
1022 idx_t *qnum;
1023 real_t *nvwgt, *npwgts;
1024 rpq_t **parts[2];
1025 idx_t higain, mincut;
1026
1027 WCOREPUSH;
1028
1029 nvtxs = graph->nvtxs;
1030 ncon = graph->ncon;
1031 xadj = graph->xadj;
1032 adjncy = graph->adjncy;
1033 nvwgt = graph->nvwgt;
1034 adjwgt = graph->adjwgt;
1035 where = graph->where;
1036 id = graph->sendind;
1037 ed = graph->recvind;
1038 npwgts = graph->gnpwgts;
1039 bndptr = graph->sendptr;
1040 bndind = graph->recvptr;
1041
1042 parts[0] = (rpq_t **)wspacemalloc(ctrl, sizeof(rpq_t *)*ncon);
1043 parts[1] = (rpq_t **)wspacemalloc(ctrl, sizeof(rpq_t *)*ncon);
1044
1045 qnum = iwspacemalloc(ctrl, nvtxs);
1046
1047 /* This is called for initial partitioning so we know from where to pick nodes */
1048 from = 1;
1049 to = (from+1)%2;
1050
1051 for (i=0; i<ncon; i++) {
1052 parts[0][i] = rpqCreate(nvtxs);
1053 parts[1][i] = rpqCreate(nvtxs);
1054 }
1055
1056 /* Compute the queues in which each vertex will be assigned to */
1057 for (i=0; i<nvtxs; i++)
1058 qnum[i] = rargmax(ncon, nvwgt+i*ncon);
1059
1060 /* Insert the nodes of the proper partition in the appropriate priority queue */
1061 for (i=0; i<nvtxs; i++) {
1062 if (where[i] == from) {
1063 if (ed[i] > 0)
1064 rpqInsert(parts[0][qnum[i]], i, (real_t)(ed[i]-id[i]));
1065 else
1066 rpqInsert(parts[1][qnum[i]], i, (real_t)(ed[i]-id[i]));
1067 }
1068 }
1069
1070 mincut = graph->mincut;
1071 nbnd = graph->gnvtxs;
1072 for (nswaps=0; nswaps<nvtxs; nswaps++) {
1073 if (Serial_AreAnyVwgtsBelow(ncon, 1.0, npwgts+from*ncon, 0.0, nvwgt, tpwgts+from*ncon))
1074 break;
1075
1076 if ((cnum = Serial_SelectQueueOneWay(ncon, npwgts, tpwgts, from, parts)) == -1)
1077 break;
1078
1079
1080 if ((higain = rpqGetTop(parts[0][cnum])) == -1)
1081 higain = rpqGetTop(parts[1][cnum]);
1082
1083 mincut -= (ed[higain]-id[higain]);
1084 raxpy(ncon, 1.0, nvwgt+higain*ncon, 1, npwgts+to*ncon, 1);
1085 raxpy(ncon, -1.0, nvwgt+higain*ncon, 1, npwgts+from*ncon, 1);
1086
1087 where[higain] = to;
1088
1089 /**************************************************************
1090 * Update the id[i]/ed[i] values of the affected nodes
1091 ***************************************************************/
1092 gk_SWAP(id[higain], ed[higain], tmp);
1093 if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
1094 BNDDelete(nbnd, bndind, bndptr, higain);
1095 if (ed[higain] > 0 && bndptr[higain] == -1)
1096 BNDInsert(nbnd, bndind, bndptr, higain);
1097
1098 for (j=xadj[higain]; j<xadj[higain+1]; j++) {
1099 k = adjncy[j];
1100
1101 kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
1102 INC_DEC(id[k], ed[k], kwgt);
1103
1104 /* Update the queue position */
1105 if (where[k] == from) {
1106 if (ed[k] > 0 && bndptr[k] == -1) { /* It moves in boundary */
1107 rpqDelete(parts[1][qnum[k]], k);
1108 rpqInsert(parts[0][qnum[k]], k, (real_t)(ed[k]-id[k]));
1109 }
1110 else { /* It must be in the boundary already */
1111 rpqUpdate(parts[0][qnum[k]], k, (real_t)(ed[k]-id[k]));
1112 }
1113 }
1114
1115 /* Update its boundary information */
1116 if (ed[k] == 0 && bndptr[k] != -1)
1117 BNDDelete(nbnd, bndind, bndptr, k);
1118 else if (ed[k] > 0 && bndptr[k] == -1)
1119 BNDInsert(nbnd, bndind, bndptr, k);
1120 }
1121 }
1122
1123 graph->mincut = mincut;
1124 graph->gnvtxs = nbnd;
1125
1126 for (i=0; i<ncon; i++) {
1127 rpqDestroy(parts[0][i]);
1128 rpqDestroy(parts[1][i]);
1129 }
1130
1131 WCOREPOP;
1132 }
1133
1134
1135 /*************************************************************************
1136 * This function selects the partition number and the queue from which
1137 * we will move vertices out
1138 **************************************************************************/
Serial_SelectQueueOneWay(idx_t ncon,real_t * npwgts,real_t * tpwgts,idx_t from,rpq_t ** queues[2])1139 idx_t Serial_SelectQueueOneWay(idx_t ncon, real_t *npwgts, real_t *tpwgts,
1140 idx_t from, rpq_t **queues[2])
1141 {
1142 idx_t i, cnum=-1;
1143 real_t max=0.0;
1144
1145 for (i=0; i<ncon; i++) {
1146 if (npwgts[from*ncon+i]-tpwgts[from*ncon+i] >= max &&
1147 rpqLength(queues[0][i]) + rpqLength(queues[1][i]) > 0) {
1148 max = npwgts[from*ncon+i]-tpwgts[i];
1149 cnum = i;
1150 }
1151 }
1152
1153 return cnum;
1154 }
1155
1156
1157 /*************************************************************************
1158 * This function computes the initial id/ed
1159 **************************************************************************/
Mc_Serial_Compute2WayPartitionParams(ctrl_t * ctrl,graph_t * graph)1160 void Mc_Serial_Compute2WayPartitionParams(ctrl_t *ctrl, graph_t *graph)
1161 {
1162 idx_t i, j, me, nvtxs, ncon, nbnd, mincut;
1163 idx_t *xadj, *adjncy, *adjwgt;
1164 real_t *nvwgt, *npwgts;
1165 idx_t *id, *ed, *where;
1166 idx_t *bndptr, *bndind;
1167
1168 nvtxs = graph->nvtxs;
1169 ncon = graph->ncon;
1170 xadj = graph->xadj;
1171 nvwgt = graph->nvwgt;
1172 adjncy = graph->adjncy;
1173 adjwgt = graph->adjwgt;
1174 where = graph->where;
1175
1176 npwgts = rset(2*ncon, 0.0, graph->gnpwgts);
1177 id = iset(nvtxs, 0, graph->sendind);
1178 ed = iset(nvtxs, 0, graph->recvind);
1179 bndptr = iset(nvtxs, -1, graph->sendptr);
1180 bndind = graph->recvptr;
1181
1182 /*------------------------------------------------------------
1183 / Compute now the id/ed degrees
1184 /------------------------------------------------------------*/
1185 nbnd = mincut = 0;
1186 for (i=0; i<nvtxs; i++) {
1187 me = where[i];
1188 raxpy(ncon, 1.0, nvwgt+i*ncon, 1, npwgts+me*ncon, 1);
1189
1190 for (j=xadj[i]; j<xadj[i+1]; j++) {
1191 if (me == where[adjncy[j]])
1192 id[i] += adjwgt[j];
1193 else
1194 ed[i] += adjwgt[j];
1195 }
1196
1197 if (ed[i] > 0 || xadj[i] == xadj[i+1]) {
1198 mincut += ed[i];
1199 BNDInsert(nbnd, bndind, bndptr, i);
1200 }
1201 }
1202
1203 graph->mincut = mincut/2;
1204 graph->gnvtxs = nbnd;
1205
1206 }
1207
1208
1209 /*************************************************************************
1210 * This function checks if the vertex weights of two vertices are below
1211 * a given set of values
1212 **************************************************************************/
Serial_AreAnyVwgtsBelow(idx_t ncon,real_t alpha,real_t * vwgt1,real_t beta,real_t * vwgt2,real_t * limit)1213 idx_t Serial_AreAnyVwgtsBelow(idx_t ncon, real_t alpha, real_t *vwgt1, real_t beta, real_t *vwgt2, real_t *limit)
1214 {
1215 idx_t i;
1216
1217 for (i=0; i<ncon; i++)
1218 if (alpha*vwgt1[i] + beta*vwgt2[i] < limit[i])
1219 return 1;
1220
1221 return 0;
1222 }
1223
1224
1225 /*************************************************************************
1226 * This function computes the edge-cut of a serial graph.
1227 **************************************************************************/
ComputeSerialEdgeCut(graph_t * graph)1228 idx_t ComputeSerialEdgeCut(graph_t *graph)
1229 {
1230 idx_t i, j;
1231 idx_t cut = 0;
1232
1233 for (i=0; i<graph->nvtxs; i++) {
1234 for (j=graph->xadj[i]; j<graph->xadj[i+1]; j++)
1235 if (graph->where[i] != graph->where[graph->adjncy[j]])
1236 cut += graph->adjwgt[j];
1237 }
1238 graph->mincut = cut/2;
1239
1240 return graph->mincut;
1241 }
1242
1243
1244 /*************************************************************************
1245 * This function computes the TotalV of a serial graph.
1246 **************************************************************************/
ComputeSerialTotalV(graph_t * graph,idx_t * home)1247 idx_t ComputeSerialTotalV(graph_t *graph, idx_t *home)
1248 {
1249 idx_t i;
1250 idx_t totalv = 0;
1251
1252 for (i=0; i<graph->nvtxs; i++)
1253 if (graph->where[i] != home[i])
1254 totalv += (graph->vsize == NULL) ? graph->vwgt[i] : graph->vsize[i];
1255
1256 return totalv;
1257 }
1258
1259
1260