1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * subdomains.c
5 *
6 * This file contains functions that deal with prunning the number of
7 * adjacent subdomains in KMETIS
8 *
9 * Started 7/15/98
10 * George
11 *
12 * $Id: subdomains.c,v 1.1 1998/11/27 17:59:32 karypis Exp $
13 *
14 */
15
16 #include "metis.h"
17
18
19 /*************************************************************************
20 * This function performs k-way refinement
21 **************************************************************************/
Random_KWayEdgeRefineMConn(CtrlType * ctrl,GraphType * graph,int nparts,float * tpwgts,float ubfactor,int npasses,int ffactor)22 void Random_KWayEdgeRefineMConn(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses, int ffactor)
23 {
24 int i, ii, iii, j, jj, k, l, pass, nvtxs, nmoves, nbnd, tvwgt, myndegrees;
25 int from, me, to, oldcut, vwgt, gain;
26 int maxndoms, nadd;
27 idxtype *xadj, *adjncy, *adjwgt;
28 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
29 idxtype *phtable, *pmat, *pmatptr, *ndoms;
30 EDegreeType *myedegrees;
31 RInfoType *myrinfo;
32
33 nvtxs = graph->nvtxs;
34 xadj = graph->xadj;
35 adjncy = graph->adjncy;
36 adjwgt = graph->adjwgt;
37
38 bndptr = graph->bndptr;
39 bndind = graph->bndind;
40
41 where = graph->where;
42 pwgts = graph->pwgts;
43
44 pmat = ctrl->wspace.pmat;
45 phtable = idxwspacemalloc(ctrl, nparts);
46 ndoms = idxwspacemalloc(ctrl, nparts);
47
48 ComputeSubDomainGraph(graph, nparts, pmat, ndoms);
49
50 /* Setup the weight intervals of the various subdomains */
51 minwgt = idxwspacemalloc(ctrl, nparts);
52 maxwgt = idxwspacemalloc(ctrl, nparts);
53 itpwgts = idxwspacemalloc(ctrl, nparts);
54 tvwgt = idxsum(nparts, pwgts);
55 ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
56
57 for (i=0; i<nparts; i++) {
58 itpwgts[i] = tpwgts[i]*tvwgt;
59 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
60 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
61 }
62
63 perm = idxwspacemalloc(ctrl, nvtxs);
64
65 IFSET(ctrl->dbglvl, DBG_REFINE,
66 printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d\n",
67 pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
68 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
69 graph->mincut));
70
71 for (pass=0; pass<npasses; pass++) {
72 ASSERT(ComputeCut(graph, where) == graph->mincut);
73
74 maxndoms = ndoms[idxamax(nparts, ndoms)];
75
76 oldcut = graph->mincut;
77 nbnd = graph->nbnd;
78
79 RandomPermute(nbnd, perm, 1);
80 for (nmoves=iii=0; iii<graph->nbnd; iii++) {
81 ii = perm[iii];
82 if (ii >= nbnd)
83 continue;
84 i = bndind[ii];
85
86 myrinfo = graph->rinfo+i;
87
88 if (myrinfo->ed >= myrinfo->id) { /* Total ED is too high */
89 from = where[i];
90 vwgt = graph->vwgt[i];
91
92 if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from])
93 continue; /* This cannot be moved! */
94
95 myedegrees = myrinfo->edegrees;
96 myndegrees = myrinfo->ndegrees;
97
98 /* Determine the valid domains */
99 for (j=0; j<myndegrees; j++) {
100 to = myedegrees[j].pid;
101 phtable[to] = 1;
102 pmatptr = pmat + to*nparts;
103 for (nadd=0, k=0; k<myndegrees; k++) {
104 if (k == j)
105 continue;
106
107 l = myedegrees[k].pid;
108 if (pmatptr[l] == 0) {
109 if (ndoms[l] > maxndoms-1) {
110 phtable[to] = 0;
111 nadd = maxndoms;
112 break;
113 }
114 nadd++;
115 }
116 }
117 if (ndoms[to]+nadd > maxndoms)
118 phtable[to] = 0;
119 if (nadd == 0)
120 phtable[to] = 2;
121 }
122
123 /* Find the first valid move */
124 j = myrinfo->id;
125 for (k=0; k<myndegrees; k++) {
126 to = myedegrees[k].pid;
127 if (!phtable[to])
128 continue;
129 gain = myedegrees[k].ed-j; /* j = myrinfo->id. Allow good nodes to move */
130 if (pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain && gain >= 0)
131 break;
132 }
133 if (k == myndegrees)
134 continue; /* break out if you did not find a candidate */
135
136 for (j=k+1; j<myndegrees; j++) {
137 to = myedegrees[j].pid;
138 if (!phtable[to])
139 continue;
140 if ((myedegrees[j].ed > myedegrees[k].ed && pwgts[to]+vwgt <= maxwgt[to]) ||
141 (myedegrees[j].ed == myedegrees[k].ed &&
142 itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid]))
143 k = j;
144 }
145
146 to = myedegrees[k].pid;
147
148 j = 0;
149 if (myedegrees[k].ed-myrinfo->id > 0)
150 j = 1;
151 else if (myedegrees[k].ed-myrinfo->id == 0) {
152 if (/*(iii&7) == 0 ||*/ phtable[myedegrees[k].pid] == 2 || pwgts[from] >= maxwgt[from] || itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
153 j = 1;
154 }
155 if (j == 0)
156 continue;
157
158 /*=====================================================================
159 * If we got here, we can now move the vertex from 'from' to 'to'
160 *======================================================================*/
161 graph->mincut -= myedegrees[k].ed-myrinfo->id;
162
163 IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));
164
165 /* Update pmat to reflect the move of 'i' */
166 pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
167 pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
168 if (pmat[from*nparts+to] == 0) {
169 ndoms[from]--;
170 if (ndoms[from]+1 == maxndoms)
171 maxndoms = ndoms[idxamax(nparts, ndoms)];
172 }
173 if (pmat[to*nparts+from] == 0) {
174 ndoms[to]--;
175 if (ndoms[to]+1 == maxndoms)
176 maxndoms = ndoms[idxamax(nparts, ndoms)];
177 }
178
179 /* Update where, weight, and ID/ED information of the vertex you moved */
180 where[i] = to;
181 INC_DEC(pwgts[to], pwgts[from], vwgt);
182 myrinfo->ed += myrinfo->id-myedegrees[k].ed;
183 SWAP(myrinfo->id, myedegrees[k].ed, j);
184 if (myedegrees[k].ed == 0)
185 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
186 else
187 myedegrees[k].pid = from;
188
189 if (myrinfo->ed-myrinfo->id < 0)
190 BNDDelete(nbnd, bndind, bndptr, i);
191
192 /* Update the degrees of adjacent vertices */
193 for (j=xadj[i]; j<xadj[i+1]; j++) {
194 ii = adjncy[j];
195 me = where[ii];
196
197 myrinfo = graph->rinfo+ii;
198 if (myrinfo->edegrees == NULL) {
199 myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
200 ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
201 }
202 myedegrees = myrinfo->edegrees;
203
204 ASSERT(CheckRInfo(myrinfo));
205
206 if (me == from) {
207 INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
208
209 if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
210 BNDInsert(nbnd, bndind, bndptr, ii);
211 }
212 else if (me == to) {
213 INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
214
215 if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
216 BNDDelete(nbnd, bndind, bndptr, ii);
217 }
218
219 /* Remove contribution from the .ed of 'from' */
220 if (me != from) {
221 for (k=0; k<myrinfo->ndegrees; k++) {
222 if (myedegrees[k].pid == from) {
223 if (myedegrees[k].ed == adjwgt[j])
224 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
225 else
226 myedegrees[k].ed -= adjwgt[j];
227 break;
228 }
229 }
230 }
231
232 /* Add contribution to the .ed of 'to' */
233 if (me != to) {
234 for (k=0; k<myrinfo->ndegrees; k++) {
235 if (myedegrees[k].pid == to) {
236 myedegrees[k].ed += adjwgt[j];
237 break;
238 }
239 }
240 if (k == myrinfo->ndegrees) {
241 myedegrees[myrinfo->ndegrees].pid = to;
242 myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
243 }
244 }
245
246 /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
247 if (me != from && me != to) {
248 pmat[me*nparts+from] -= adjwgt[j];
249 pmat[from*nparts+me] -= adjwgt[j];
250 if (pmat[me*nparts+from] == 0) {
251 ndoms[me]--;
252 if (ndoms[me]+1 == maxndoms)
253 maxndoms = ndoms[idxamax(nparts, ndoms)];
254 }
255 if (pmat[from*nparts+me] == 0) {
256 ndoms[from]--;
257 if (ndoms[from]+1 == maxndoms)
258 maxndoms = ndoms[idxamax(nparts, ndoms)];
259 }
260
261 if (pmat[me*nparts+to] == 0) {
262 ndoms[me]++;
263 if (ndoms[me] > maxndoms) {
264 printf("You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms);
265 maxndoms = ndoms[me];
266 }
267 }
268 if (pmat[to*nparts+me] == 0) {
269 ndoms[to]++;
270 if (ndoms[to] > maxndoms) {
271 printf("You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms);
272 maxndoms = ndoms[to];
273 }
274 }
275 pmat[me*nparts+to] += adjwgt[j];
276 pmat[to*nparts+me] += adjwgt[j];
277 }
278
279 ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
280 ASSERT(CheckRInfo(myrinfo));
281
282 }
283 nmoves++;
284 }
285 }
286
287 graph->nbnd = nbnd;
288
289 IFSET(ctrl->dbglvl, DBG_REFINE,
290 printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %5d, Vol: %5d, %d\n",
291 pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
292 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves,
293 graph->mincut, ComputeVolume(graph, where), idxsum(nparts, ndoms)));
294
295 if (graph->mincut == oldcut)
296 break;
297 }
298
299 idxwspacefree(ctrl, nparts);
300 idxwspacefree(ctrl, nparts);
301 idxwspacefree(ctrl, nparts);
302 idxwspacefree(ctrl, nparts);
303 idxwspacefree(ctrl, nparts);
304 idxwspacefree(ctrl, nvtxs);
305 }
306
307
308
309 /*************************************************************************
310 * This function performs k-way refinement
311 **************************************************************************/
Greedy_KWayEdgeBalanceMConn(CtrlType * ctrl,GraphType * graph,int nparts,float * tpwgts,float ubfactor,int npasses)312 void Greedy_KWayEdgeBalanceMConn(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor, int npasses)
313 {
314 int i, ii, iii, j, jj, k, l, pass, nvtxs, nbnd, tvwgt, myndegrees, oldgain, gain, nmoves;
315 int from, me, to, oldcut, vwgt, maxndoms, nadd;
316 idxtype *xadj, *adjncy, *adjwgt;
317 idxtype *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *moved, *itpwgts;
318 idxtype *phtable, *pmat, *pmatptr, *ndoms;
319 EDegreeType *myedegrees;
320 RInfoType *myrinfo;
321 PQueueType queue;
322
323 nvtxs = graph->nvtxs;
324 xadj = graph->xadj;
325 adjncy = graph->adjncy;
326 adjwgt = graph->adjwgt;
327
328 bndind = graph->bndind;
329 bndptr = graph->bndptr;
330
331 where = graph->where;
332 pwgts = graph->pwgts;
333
334 pmat = ctrl->wspace.pmat;
335 phtable = idxwspacemalloc(ctrl, nparts);
336 ndoms = idxwspacemalloc(ctrl, nparts);
337
338 ComputeSubDomainGraph(graph, nparts, pmat, ndoms);
339
340
341 /* Setup the weight intervals of the various subdomains */
342 minwgt = idxwspacemalloc(ctrl, nparts);
343 maxwgt = idxwspacemalloc(ctrl, nparts);
344 itpwgts = idxwspacemalloc(ctrl, nparts);
345 tvwgt = idxsum(nparts, pwgts);
346 ASSERT(tvwgt == idxsum(nvtxs, graph->vwgt));
347
348 for (i=0; i<nparts; i++) {
349 itpwgts[i] = tpwgts[i]*tvwgt;
350 maxwgt[i] = tpwgts[i]*tvwgt*ubfactor;
351 minwgt[i] = tpwgts[i]*tvwgt*(1.0/ubfactor);
352 }
353
354 perm = idxwspacemalloc(ctrl, nvtxs);
355 moved = idxwspacemalloc(ctrl, nvtxs);
356
357 PQueueInit(ctrl, &queue, nvtxs, graph->adjwgtsum[idxamax(nvtxs, graph->adjwgtsum)]);
358
359 IFSET(ctrl->dbglvl, DBG_REFINE,
360 printf("Partitions: [%6d %6d]-[%6d %6d], Balance: %5.3f, Nv-Nb[%6d %6d]. Cut: %6d [B]\n",
361 pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)], minwgt[0], maxwgt[0],
362 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nvtxs, graph->nbnd,
363 graph->mincut));
364
365 for (pass=0; pass<npasses; pass++) {
366 ASSERT(ComputeCut(graph, where) == graph->mincut);
367
368 /* Check to see if things are out of balance, given the tolerance */
369 for (i=0; i<nparts; i++) {
370 if (pwgts[i] > maxwgt[i])
371 break;
372 }
373 if (i == nparts) /* Things are balanced. Return right away */
374 break;
375
376 PQueueReset(&queue);
377 idxset(nvtxs, -1, moved);
378
379 oldcut = graph->mincut;
380 nbnd = graph->nbnd;
381
382 RandomPermute(nbnd, perm, 1);
383 for (ii=0; ii<nbnd; ii++) {
384 i = bndind[perm[ii]];
385 PQueueInsert(&queue, i, graph->rinfo[i].ed - graph->rinfo[i].id);
386 moved[i] = 2;
387 }
388
389 maxndoms = ndoms[idxamax(nparts, ndoms)];
390
391 for (nmoves=0;;) {
392 if ((i = PQueueGetMax(&queue)) == -1)
393 break;
394 moved[i] = 1;
395
396 myrinfo = graph->rinfo+i;
397 from = where[i];
398 vwgt = graph->vwgt[i];
399
400 if (pwgts[from]-vwgt < minwgt[from])
401 continue; /* This cannot be moved! */
402
403 myedegrees = myrinfo->edegrees;
404 myndegrees = myrinfo->ndegrees;
405
406 /* Determine the valid domains */
407 for (j=0; j<myndegrees; j++) {
408 to = myedegrees[j].pid;
409 phtable[to] = 1;
410 pmatptr = pmat + to*nparts;
411 for (nadd=0, k=0; k<myndegrees; k++) {
412 if (k == j)
413 continue;
414
415 l = myedegrees[k].pid;
416 if (pmatptr[l] == 0) {
417 if (ndoms[l] > maxndoms-1) {
418 phtable[to] = 0;
419 nadd = maxndoms;
420 break;
421 }
422 nadd++;
423 }
424 }
425 if (ndoms[to]+nadd > maxndoms)
426 phtable[to] = 0;
427 }
428
429 for (k=0; k<myndegrees; k++) {
430 to = myedegrees[k].pid;
431 if (!phtable[to])
432 continue;
433 if (pwgts[to]+vwgt <= maxwgt[to] || itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from])
434 break;
435 }
436 if (k == myndegrees)
437 continue; /* break out if you did not find a candidate */
438
439 for (j=k+1; j<myndegrees; j++) {
440 to = myedegrees[j].pid;
441 if (!phtable[to])
442 continue;
443 if (itpwgts[myedegrees[k].pid]*pwgts[to] < itpwgts[to]*pwgts[myedegrees[k].pid])
444 k = j;
445 }
446
447 to = myedegrees[k].pid;
448
449 if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] && myedegrees[k].ed-myrinfo->id < 0)
450 continue;
451
452 /*=====================================================================
453 * If we got here, we can now move the vertex from 'from' to 'to'
454 *======================================================================*/
455 graph->mincut -= myedegrees[k].ed-myrinfo->id;
456
457 IFSET(ctrl->dbglvl, DBG_MOVEINFO, printf("\t\tMoving %6d to %3d. Gain: %4d. Cut: %6d\n", i, to, myedegrees[k].ed-myrinfo->id, graph->mincut));
458
459 /* Update pmat to reflect the move of 'i' */
460 pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
461 pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
462 if (pmat[from*nparts+to] == 0) {
463 ndoms[from]--;
464 if (ndoms[from]+1 == maxndoms)
465 maxndoms = ndoms[idxamax(nparts, ndoms)];
466 }
467 if (pmat[to*nparts+from] == 0) {
468 ndoms[to]--;
469 if (ndoms[to]+1 == maxndoms)
470 maxndoms = ndoms[idxamax(nparts, ndoms)];
471 }
472
473
474 /* Update where, weight, and ID/ED information of the vertex you moved */
475 where[i] = to;
476 INC_DEC(pwgts[to], pwgts[from], vwgt);
477 myrinfo->ed += myrinfo->id-myedegrees[k].ed;
478 SWAP(myrinfo->id, myedegrees[k].ed, j);
479 if (myedegrees[k].ed == 0)
480 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
481 else
482 myedegrees[k].pid = from;
483
484 if (myrinfo->ed == 0)
485 BNDDelete(nbnd, bndind, bndptr, i);
486
487 /* Update the degrees of adjacent vertices */
488 for (j=xadj[i]; j<xadj[i+1]; j++) {
489 ii = adjncy[j];
490 me = where[ii];
491
492 myrinfo = graph->rinfo+ii;
493 if (myrinfo->edegrees == NULL) {
494 myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
495 ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
496 }
497 myedegrees = myrinfo->edegrees;
498
499 ASSERT(CheckRInfo(myrinfo));
500
501 oldgain = (myrinfo->ed-myrinfo->id);
502
503 if (me == from) {
504 INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
505
506 if (myrinfo->ed > 0 && bndptr[ii] == -1)
507 BNDInsert(nbnd, bndind, bndptr, ii);
508 }
509 else if (me == to) {
510 INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
511
512 if (myrinfo->ed == 0 && bndptr[ii] != -1)
513 BNDDelete(nbnd, bndind, bndptr, ii);
514 }
515
516 /* Remove contribution from the .ed of 'from' */
517 if (me != from) {
518 for (k=0; k<myrinfo->ndegrees; k++) {
519 if (myedegrees[k].pid == from) {
520 if (myedegrees[k].ed == adjwgt[j])
521 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
522 else
523 myedegrees[k].ed -= adjwgt[j];
524 break;
525 }
526 }
527 }
528
529 /* Add contribution to the .ed of 'to' */
530 if (me != to) {
531 for (k=0; k<myrinfo->ndegrees; k++) {
532 if (myedegrees[k].pid == to) {
533 myedegrees[k].ed += adjwgt[j];
534 break;
535 }
536 }
537 if (k == myrinfo->ndegrees) {
538 myedegrees[myrinfo->ndegrees].pid = to;
539 myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
540 }
541 }
542
543 /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
544 if (me != from && me != to) {
545 pmat[me*nparts+from] -= adjwgt[j];
546 pmat[from*nparts+me] -= adjwgt[j];
547 if (pmat[me*nparts+from] == 0) {
548 ndoms[me]--;
549 if (ndoms[me]+1 == maxndoms)
550 maxndoms = ndoms[idxamax(nparts, ndoms)];
551 }
552 if (pmat[from*nparts+me] == 0) {
553 ndoms[from]--;
554 if (ndoms[from]+1 == maxndoms)
555 maxndoms = ndoms[idxamax(nparts, ndoms)];
556 }
557
558 if (pmat[me*nparts+to] == 0) {
559 ndoms[me]++;
560 if (ndoms[me] > maxndoms) {
561 printf("You just increased the maxndoms: %d %d\n", ndoms[me], maxndoms);
562 maxndoms = ndoms[me];
563 }
564 }
565 if (pmat[to*nparts+me] == 0) {
566 ndoms[to]++;
567 if (ndoms[to] > maxndoms) {
568 printf("You just increased the maxndoms: %d %d\n", ndoms[to], maxndoms);
569 maxndoms = ndoms[to];
570 }
571 }
572 pmat[me*nparts+to] += adjwgt[j];
573 pmat[to*nparts+me] += adjwgt[j];
574 }
575
576 /* Update the queue */
577 if (me == to || me == from) {
578 gain = myrinfo->ed-myrinfo->id;
579 if (moved[ii] == 2) {
580 if (myrinfo->ed > 0)
581 PQueueUpdate(&queue, ii, oldgain, gain);
582 else {
583 PQueueDelete(&queue, ii, oldgain);
584 moved[ii] = -1;
585 }
586 }
587 else if (moved[ii] == -1 && myrinfo->ed > 0) {
588 PQueueInsert(&queue, ii, gain);
589 moved[ii] = 2;
590 }
591 }
592
593 ASSERT(myrinfo->ndegrees <= xadj[ii+1]-xadj[ii]);
594 ASSERT(CheckRInfo(myrinfo));
595 }
596 nmoves++;
597 }
598
599 graph->nbnd = nbnd;
600
601 IFSET(ctrl->dbglvl, DBG_REFINE,
602 printf("\t[%6d %6d], Balance: %5.3f, Nb: %6d. Nmoves: %5d, Cut: %6d, %d\n",
603 pwgts[idxamin(nparts, pwgts)], pwgts[idxamax(nparts, pwgts)],
604 1.0*nparts*pwgts[idxamax(nparts, pwgts)]/tvwgt, graph->nbnd, nmoves, graph->mincut,idxsum(nparts, ndoms)));
605 }
606
607 PQueueFree(ctrl, &queue);
608
609 idxwspacefree(ctrl, nparts);
610 idxwspacefree(ctrl, nparts);
611 idxwspacefree(ctrl, nparts);
612 idxwspacefree(ctrl, nparts);
613 idxwspacefree(ctrl, nparts);
614 idxwspacefree(ctrl, nvtxs);
615 idxwspacefree(ctrl, nvtxs);
616
617 }
618
619
620
621
622 /*************************************************************************
623 * This function computes the subdomain graph
624 **************************************************************************/
PrintSubDomainGraph(GraphType * graph,int nparts,idxtype * where)625 void PrintSubDomainGraph(GraphType *graph, int nparts, idxtype *where)
626 {
627 int i, j, k, me, nvtxs, total, max;
628 idxtype *xadj, *adjncy, *adjwgt, *pmat;
629
630 nvtxs = graph->nvtxs;
631 xadj = graph->xadj;
632 adjncy = graph->adjncy;
633 adjwgt = graph->adjwgt;
634
635 pmat = idxsmalloc(nparts*nparts, 0, "ComputeSubDomainGraph: pmat");
636
637 for (i=0; i<nvtxs; i++) {
638 me = where[i];
639 for (j=xadj[i]; j<xadj[i+1]; j++) {
640 k = adjncy[j];
641 if (where[k] != me)
642 pmat[me*nparts+where[k]] += adjwgt[j];
643 }
644 }
645
646 /* printf("Subdomain Info\n"); */
647 total = max = 0;
648 for (i=0; i<nparts; i++) {
649 for (k=0, j=0; j<nparts; j++) {
650 if (pmat[i*nparts+j] > 0)
651 k++;
652 }
653 total += k;
654
655 if (k > max)
656 max = k;
657 /*
658 printf("%2d -> %2d ", i, k);
659 for (j=0; j<nparts; j++) {
660 if (pmat[i*nparts+j] > 0)
661 printf("[%2d %4d] ", j, pmat[i*nparts+j]);
662 }
663 printf("\n");
664 */
665 }
666 printf("Total adjacent subdomains: %d, Max: %d\n", total, max);
667
668 free(pmat);
669 }
670
671
672
673 /*************************************************************************
674 * This function computes the subdomain graph
675 **************************************************************************/
ComputeSubDomainGraph(GraphType * graph,int nparts,idxtype * pmat,idxtype * ndoms)676 void ComputeSubDomainGraph(GraphType *graph, int nparts, idxtype *pmat, idxtype *ndoms)
677 {
678 int i, j, k, me, nvtxs, ndegrees;
679 idxtype *xadj, *adjncy, *adjwgt, *where;
680 RInfoType *rinfo;
681 EDegreeType *edegrees;
682
683 nvtxs = graph->nvtxs;
684 xadj = graph->xadj;
685 adjncy = graph->adjncy;
686 adjwgt = graph->adjwgt;
687 where = graph->where;
688 rinfo = graph->rinfo;
689
690 idxset(nparts*nparts, 0, pmat);
691
692 for (i=0; i<nvtxs; i++) {
693 if (rinfo[i].ed > 0) {
694 me = where[i];
695 ndegrees = rinfo[i].ndegrees;
696 edegrees = rinfo[i].edegrees;
697
698 k = me*nparts;
699 for (j=0; j<ndegrees; j++)
700 pmat[k+edegrees[j].pid] += edegrees[j].ed;
701 }
702 }
703
704 for (i=0; i<nparts; i++) {
705 ndoms[i] = 0;
706 for (j=0; j<nparts; j++) {
707 if (pmat[i*nparts+j] > 0)
708 ndoms[i]++;
709 }
710 }
711
712 }
713
714
715
716
717
718 /*************************************************************************
719 * This function computes the subdomain graph
720 **************************************************************************/
EliminateSubDomainEdges(CtrlType * ctrl,GraphType * graph,int nparts,float * tpwgts)721 void EliminateSubDomainEdges(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts)
722 {
723 int i, ii, j, k, me, other, nvtxs, total, max, avg, totalout, nind, ncand, ncand2, target, target2, nadd;
724 int min, move, cpwgt, tvwgt;
725 idxtype *xadj, *adjncy, *vwgt, *adjwgt, *pwgts, *where, *maxpwgt, *pmat, *ndoms, *mypmat, *otherpmat, *ind;
726 KeyValueType *cand, *cand2;
727
728 nvtxs = graph->nvtxs;
729 xadj = graph->xadj;
730 adjncy = graph->adjncy;
731 vwgt = graph->vwgt;
732 adjwgt = graph->adjwgt;
733
734 where = graph->where;
735 pwgts = graph->pwgts; /* We assume that this is properly initialized */
736
737 maxpwgt = idxwspacemalloc(ctrl, nparts);
738 ndoms = idxwspacemalloc(ctrl, nparts);
739 otherpmat = idxwspacemalloc(ctrl, nparts);
740 ind = idxwspacemalloc(ctrl, nvtxs);
741 pmat = ctrl->wspace.pmat;
742
743 cand = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand");
744 cand2 = (KeyValueType *)GKmalloc(nparts*sizeof(KeyValueType), "EliminateSubDomainEdges: cand");
745
746 /* Compute the pmat matrix and ndoms */
747 ComputeSubDomainGraph(graph, nparts, pmat, ndoms);
748
749
750 /* Compute the maximum allowed weight for each domain */
751 tvwgt = idxsum(nparts, pwgts);
752 for (i=0; i<nparts; i++)
753 maxpwgt[i] = 1.25*tpwgts[i]*tvwgt;
754
755
756 /* Get into the loop eliminating subdomain connections */
757 for (;;) {
758 total = idxsum(nparts, ndoms);
759 avg = total/nparts;
760 max = ndoms[idxamax(nparts, ndoms)];
761
762 /* printf("Adjacent Subdomain Stats: Total: %3d, Max: %3d, Avg: %3d [%5d]\n", total, max, avg, idxsum(nparts*nparts, pmat)); */
763
764 if (max < 1.4*avg)
765 break;
766
767 me = idxamax(nparts, ndoms);
768 mypmat = pmat + me*nparts;
769 totalout = idxsum(nparts, mypmat);
770
771 /*printf("Me: %d, TotalOut: %d,\n", me, totalout);*/
772
773 /* Sort the connections according to their cut */
774 for (ncand2=0, i=0; i<nparts; i++) {
775 if (mypmat[i] > 0) {
776 cand2[ncand2].key = mypmat[i];
777 cand2[ncand2++].val = i;
778 }
779 }
780 ikeysort(ncand2, cand2);
781
782 move = 0;
783 for (min=0; min<ncand2; min++) {
784 if (cand2[min].key > totalout/(2*ndoms[me]))
785 break;
786
787 other = cand2[min].val;
788
789 /*printf("\tMinOut: %d to %d\n", mypmat[other], other);*/
790
791 idxset(nparts, 0, otherpmat);
792
793 /* Go and find the vertices in 'other' that are connected in 'me' */
794 for (nind=0, i=0; i<nvtxs; i++) {
795 if (where[i] == other) {
796 for (j=xadj[i]; j<xadj[i+1]; j++) {
797 if (where[adjncy[j]] == me) {
798 ind[nind++] = i;
799 break;
800 }
801 }
802 }
803 }
804
805 /* Go and construct the otherpmat to see where these nind vertices are connected to */
806 for (cpwgt=0, ii=0; ii<nind; ii++) {
807 i = ind[ii];
808 cpwgt += vwgt[i];
809
810 for (j=xadj[i]; j<xadj[i+1]; j++)
811 otherpmat[where[adjncy[j]]] += adjwgt[j];
812 }
813 otherpmat[other] = 0;
814
815 for (ncand=0, i=0; i<nparts; i++) {
816 if (otherpmat[i] > 0) {
817 cand[ncand].key = -otherpmat[i];
818 cand[ncand++].val = i;
819 }
820 }
821 ikeysort(ncand, cand);
822
823 /*
824 * Go through and the select the first domain that is common with 'me', and
825 * does not increase the ndoms[target] higher than my ndoms, subject to the
826 * maxpwgt constraint. Traversal is done from the mostly connected to the least.
827 */
828 target = target2 = -1;
829 for (i=0; i<ncand; i++) {
830 k = cand[i].val;
831
832 if (mypmat[k] > 0) {
833 if (pwgts[k] + cpwgt > maxpwgt[k]) /* Check if balance will go off */
834 continue;
835
836 for (j=0; j<nparts; j++) {
837 if (otherpmat[j] > 0 && ndoms[j] >= ndoms[me]-1 && pmat[nparts*j+k] == 0)
838 break;
839 }
840 if (j == nparts) { /* No bad second level effects */
841 for (nadd=0, j=0; j<nparts; j++) {
842 if (otherpmat[j] > 0 && pmat[nparts*k+j] == 0)
843 nadd++;
844 }
845
846 /*printf("\t\tto=%d, nadd=%d, %d\n", k, nadd, ndoms[k]);*/
847 if (target2 == -1 && ndoms[k]+nadd < ndoms[me]) {
848 target2 = k;
849 }
850 if (nadd == 0) {
851 target = k;
852 break;
853 }
854 }
855 }
856 }
857 if (target == -1 && target2 != -1)
858 target = target2;
859
860 if (target == -1) {
861 /* printf("\t\tCould not make the move\n");*/
862 continue;
863 }
864
865 /*printf("\t\tMoving to %d\n", target);*/
866
867 /* Update the partition weights */
868 INC_DEC(pwgts[target], pwgts[other], cpwgt);
869
870 MoveGroupMConn(ctrl, graph, ndoms, pmat, nparts, target, nind, ind);
871
872 move = 1;
873 break;
874 }
875
876 if (move == 0)
877 break;
878 }
879
880 idxwspacefree(ctrl, nparts);
881 idxwspacefree(ctrl, nparts);
882 idxwspacefree(ctrl, nparts);
883 idxwspacefree(ctrl, nvtxs);
884
885 GKfree((void **) &cand, (void **) &cand2, LTERM);
886 }
887
888
889 /*************************************************************************
890 * This function moves a collection of vertices and updates their rinfo
891 **************************************************************************/
MoveGroupMConn(CtrlType * ctrl,GraphType * graph,idxtype * ndoms,idxtype * pmat,int nparts,int to,int nind,idxtype * ind)892 void MoveGroupMConn(CtrlType *ctrl, GraphType *graph, idxtype *ndoms, idxtype *pmat,
893 int nparts, int to, int nind, idxtype *ind)
894 {
895 int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees;
896 int from, me;
897 idxtype *xadj, *adjncy, *adjwgt;
898 idxtype *where, *bndptr, *bndind;
899 EDegreeType *myedegrees;
900 RInfoType *myrinfo;
901
902 nvtxs = graph->nvtxs;
903 xadj = graph->xadj;
904 adjncy = graph->adjncy;
905 adjwgt = graph->adjwgt;
906
907 where = graph->where;
908 bndptr = graph->bndptr;
909 bndind = graph->bndind;
910
911 nbnd = graph->nbnd;
912
913 for (iii=0; iii<nind; iii++) {
914 i = ind[iii];
915 from = where[i];
916
917 myrinfo = graph->rinfo+i;
918 if (myrinfo->edegrees == NULL) {
919 myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
920 ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
921 myrinfo->ndegrees = 0;
922 }
923 myedegrees = myrinfo->edegrees;
924
925 /* find the location of 'to' in myrinfo or create it if it is not there */
926 for (k=0; k<myrinfo->ndegrees; k++) {
927 if (myedegrees[k].pid == to)
928 break;
929 }
930 if (k == myrinfo->ndegrees) {
931 myedegrees[k].pid = to;
932 myedegrees[k].ed = 0;
933 myrinfo->ndegrees++;
934 }
935
936 graph->mincut -= myedegrees[k].ed-myrinfo->id;
937
938 /* Update pmat to reflect the move of 'i' */
939 pmat[from*nparts+to] += (myrinfo->id-myedegrees[k].ed);
940 pmat[to*nparts+from] += (myrinfo->id-myedegrees[k].ed);
941 if (pmat[from*nparts+to] == 0)
942 ndoms[from]--;
943 if (pmat[to*nparts+from] == 0)
944 ndoms[to]--;
945
946 /* Update where, weight, and ID/ED information of the vertex you moved */
947 where[i] = to;
948 myrinfo->ed += myrinfo->id-myedegrees[k].ed;
949 SWAP(myrinfo->id, myedegrees[k].ed, j);
950 if (myedegrees[k].ed == 0)
951 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
952 else
953 myedegrees[k].pid = from;
954
955 if (myrinfo->ed-myrinfo->id < 0 && bndptr[i] != -1)
956 BNDDelete(nbnd, bndind, bndptr, i);
957
958 /* Update the degrees of adjacent vertices */
959 for (j=xadj[i]; j<xadj[i+1]; j++) {
960 ii = adjncy[j];
961 me = where[ii];
962
963 myrinfo = graph->rinfo+ii;
964 if (myrinfo->edegrees == NULL) {
965 myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
966 ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
967 }
968 myedegrees = myrinfo->edegrees;
969
970 ASSERT(CheckRInfo(myrinfo));
971
972 if (me == from) {
973 INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
974
975 if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
976 BNDInsert(nbnd, bndind, bndptr, ii);
977 }
978 else if (me == to) {
979 INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
980
981 if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
982 BNDDelete(nbnd, bndind, bndptr, ii);
983 }
984
985 /* Remove contribution from the .ed of 'from' */
986 if (me != from) {
987 for (k=0; k<myrinfo->ndegrees; k++) {
988 if (myedegrees[k].pid == from) {
989 if (myedegrees[k].ed == adjwgt[j])
990 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
991 else
992 myedegrees[k].ed -= adjwgt[j];
993 break;
994 }
995 }
996 }
997
998 /* Add contribution to the .ed of 'to' */
999 if (me != to) {
1000 for (k=0; k<myrinfo->ndegrees; k++) {
1001 if (myedegrees[k].pid == to) {
1002 myedegrees[k].ed += adjwgt[j];
1003 break;
1004 }
1005 }
1006 if (k == myrinfo->ndegrees) {
1007 myedegrees[myrinfo->ndegrees].pid = to;
1008 myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
1009 }
1010 }
1011
1012 /* Update pmat to reflect the move of 'i' for domains other than 'from' and 'to' */
1013 if (me != from && me != to) {
1014 pmat[me*nparts+from] -= adjwgt[j];
1015 pmat[from*nparts+me] -= adjwgt[j];
1016 if (pmat[me*nparts+from] == 0)
1017 ndoms[me]--;
1018 if (pmat[from*nparts+me] == 0)
1019 ndoms[from]--;
1020
1021 if (pmat[me*nparts+to] == 0)
1022 ndoms[me]++;
1023 if (pmat[to*nparts+me] == 0)
1024 ndoms[to]++;
1025
1026 pmat[me*nparts+to] += adjwgt[j];
1027 pmat[to*nparts+me] += adjwgt[j];
1028 }
1029
1030 ASSERT(CheckRInfo(myrinfo));
1031 }
1032
1033 ASSERT(CheckRInfo(graph->rinfo+i));
1034 }
1035
1036 graph->nbnd = nbnd;
1037
1038 }
1039
1040
1041
1042
1043 /*************************************************************************
1044 * This function finds all the connected components induced by the
1045 * partitioning vector in wgraph->where and tries to push them around to
1046 * remove some of them
1047 **************************************************************************/
EliminateComponents(CtrlType * ctrl,GraphType * graph,int nparts,float * tpwgts,float ubfactor)1048 void EliminateComponents(CtrlType *ctrl, GraphType *graph, int nparts, float *tpwgts, float ubfactor)
1049 {
1050 int i, ii, j, jj, k, me, nvtxs, tvwgt, first, last, nleft, ncmps, cwgt, other, target, deltawgt;
1051 idxtype *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *maxpwgt;
1052 idxtype *cpvec, *touched, *perm, *todo, *cind, *cptr, *npcmps;
1053
1054 nvtxs = graph->nvtxs;
1055 xadj = graph->xadj;
1056 adjncy = graph->adjncy;
1057 vwgt = graph->vwgt;
1058 adjwgt = graph->adjwgt;
1059
1060 where = graph->where;
1061 pwgts = graph->pwgts;
1062
1063 touched = idxset(nvtxs, 0, idxwspacemalloc(ctrl, nvtxs));
1064 cptr = idxwspacemalloc(ctrl, nvtxs);
1065 cind = idxwspacemalloc(ctrl, nvtxs);
1066 perm = idxwspacemalloc(ctrl, nvtxs);
1067 todo = idxwspacemalloc(ctrl, nvtxs);
1068 maxpwgt = idxwspacemalloc(ctrl, nparts);
1069 cpvec = idxwspacemalloc(ctrl, nparts);
1070 npcmps = idxset(nparts, 0, idxwspacemalloc(ctrl, nparts));
1071
1072 for (i=0; i<nvtxs; i++)
1073 perm[i] = todo[i] = i;
1074
1075 /* Find the connected componends induced by the partition */
1076 ncmps = -1;
1077 first = last = 0;
1078 nleft = nvtxs;
1079 while (nleft > 0) {
1080 if (first == last) { /* Find another starting vertex */
1081 cptr[++ncmps] = first;
1082 ASSERT(touched[todo[0]] == 0);
1083 i = todo[0];
1084 cind[last++] = i;
1085 touched[i] = 1;
1086 me = where[i];
1087 npcmps[me]++;
1088 }
1089
1090 i = cind[first++];
1091 k = perm[i];
1092 j = todo[k] = todo[--nleft];
1093 perm[j] = k;
1094
1095 for (j=xadj[i]; j<xadj[i+1]; j++) {
1096 k = adjncy[j];
1097 if (where[k] == me && !touched[k]) {
1098 cind[last++] = k;
1099 touched[k] = 1;
1100 }
1101 }
1102 }
1103 cptr[++ncmps] = first;
1104
1105 /* printf("I found %d components, for this %d-way partition\n", ncmps, nparts); */
1106
1107 if (ncmps > nparts) { /* There are more components than processors */
1108 /* First determine the max allowed load imbalance */
1109 tvwgt = idxsum(nparts, pwgts);
1110 for (i=0; i<nparts; i++)
1111 maxpwgt[i] = ubfactor*tpwgts[i]*tvwgt;
1112
1113 deltawgt = 5;
1114
1115 for (i=0; i<ncmps; i++) {
1116 me = where[cind[cptr[i]]]; /* Get the domain of this component */
1117 if (npcmps[me] == 1)
1118 continue; /* Skip it because it is contigous */
1119
1120 /*printf("Trying to move %d from %d\n", i, me); */
1121
1122 /* Determine the weight of the block to be moved and abort if too high */
1123 for (cwgt=0, j=cptr[i]; j<cptr[i+1]; j++)
1124 cwgt += vwgt[cind[j]];
1125
1126 if (cwgt > .30*pwgts[me])
1127 continue; /* Skip the component if it is over 30% of the weight */
1128
1129 /* Determine the connectivity */
1130 idxset(nparts, 0, cpvec);
1131 for (j=cptr[i]; j<cptr[i+1]; j++) {
1132 ii = cind[j];
1133 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++)
1134 cpvec[where[adjncy[jj]]] += adjwgt[jj];
1135 }
1136 cpvec[me] = 0;
1137
1138 target = -1;
1139 for (j=0; j<nparts; j++) {
1140 if (cpvec[j] > 0 && (cwgt < deltawgt || pwgts[j] + cwgt < maxpwgt[j])) {
1141 if (target == -1 || cpvec[target] < cpvec[j])
1142 target = j;
1143 }
1144 }
1145
1146 /* printf("\tMoving it to %d [%d]\n", target, cpvec[target]);*/
1147
1148 if (target != -1) {
1149 /* Assign all the vertices of 'me' to 'target' and update data structures */
1150 INC_DEC(pwgts[target], pwgts[me], cwgt);
1151 npcmps[me]--;
1152
1153 MoveGroup(ctrl, graph, nparts, target, i, cptr, cind);
1154 }
1155 }
1156
1157 }
1158
1159 idxwspacefree(ctrl, nparts);
1160 idxwspacefree(ctrl, nparts);
1161 idxwspacefree(ctrl, nparts);
1162 idxwspacefree(ctrl, nvtxs);
1163 idxwspacefree(ctrl, nvtxs);
1164 idxwspacefree(ctrl, nvtxs);
1165 idxwspacefree(ctrl, nvtxs);
1166 idxwspacefree(ctrl, nvtxs);
1167
1168 }
1169
1170
1171 /*************************************************************************
1172 * This function moves a collection of vertices and updates their rinfo
1173 **************************************************************************/
MoveGroup(CtrlType * ctrl,GraphType * graph,int nparts,int to,int gid,idxtype * ptr,idxtype * ind)1174 void MoveGroup(CtrlType *ctrl, GraphType *graph, int nparts, int to, int gid, idxtype *ptr, idxtype *ind)
1175 {
1176 int i, ii, iii, j, jj, k, l, nvtxs, nbnd, myndegrees;
1177 int from, me;
1178 idxtype *xadj, *adjncy, *adjwgt;
1179 idxtype *where, *bndptr, *bndind;
1180 EDegreeType *myedegrees;
1181 RInfoType *myrinfo;
1182
1183 nvtxs = graph->nvtxs;
1184 xadj = graph->xadj;
1185 adjncy = graph->adjncy;
1186 adjwgt = graph->adjwgt;
1187
1188 where = graph->where;
1189 bndptr = graph->bndptr;
1190 bndind = graph->bndind;
1191
1192 nbnd = graph->nbnd;
1193
1194 for (iii=ptr[gid]; iii<ptr[gid+1]; iii++) {
1195 i = ind[iii];
1196 from = where[i];
1197
1198 myrinfo = graph->rinfo+i;
1199 if (myrinfo->edegrees == NULL) {
1200 myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
1201 ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
1202 myrinfo->ndegrees = 0;
1203 }
1204 myedegrees = myrinfo->edegrees;
1205
1206 /* find the location of 'to' in myrinfo or create it if it is not there */
1207 for (k=0; k<myrinfo->ndegrees; k++) {
1208 if (myedegrees[k].pid == to)
1209 break;
1210 }
1211 if (k == myrinfo->ndegrees) {
1212 myedegrees[k].pid = to;
1213 myedegrees[k].ed = 0;
1214 myrinfo->ndegrees++;
1215 }
1216
1217 graph->mincut -= myedegrees[k].ed-myrinfo->id;
1218
1219
1220 /* Update where, weight, and ID/ED information of the vertex you moved */
1221 where[i] = to;
1222 myrinfo->ed += myrinfo->id-myedegrees[k].ed;
1223 SWAP(myrinfo->id, myedegrees[k].ed, j);
1224 if (myedegrees[k].ed == 0)
1225 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
1226 else
1227 myedegrees[k].pid = from;
1228
1229 if (myrinfo->ed-myrinfo->id < 0 && bndptr[i] != -1)
1230 BNDDelete(nbnd, bndind, bndptr, i);
1231
1232 /* Update the degrees of adjacent vertices */
1233 for (j=xadj[i]; j<xadj[i+1]; j++) {
1234 ii = adjncy[j];
1235 me = where[ii];
1236
1237 myrinfo = graph->rinfo+ii;
1238 if (myrinfo->edegrees == NULL) {
1239 myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
1240 ctrl->wspace.cdegree += xadj[ii+1]-xadj[ii];
1241 }
1242 myedegrees = myrinfo->edegrees;
1243
1244 ASSERT(CheckRInfo(myrinfo));
1245
1246 if (me == from) {
1247 INC_DEC(myrinfo->ed, myrinfo->id, adjwgt[j]);
1248
1249 if (myrinfo->ed-myrinfo->id >= 0 && bndptr[ii] == -1)
1250 BNDInsert(nbnd, bndind, bndptr, ii);
1251 }
1252 else if (me == to) {
1253 INC_DEC(myrinfo->id, myrinfo->ed, adjwgt[j]);
1254
1255 if (myrinfo->ed-myrinfo->id < 0 && bndptr[ii] != -1)
1256 BNDDelete(nbnd, bndind, bndptr, ii);
1257 }
1258
1259 /* Remove contribution from the .ed of 'from' */
1260 if (me != from) {
1261 for (k=0; k<myrinfo->ndegrees; k++) {
1262 if (myedegrees[k].pid == from) {
1263 if (myedegrees[k].ed == adjwgt[j])
1264 myedegrees[k] = myedegrees[--myrinfo->ndegrees];
1265 else
1266 myedegrees[k].ed -= adjwgt[j];
1267 break;
1268 }
1269 }
1270 }
1271
1272 /* Add contribution to the .ed of 'to' */
1273 if (me != to) {
1274 for (k=0; k<myrinfo->ndegrees; k++) {
1275 if (myedegrees[k].pid == to) {
1276 myedegrees[k].ed += adjwgt[j];
1277 break;
1278 }
1279 }
1280 if (k == myrinfo->ndegrees) {
1281 myedegrees[myrinfo->ndegrees].pid = to;
1282 myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
1283 }
1284 }
1285
1286 ASSERT(CheckRInfo(myrinfo));
1287 }
1288
1289 ASSERT(CheckRInfo(graph->rinfo+i));
1290 }
1291
1292 graph->nbnd = nbnd;
1293
1294 }
1295
1296