1 /*!
2 \file
3 \brief Functions that deal with eliminating disconnected partitions
4
5 \date Started 7/15/98
6 \author George
7 \author Copyright 1997-2009, Regents of the University of Minnesota
8 \version $Id: contig.c 10513 2011-07-07 22:06:03Z karypis $
9 */
10
11 #include "metislib.h"
12
13
14 /*************************************************************************/
15 /*! This function finds the connected components induced by the
16 partitioning vector.
17
18 \param graph is the graph structure
19 \param where is the partitioning vector. If this is NULL, then the
20 entire graph is treated to belong into a single partition.
21 \param cptr is the ptr structure of the CSR representation of the
22 components. The length of this vector must be graph->nvtxs+1.
23 \param cind is the indices structure of the CSR representation of
24 the components. The length of this vector must be graph->nvtxs.
25
26 \returns the number of components that it found.
27
28 \note The cptr and cind parameters can be NULL, in which case only the
29 number of connected components is returned.
30 */
31 /*************************************************************************/
FindPartitionInducedComponents(graph_t * graph,idx_t * where,idx_t * cptr,idx_t * cind)32 idx_t FindPartitionInducedComponents(graph_t *graph, idx_t *where,
33 idx_t *cptr, idx_t *cind)
34 {
35 idx_t i, ii, j, jj, k, me=0, nvtxs, first, last, nleft, ncmps;
36 idx_t *xadj, *adjncy;
37 idx_t *touched, *perm, *todo;
38 idx_t mustfree_ccsr=0, mustfree_where=0;
39
40 nvtxs = graph->nvtxs;
41 xadj = graph->xadj;
42 adjncy = graph->adjncy;
43
44 /* Deal with NULL supplied cptr/cind vectors */
45 if (cptr == NULL) {
46 cptr = imalloc(nvtxs+1, "FindPartitionInducedComponents: cptr");
47 cind = imalloc(nvtxs, "FindPartitionInducedComponents: cind");
48 mustfree_ccsr = 1;
49 }
50
51 /* Deal with NULL supplied where vector */
52 if (where == NULL) {
53 where = ismalloc(nvtxs, 0, "FindPartitionInducedComponents: where");
54 mustfree_where = 1;
55 }
56
57 /* Allocate memory required for the BFS traversal */
58 perm = iincset(nvtxs, 0, imalloc(nvtxs, "FindPartitionInducedComponents: perm"));
59 todo = iincset(nvtxs, 0, imalloc(nvtxs, "FindPartitionInducedComponents: todo"));
60 touched = ismalloc(nvtxs, 0, "FindPartitionInducedComponents: touched");
61
62
63 /* Find the connected componends induced by the partition */
64 ncmps = -1;
65 first = last = 0;
66 nleft = nvtxs;
67 while (nleft > 0) {
68 if (first == last) { /* Find another starting vertex */
69 cptr[++ncmps] = first;
70 ASSERT(touched[todo[0]] == 0);
71 i = todo[0];
72 cind[last++] = i;
73 touched[i] = 1;
74 me = where[i];
75 }
76
77 i = cind[first++];
78 k = perm[i];
79 j = todo[k] = todo[--nleft];
80 perm[j] = k;
81
82 for (j=xadj[i]; j<xadj[i+1]; j++) {
83 k = adjncy[j];
84 if (where[k] == me && !touched[k]) {
85 cind[last++] = k;
86 touched[k] = 1;
87 }
88 }
89 }
90 cptr[++ncmps] = first;
91
92 if (mustfree_ccsr)
93 gk_free((void **)&cptr, &cind, LTERM);
94 if (mustfree_where)
95 gk_free((void **)&where, LTERM);
96
97 gk_free((void **)&perm, &todo, &touched, LTERM);
98
99 return ncmps;
100 }
101
102
103 /*************************************************************************/
104 /*! This function computes a permutation of the vertices based on a
105 breadth-first-traversal. It can be used for re-ordering the graph
106 to reduce its bandwidth for better cache locality.
107
108 \param ctrl is the control structure
109 \param graph is the graph structure
110 \param perm is the array that upon completion, perm[i] will store
111 the ID of the vertex that corresponds to the ith vertex in the
112 re-ordered graph.
113 */
114 /*************************************************************************/
ComputeBFSOrdering(ctrl_t * ctrl,graph_t * graph,idx_t * bfsperm)115 void ComputeBFSOrdering(ctrl_t *ctrl, graph_t *graph, idx_t *bfsperm)
116 {
117 idx_t i, j, k, nvtxs, first, last;
118 idx_t *xadj, *adjncy, *perm;
119
120 WCOREPUSH;
121
122 nvtxs = graph->nvtxs;
123 xadj = graph->xadj;
124 adjncy = graph->adjncy;
125
126 /* Allocate memory required for the BFS traversal */
127 perm = iincset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
128
129 iincset(nvtxs, 0, bfsperm); /* this array will also store the vertices
130 still to be processed */
131
132 /* Find the connected componends induced by the partition */
133 first = last = 0;
134 while (first < nvtxs) {
135 if (first == last) { /* Find another starting vertex */
136 k = bfsperm[last];
137 ASSERT(perm[k] != -1);
138 perm[k] = -1; /* mark node as being visited */
139 last++;
140 }
141
142 i = bfsperm[first++];
143 for (j=xadj[i]; j<xadj[i+1]; j++) {
144 k = adjncy[j];
145 /* if a node has been already been visited, its perm[] will be -1 */
146 if (perm[k] != -1) {
147 /* perm[k] is the location within bfsperm of where k resides;
148 put in that location bfsperm[last] that we are about to
149 overwrite and update perm[bfsperm[last]] to reflect that. */
150 bfsperm[perm[k]] = bfsperm[last];
151 perm[bfsperm[last]] = perm[k];
152
153 bfsperm[last++] = k; /* put node at the end of the "queue" */
154 perm[k] = -1; /* mark node as being visited */
155 }
156 }
157 }
158
159 WCOREPOP;
160 }
161
162
163 /*************************************************************************/
164 /*! This function checks whether a graph is contiguous or not.
165 */
166 /**************************************************************************/
IsConnected(graph_t * graph,idx_t report)167 idx_t IsConnected(graph_t *graph, idx_t report)
168 {
169 idx_t ncmps;
170
171 ncmps = FindPartitionInducedComponents(graph, NULL, NULL, NULL);
172
173 if (ncmps != 1 && report)
174 printf("The graph is not connected. It has %"PRIDX" connected components.\n", ncmps);
175
176 return (ncmps == 1);
177 }
178
179
180 /*************************************************************************/
181 /*! This function checks whether or not partition pid is contigous
182 */
183 /*************************************************************************/
IsConnectedSubdomain(ctrl_t * ctrl,graph_t * graph,idx_t pid,idx_t report)184 idx_t IsConnectedSubdomain(ctrl_t *ctrl, graph_t *graph, idx_t pid, idx_t report)
185 {
186 idx_t i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
187 idx_t *xadj, *adjncy, *where, *touched, *queue;
188 idx_t *cptr;
189
190 nvtxs = graph->nvtxs;
191 xadj = graph->xadj;
192 adjncy = graph->adjncy;
193 where = graph->where;
194
195 touched = ismalloc(nvtxs, 0, "IsConnected: touched");
196 queue = imalloc(nvtxs, "IsConnected: queue");
197 cptr = imalloc(nvtxs+1, "IsConnected: cptr");
198
199 nleft = 0;
200 for (i=0; i<nvtxs; i++) {
201 if (where[i] == pid)
202 nleft++;
203 }
204
205 for (i=0; i<nvtxs; i++) {
206 if (where[i] == pid)
207 break;
208 }
209
210 touched[i] = 1;
211 queue[0] = i;
212 first = 0; last = 1;
213
214 cptr[0] = 0; /* This actually points to queue */
215 ncmps = 0;
216 while (first != nleft) {
217 if (first == last) { /* Find another starting vertex */
218 cptr[++ncmps] = first;
219 for (i=0; i<nvtxs; i++) {
220 if (where[i] == pid && !touched[i])
221 break;
222 }
223 queue[last++] = i;
224 touched[i] = 1;
225 }
226
227 i = queue[first++];
228 for (j=xadj[i]; j<xadj[i+1]; j++) {
229 k = adjncy[j];
230 if (where[k] == pid && !touched[k]) {
231 queue[last++] = k;
232 touched[k] = 1;
233 }
234 }
235 }
236 cptr[++ncmps] = first;
237
238 if (ncmps > 1 && report) {
239 printf("The graph has %"PRIDX" connected components in partition %"PRIDX":\t", ncmps, pid);
240 for (i=0; i<ncmps; i++) {
241 wgt = 0;
242 for (j=cptr[i]; j<cptr[i+1]; j++)
243 wgt += graph->vwgt[queue[j]];
244 printf("[%5"PRIDX" %5"PRIDX"] ", cptr[i+1]-cptr[i], wgt);
245 /*
246 if (cptr[i+1]-cptr[i] == 1)
247 printf("[%"PRIDX" %"PRIDX"] ", queue[cptr[i]], xadj[queue[cptr[i]]+1]-xadj[queue[cptr[i]]]);
248 */
249 }
250 printf("\n");
251 }
252
253 gk_free((void **)&touched, &queue, &cptr, LTERM);
254
255 return (ncmps == 1 ? 1 : 0);
256 }
257
258
259 /*************************************************************************/
260 /*! This function identifies the number of connected components in a graph
261 that result after removing the vertices that belong to the vertex
262 separator (i.e., graph->where[i] == 2).
263 The connected component memberships are returned in the CSR-style
264 pair of arrays cptr, cind.
265 */
266 /**************************************************************************/
FindSepInducedComponents(ctrl_t * ctrl,graph_t * graph,idx_t * cptr,idx_t * cind)267 idx_t FindSepInducedComponents(ctrl_t *ctrl, graph_t *graph, idx_t *cptr,
268 idx_t *cind)
269 {
270 idx_t i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
271 idx_t *xadj, *adjncy, *where, *touched, *queue;
272
273 nvtxs = graph->nvtxs;
274 xadj = graph->xadj;
275 adjncy = graph->adjncy;
276 where = graph->where;
277
278 touched = ismalloc(nvtxs, 0, "IsConnected: queue");
279
280 for (i=0; i<graph->nbnd; i++)
281 touched[graph->bndind[i]] = 1;
282
283 queue = cind;
284
285 nleft = 0;
286 for (i=0; i<nvtxs; i++) {
287 if (where[i] != 2)
288 nleft++;
289 }
290
291 for (i=0; i<nvtxs; i++) {
292 if (where[i] != 2)
293 break;
294 }
295
296 touched[i] = 1;
297 queue[0] = i;
298 first = 0;
299 last = 1;
300 cptr[0] = 0; /* This actually points to queue */
301 ncmps = 0;
302
303 while (first != nleft) {
304 if (first == last) { /* Find another starting vertex */
305 cptr[++ncmps] = first;
306 for (i=0; i<nvtxs; i++) {
307 if (!touched[i])
308 break;
309 }
310 queue[last++] = i;
311 touched[i] = 1;
312 }
313
314 i = queue[first++];
315 for (j=xadj[i]; j<xadj[i+1]; j++) {
316 k = adjncy[j];
317 if (!touched[k]) {
318 queue[last++] = k;
319 touched[k] = 1;
320 }
321 }
322 }
323 cptr[++ncmps] = first;
324
325 gk_free((void **)&touched, LTERM);
326
327 return ncmps;
328 }
329
330
331 /*************************************************************************/
332 /*! This function finds all the connected components induced by the
333 partitioning vector in graph->where and tries to push them around to
334 remove some of them. */
335 /*************************************************************************/
EliminateComponents(ctrl_t * ctrl,graph_t * graph)336 void EliminateComponents(ctrl_t *ctrl, graph_t *graph)
337 {
338 idx_t i, ii, j, jj, k, me, nparts, nvtxs, ncon, ncmps, other,
339 ncand, target;
340 idx_t *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts;
341 idx_t *cptr, *cind, *cpvec, *pcptr, *pcind, *cwhere;
342 idx_t cid, bestcid, *cwgt, *bestcwgt;
343 idx_t ntodo, oldntodo, *todo;
344 rkv_t *cand;
345 real_t *tpwgts;
346 idx_t *vmarker=NULL, *pmarker=NULL, *modind=NULL; /* volume specific work arrays */
347
348 WCOREPUSH;
349
350 nvtxs = graph->nvtxs;
351 ncon = graph->ncon;
352 xadj = graph->xadj;
353 adjncy = graph->adjncy;
354 vwgt = graph->vwgt;
355 adjwgt = (ctrl->objtype == METIS_OBJTYPE_VOL ? NULL : graph->adjwgt);
356
357 where = graph->where;
358 pwgts = graph->pwgts;
359
360 nparts = ctrl->nparts;
361 tpwgts = ctrl->tpwgts;
362
363 cptr = iwspacemalloc(ctrl, nvtxs+1);
364 cind = iwspacemalloc(ctrl, nvtxs);
365
366 ncmps = FindPartitionInducedComponents(graph, where, cptr, cind);
367
368 IFSET(ctrl->dbglvl, METIS_DBG_CONTIGINFO,
369 printf("I found %"PRIDX" components, for this %"PRIDX"-way partition\n",
370 ncmps, nparts));
371
372 /* There are more components than partitions */
373 if (ncmps > nparts) {
374 cwgt = iwspacemalloc(ctrl, ncon);
375 bestcwgt = iwspacemalloc(ctrl, ncon);
376 cpvec = iwspacemalloc(ctrl, nparts);
377 pcptr = iset(nparts+1, 0, iwspacemalloc(ctrl, nparts+1));
378 pcind = iwspacemalloc(ctrl, ncmps);
379 cwhere = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
380 todo = iwspacemalloc(ctrl, ncmps);
381 cand = (rkv_t *)wspacemalloc(ctrl, nparts*sizeof(rkv_t));
382
383 if (ctrl->objtype == METIS_OBJTYPE_VOL) {
384 /* Vol-refinement specific working arrays */
385 modind = iwspacemalloc(ctrl, nvtxs);
386 vmarker = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
387 pmarker = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
388 }
389
390
391 /* Get a CSR representation of the components-2-partitions mapping */
392 for (i=0; i<ncmps; i++)
393 pcptr[where[cind[cptr[i]]]]++;
394 MAKECSR(i, nparts, pcptr);
395 for (i=0; i<ncmps; i++)
396 pcind[pcptr[where[cind[cptr[i]]]]++] = i;
397 SHIFTCSR(i, nparts, pcptr);
398
399 /* Assign the heaviest component of each partition to its original partition */
400 for (ntodo=0, i=0; i<nparts; i++) {
401 if (pcptr[i+1]-pcptr[i] == 1)
402 bestcid = pcind[pcptr[i]];
403 else {
404 for (bestcid=-1, j=pcptr[i]; j<pcptr[i+1]; j++) {
405 cid = pcind[j];
406 iset(ncon, 0, cwgt);
407 for (ii=cptr[cid]; ii<cptr[cid+1]; ii++)
408 iaxpy(ncon, 1, vwgt+cind[ii]*ncon, 1, cwgt, 1);
409 if (bestcid == -1 || isum(ncon, bestcwgt, 1) < isum(ncon, cwgt, 1)) {
410 bestcid = cid;
411 icopy(ncon, cwgt, bestcwgt);
412 }
413 }
414 /* Keep track of those that need to be dealt with */
415 for (j=pcptr[i]; j<pcptr[i+1]; j++) {
416 if (pcind[j] != bestcid)
417 todo[ntodo++] = pcind[j];
418 }
419 }
420
421 for (j=cptr[bestcid]; j<cptr[bestcid+1]; j++) {
422 ASSERT(where[cind[j]] == i);
423 cwhere[cind[j]] = i;
424 }
425 }
426
427
428 while (ntodo > 0) {
429 oldntodo = ntodo;
430 for (i=0; i<ntodo; i++) {
431 cid = todo[i];
432 me = where[cind[cptr[cid]]]; /* Get the domain of this component */
433
434 /* Determine the weight of the block to be moved */
435 iset(ncon, 0, cwgt);
436 for (j=cptr[cid]; j<cptr[cid+1]; j++)
437 iaxpy(ncon, 1, vwgt+cind[j]*ncon, 1, cwgt, 1);
438
439 IFSET(ctrl->dbglvl, METIS_DBG_CONTIGINFO,
440 printf("Trying to move %"PRIDX" [%"PRIDX"] from %"PRIDX"\n",
441 cid, isum(ncon, cwgt, 1), me));
442
443 /* Determine the connectivity */
444 iset(nparts, 0, cpvec);
445 for (j=cptr[cid]; j<cptr[cid+1]; j++) {
446 ii = cind[j];
447 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++)
448 if (cwhere[adjncy[jj]] != -1)
449 cpvec[cwhere[adjncy[jj]]] += (adjwgt ? adjwgt[jj] : 1);
450 }
451
452 /* Put the neighbors into a cand[] array for sorting */
453 for (ncand=0, j=0; j<nparts; j++) {
454 if (cpvec[j] > 0) {
455 cand[ncand].key = cpvec[j];
456 cand[ncand++].val = j;
457 }
458 }
459 if (ncand == 0)
460 continue;
461
462 rkvsortd(ncand, cand);
463
464 /* Limit the moves to only the top candidates, which are defined as
465 those with connectivity at least 50% of the best.
466 This applies only when ncon=1, as for multi-constraint, balancing
467 will be hard. */
468 if (ncon == 1) {
469 for (j=1; j<ncand; j++) {
470 if (cand[j].key < .5*cand[0].key)
471 break;
472 }
473 ncand = j;
474 }
475
476 /* Now among those, select the one with the best balance */
477 target = cand[0].val;
478 for (j=1; j<ncand; j++) {
479 if (BetterBalanceKWay(ncon, cwgt, ctrl->ubfactors,
480 1, pwgts+target*ncon, ctrl->pijbm+target*ncon,
481 1, pwgts+cand[j].val*ncon, ctrl->pijbm+cand[j].val*ncon))
482 target = cand[j].val;
483 }
484
485 IFSET(ctrl->dbglvl, METIS_DBG_CONTIGINFO,
486 printf("\tMoving it to %"PRIDX" [%"PRIDX"] [%"PRIDX"]\n", target, cpvec[target], ncand));
487
488 /* Note that as a result of a previous movement, a connected component may
489 now will like to stay to its original partition */
490 if (target != me) {
491 switch (ctrl->objtype) {
492 case METIS_OBJTYPE_CUT:
493 MoveGroupContigForCut(ctrl, graph, target, cid, cptr, cind);
494 break;
495
496 case METIS_OBJTYPE_VOL:
497 MoveGroupContigForVol(ctrl, graph, target, cid, cptr, cind,
498 vmarker, pmarker, modind);
499 break;
500
501 default:
502 gk_errexit(SIGERR, "Unknown objtype %d\n", ctrl->objtype);
503 }
504 }
505
506 /* Update the cwhere vector */
507 for (j=cptr[cid]; j<cptr[cid+1]; j++)
508 cwhere[cind[j]] = target;
509
510 todo[i] = todo[--ntodo];
511 }
512 if (oldntodo == ntodo) {
513 IFSET(ctrl->dbglvl, METIS_DBG_CONTIGINFO, printf("Stopped at ntodo: %"PRIDX"\n", ntodo));
514 break;
515 }
516 }
517
518 for (i=0; i<nvtxs; i++)
519 ASSERT(where[i] == cwhere[i]);
520
521 }
522
523 WCOREPOP;
524 }
525
526
527 /*************************************************************************/
528 /*! This function moves a collection of vertices and updates their rinfo
529 */
530 /*************************************************************************/
MoveGroupContigForCut(ctrl_t * ctrl,graph_t * graph,idx_t to,idx_t gid,idx_t * ptr,idx_t * ind)531 void MoveGroupContigForCut(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid,
532 idx_t *ptr, idx_t *ind)
533 {
534 idx_t i, ii, iii, j, jj, k, l, nvtxs, nbnd, from, me;
535 idx_t *xadj, *adjncy, *adjwgt, *where, *bndptr, *bndind;
536 ckrinfo_t *myrinfo;
537 cnbr_t *mynbrs;
538
539 nvtxs = graph->nvtxs;
540 xadj = graph->xadj;
541 adjncy = graph->adjncy;
542 adjwgt = graph->adjwgt;
543
544 where = graph->where;
545 bndptr = graph->bndptr;
546 bndind = graph->bndind;
547
548 nbnd = graph->nbnd;
549
550 for (iii=ptr[gid]; iii<ptr[gid+1]; iii++) {
551 i = ind[iii];
552 from = where[i];
553
554 myrinfo = graph->ckrinfo+i;
555 if (myrinfo->inbr == -1) {
556 myrinfo->inbr = cnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
557 myrinfo->nnbrs = 0;
558 }
559 mynbrs = ctrl->cnbrpool + myrinfo->inbr;
560
561 /* find the location of 'to' in myrinfo or create it if it is not there */
562 for (k=0; k<myrinfo->nnbrs; k++) {
563 if (mynbrs[k].pid == to)
564 break;
565 }
566 if (k == myrinfo->nnbrs) {
567 mynbrs[k].pid = to;
568 mynbrs[k].ed = 0;
569 myrinfo->nnbrs++;
570 }
571
572 graph->mincut -= mynbrs[k].ed-myrinfo->id;
573
574 /* Update ID/ED and BND related information for the moved vertex */
575 iaxpy(graph->ncon, 1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+to*graph->ncon, 1);
576 iaxpy(graph->ncon, -1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+from*graph->ncon, 1);
577 UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where, nbnd,
578 bndptr, bndind, BNDTYPE_REFINE);
579
580 /* Update the degrees of adjacent vertices */
581 for (j=xadj[i]; j<xadj[i+1]; j++) {
582 ii = adjncy[j];
583 me = where[ii];
584 myrinfo = graph->ckrinfo+ii;
585
586 UpdateAdjacentVertexInfoAndBND(ctrl, ii, xadj[ii+1]-xadj[ii], me,
587 from, to, myrinfo, adjwgt[j], nbnd, bndptr, bndind, BNDTYPE_REFINE);
588 }
589
590 ASSERT(CheckRInfo(ctrl, graph->ckrinfo+i));
591 }
592
593 graph->nbnd = nbnd;
594 }
595
596
597 /*************************************************************************/
598 /*! This function moves a collection of vertices and updates their rinfo
599 */
600 /*************************************************************************/
MoveGroupContigForVol(ctrl_t * ctrl,graph_t * graph,idx_t to,idx_t gid,idx_t * ptr,idx_t * ind,idx_t * vmarker,idx_t * pmarker,idx_t * modind)601 void MoveGroupContigForVol(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid,
602 idx_t *ptr, idx_t *ind, idx_t *vmarker, idx_t *pmarker,
603 idx_t *modind)
604 {
605 idx_t i, ii, iii, j, jj, k, l, nvtxs, from, me, other, xgain;
606 idx_t *xadj, *vsize, *adjncy, *where;
607 vkrinfo_t *myrinfo, *orinfo;
608 vnbr_t *mynbrs, *onbrs;
609
610 nvtxs = graph->nvtxs;
611 xadj = graph->xadj;
612 vsize = graph->vsize;
613 adjncy = graph->adjncy;
614 where = graph->where;
615
616 for (iii=ptr[gid]; iii<ptr[gid+1]; iii++) {
617 i = ind[iii];
618 from = where[i];
619
620 myrinfo = graph->vkrinfo+i;
621 if (myrinfo->inbr == -1) {
622 myrinfo->inbr = vnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
623 myrinfo->nnbrs = 0;
624 }
625 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
626
627 xgain = (myrinfo->nid == 0 && myrinfo->ned > 0 ? vsize[i] : 0);
628
629 /* find the location of 'to' in myrinfo or create it if it is not there */
630 for (k=0; k<myrinfo->nnbrs; k++) {
631 if (mynbrs[k].pid == to)
632 break;
633 }
634 if (k == myrinfo->nnbrs) {
635 if (myrinfo->nid > 0)
636 xgain -= vsize[i];
637
638 /* determine the volume gain resulting from that move */
639 for (j=xadj[i]; j<xadj[i+1]; j++) {
640 ii = adjncy[j];
641 other = where[ii];
642 orinfo = graph->vkrinfo+ii;
643 onbrs = ctrl->vnbrpool + orinfo->inbr;
644 ASSERT(other != to)
645
646 if (from == other) {
647 /* Same subdomain vertex: Decrease the gain if 'to' is a new neighbor. */
648 for (l=0; l<orinfo->nnbrs; l++) {
649 if (onbrs[l].pid == to)
650 break;
651 }
652 if (l == orinfo->nnbrs)
653 xgain -= vsize[ii];
654 }
655 else {
656 /* Remote vertex: increase if 'to' is a new subdomain */
657 for (l=0; l<orinfo->nnbrs; l++) {
658 if (onbrs[l].pid == to)
659 break;
660 }
661 if (l == orinfo->nnbrs)
662 xgain -= vsize[ii];
663
664 /* Remote vertex: decrease if i is the only connection to 'from' */
665 for (l=0; l<orinfo->nnbrs; l++) {
666 if (onbrs[l].pid == from && onbrs[l].ned == 1) {
667 xgain += vsize[ii];
668 break;
669 }
670 }
671 }
672 }
673 graph->minvol -= xgain;
674 graph->mincut -= -myrinfo->nid;
675 }
676 else {
677 graph->minvol -= (xgain + mynbrs[k].gv);
678 graph->mincut -= mynbrs[k].ned-myrinfo->nid;
679 }
680
681
682 /* Update where and pwgts */
683 where[i] = to;
684 iaxpy(graph->ncon, 1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+to*graph->ncon, 1);
685 iaxpy(graph->ncon, -1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+from*graph->ncon, 1);
686
687 /* Update the id/ed/gains/bnd of potentially affected nodes */
688 KWayVolUpdate(ctrl, graph, i, from, to, NULL, NULL, NULL, NULL,
689 NULL, BNDTYPE_REFINE, vmarker, pmarker, modind);
690
691 /*CheckKWayVolPartitionParams(ctrl, graph);*/
692 }
693
694 ASSERT(ComputeCut(graph, where) == graph->mincut);
695 ASSERTP(ComputeVolume(graph, where) == graph->minvol,
696 ("%"PRIDX" %"PRIDX"\n", ComputeVolume(graph, where), graph->minvol));
697
698 }
699
700