?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Bug #1267: Integrate METIS graph partitioning library
[charm.git] / src / libs / ck-libs / metis / libmetis / kwayfm.c
blobdedfd39098c40836f60f9b6ca3895e2293c89f29
1 /*!
2 \file
3 \brief Routines for k-way refinement
4
5 \date Started 7/28/97
6 \author George
7 \author Copyright 1997-2009, Regents of the University of Minnesota
8 \version $Id: kwayfm.c 10567 2011-07-13 16:17:07Z karypis $
9 */
10
11 #include "metislib.h"
12
13
14
15 /*************************************************************************/
16 /* Top-level routine for k-way partitioning refinement. This routine just
17 calls the appropriate refinement routine based on the objectives and
18 constraints. */
19 /*************************************************************************/
20 void Greedy_KWayOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter,
21 real_t ffactor, idx_t omode)
22 {
23 switch (ctrl->objtype) {
24 case METIS_OBJTYPE_CUT:
25 if (graph->ncon == 1)
26 Greedy_KWayCutOptimize(ctrl, graph, niter, ffactor, omode);
27 else
28 Greedy_McKWayCutOptimize(ctrl, graph, niter, ffactor, omode);
29 break;
30
31 case METIS_OBJTYPE_VOL:
32 if (graph->ncon == 1)
33 Greedy_KWayVolOptimize(ctrl, graph, niter, ffactor, omode);
34 else
35 Greedy_McKWayVolOptimize(ctrl, graph, niter, ffactor, omode);
36 break;
37
38 default:
39 gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
40 }
41 }
42
43
44 /*************************************************************************/
45 /*! K-way partitioning optimization in which the vertices are visited in
46 decreasing ed/sqrt(nnbrs)-id order. Note this is just an
47 approximation, as the ed is often split across different subdomains
48 and the sqrt(nnbrs) is just a crude approximation.
49
50 \param graph is the graph that is being refined.
51 \param niter is the number of refinement iterations.
52 \param ffactor is the \em fudge-factor for allowing positive gain moves
53 to violate the max-pwgt constraint.
54 \param omode is the type of optimization that will performed among
55 OMODE_REFINE and OMODE_BALANCE
56
57
58 */
59 /**************************************************************************/
60 void Greedy_KWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter,
61 real_t ffactor, idx_t omode)
62 {
63 /* Common variables to all types of kway-refinement/balancing routines */
64 idx_t i, ii, iii, j, k, l, pass, nvtxs, nparts, gain;
65 idx_t from, me, to, oldcut, vwgt;
66 idx_t *xadj, *adjncy, *adjwgt;
67 idx_t *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
68 idx_t nmoved, nupd, *vstatus, *updptr, *updind;
69 idx_t maxndoms, *safetos=NULL, *nads=NULL, *doms=NULL, **adids=NULL, **adwgts=NULL;
70 idx_t *bfslvl=NULL, *bfsind=NULL, *bfsmrk=NULL;
71 idx_t bndtype = (omode == OMODE_REFINE ? BNDTYPE_REFINE : BNDTYPE_BALANCE);
72
73 /* Edgecut-specific/different variables */
74 idx_t nbnd, oldnnbrs;
75 rpq_t *queue;
76 real_t rgain;
77 ckrinfo_t *myrinfo;
78 cnbr_t *mynbrs;
79
80 WCOREPUSH;
81
82 /* Link the graph fields */
83 nvtxs = graph->nvtxs;
84 xadj = graph->xadj;
85 adjncy = graph->adjncy;
86 adjwgt = graph->adjwgt;
87
88 bndind = graph->bndind;
89 bndptr = graph->bndptr;
90
91 where = graph->where;
92 pwgts = graph->pwgts;
93
94 nparts = ctrl->nparts;
95
96 /* Setup the weight intervals of the various subdomains */
97 minwgt = iwspacemalloc(ctrl, nparts);
98 maxwgt = iwspacemalloc(ctrl, nparts);
99 itpwgts = iwspacemalloc(ctrl, nparts);
100
101 for (i=0; i<nparts; i++) {
102 itpwgts[i] = ctrl->tpwgts[i]*graph->tvwgt[0];
103 maxwgt[i] = ctrl->tpwgts[i]*graph->tvwgt[0]*ctrl->ubfactors[0];
104 minwgt[i] = ctrl->tpwgts[i]*graph->tvwgt[0]*(1.0/ctrl->ubfactors[0]);
105 }
106
107 perm = iwspacemalloc(ctrl, nvtxs);
108
109
110 /* This stores the valid target subdomains. It is used when ctrl->minconn to
111 control the subdomains to which moves are allowed to be made.
112 When ctrl->minconn is false, the default values of 2 allow all moves to
113 go through and it does not interfere with the zero-gain move selection. */
114 safetos = iset(nparts, 2, iwspacemalloc(ctrl, nparts));
115
116 if (ctrl->minconn) {
117 ComputeSubDomainGraph(ctrl, graph);
118
119 nads = ctrl->nads;
120 adids = ctrl->adids;
121 adwgts = ctrl->adwgts;
122 doms = iset(nparts, 0, ctrl->pvec1);
123 }
124
125
126 /* Setup updptr, updind like boundary info to keep track of the vertices whose
127 vstatus's need to be reset at the end of the inner iteration */
128 vstatus = iset(nvtxs, VPQSTATUS_NOTPRESENT, iwspacemalloc(ctrl, nvtxs));
129 updptr = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
130 updind = iwspacemalloc(ctrl, nvtxs);
131
132 if (ctrl->contig) {
133 /* The arrays that will be used for limited check of articulation points */
134 bfslvl = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
135 bfsind = iwspacemalloc(ctrl, nvtxs);
136 bfsmrk = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
137 }
138
139 if (ctrl->dbglvl&METIS_DBG_REFINE) {
140 printf("%s: [%6"PRIDX" %6"PRIDX"]-[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL","
141 " Nv-Nb[%6"PRIDX" %6"PRIDX"], Cut: %6"PRIDX,
142 (omode == OMODE_REFINE ? "GRC" : "GBC"),
143 pwgts[iargmin(nparts, pwgts)], imax(nparts, pwgts), minwgt[0], maxwgt[0],
144 ComputeLoadImbalance(graph, nparts, ctrl->pijbm),
145 graph->nvtxs, graph->nbnd, graph->mincut);
146 if (ctrl->minconn)
147 printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
148 printf("\n");
149 }
150
151 queue = rpqCreate(nvtxs);
152
153 /*=====================================================================
154 * The top-level refinement loop
155 *======================================================================*/
156 for (pass=0; pass<niter; pass++) {
157 ASSERT(ComputeCut(graph, where) == graph->mincut);
158
159 if (omode == OMODE_BALANCE) {
160 /* Check to see if things are out of balance, given the tolerance */
161 for (i=0; i<nparts; i++) {
162 if (pwgts[i] > maxwgt[i])
163 break;
164 }
165 if (i == nparts) /* Things are balanced. Return right away */
166 break;
167 }
168
169 oldcut = graph->mincut;
170 nbnd = graph->nbnd;
171 nupd = 0;
172
173 if (ctrl->minconn)
174 maxndoms = imax(nparts, nads);
175
176 /* Insert the boundary vertices in the priority queue */
177 irandArrayPermute(nbnd, perm, nbnd/4, 1);
178 for (ii=0; ii<nbnd; ii++) {
179 i = bndind[perm[ii]];
180 rgain = (graph->ckrinfo[i].nnbrs > 0 ?
181 1.0*graph->ckrinfo[i].ed/sqrt(graph->ckrinfo[i].nnbrs) : 0.0)
182 - graph->ckrinfo[i].id;
183 rpqInsert(queue, i, rgain);
184 vstatus[i] = VPQSTATUS_PRESENT;
185 ListInsert(nupd, updind, updptr, i);
186 }
187
188 /* Start extracting vertices from the queue and try to move them */
189 for (nmoved=0, iii=0;;iii++) {
190 if ((i = rpqGetTop(queue)) == -1)
191 break;
192 vstatus[i] = VPQSTATUS_EXTRACTED;
193
194 myrinfo = graph->ckrinfo+i;
195 mynbrs = ctrl->cnbrpool + myrinfo->inbr;
196
197 from = where[i];
198 vwgt = graph->vwgt[i];
199
200 /* Prevent moves that make 'from' domain underbalanced */
201 if (omode == OMODE_REFINE) {
202 if (myrinfo->id > 0 && pwgts[from]-vwgt < minwgt[from])
203 continue;
204 }
205 else { /* OMODE_BALANCE */
206 if (pwgts[from]-vwgt < minwgt[from])
207 continue;
208 }
209
210 if (ctrl->contig && IsArticulationNode(i, xadj, adjncy, where, bfslvl, bfsind, bfsmrk))
211 continue;
212
213 if (ctrl->minconn)
214 SelectSafeTargetSubdomains(myrinfo, mynbrs, nads, adids, maxndoms, safetos, doms);
215
216 /* Find the most promising subdomain to move to */
217 if (omode == OMODE_REFINE) {
218 for (k=myrinfo->nnbrs-1; k>=0; k--) {
219 if (!safetos[to=mynbrs[k].pid])
220 continue;
221 gain = mynbrs[k].ed-myrinfo->id;
222 if (gain >= 0 && pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain)
223 break;
224 }
225 if (k < 0)
226 continue; /* break out if you did not find a candidate */
227
228 for (j=k-1; j>=0; j--) {
229 if (!safetos[to=mynbrs[j].pid])
230 continue;
231 gain = mynbrs[j].ed-myrinfo->id;
232 if ((mynbrs[j].ed > mynbrs[k].ed && pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain)
233 ||
234 (mynbrs[j].ed == mynbrs[k].ed &&
235 itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid]))
236 k = j;
237 }
238
239 to = mynbrs[k].pid;
240
241 gain = mynbrs[k].ed-myrinfo->id;
242 if (!(gain > 0
243 || (gain == 0
244 && (pwgts[from] >= maxwgt[from]
245 || itpwgts[to]*pwgts[from] > itpwgts[from]*(pwgts[to]+vwgt)
246 || (iii%2 == 0 && safetos[to] == 2)
247 )
248 )
249 )
250 )
251 continue;
252 }
253 else { /* OMODE_BALANCE */
254 for (k=myrinfo->nnbrs-1; k>=0; k--) {
255 if (!safetos[to=mynbrs[k].pid])
256 continue;
257 if (pwgts[to]+vwgt <= maxwgt[to] ||
258 itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from])
259 break;
260 }
261 if (k < 0)
262 continue; /* break out if you did not find a candidate */
263
264 for (j=k-1; j>=0; j--) {
265 if (!safetos[to=mynbrs[j].pid])
266 continue;
267 if (itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid])
268 k = j;
269 }
270
271 to = mynbrs[k].pid;
272
273 if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] &&
274 mynbrs[k].ed-myrinfo->id < 0)
275 continue;
276 }
277
278
279
280 /*=====================================================================
281 * If we got here, we can now move the vertex from 'from' to 'to'
282 *======================================================================*/
283 graph->mincut -= mynbrs[k].ed-myrinfo->id;
284 nmoved++;
285
286 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
287 printf("\t\tMoving %6"PRIDX" to %3"PRIDX". Gain: %4"PRIDX". Cut: %6"PRIDX"\n",
288 i, to, mynbrs[k].ed-myrinfo->id, graph->mincut));
289
290 /* Update the subdomain connectivity information */
291 if (ctrl->minconn) {
292 /* take care of i's move itself */
293 UpdateEdgeSubDomainGraph(ctrl, from, to, myrinfo->id-mynbrs[k].ed, &maxndoms);
294
295 /* take care of the adjancent vertices */
296 for (j=xadj[i]; j<xadj[i+1]; j++) {
297 me = where[adjncy[j]];
298 if (me != from && me != to) {
299 UpdateEdgeSubDomainGraph(ctrl, from, me, -adjwgt[j], &maxndoms);
300 UpdateEdgeSubDomainGraph(ctrl, to, me, adjwgt[j], &maxndoms);
301 }
302 }
303 }
304
305 /* Update ID/ED and BND related information for the moved vertex */
306 INC_DEC(pwgts[to], pwgts[from], vwgt);
307 UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where, nbnd,
308 bndptr, bndind, bndtype);
309
310 /* Update the degrees of adjacent vertices */
311 for (j=xadj[i]; j<xadj[i+1]; j++) {
312 ii = adjncy[j];
313 me = where[ii];
314 myrinfo = graph->ckrinfo+ii;
315
316 oldnnbrs = myrinfo->nnbrs;
317
318 UpdateAdjacentVertexInfoAndBND(ctrl, ii, xadj[ii+1]-xadj[ii], me,
319 from, to, myrinfo, adjwgt[j], nbnd, bndptr, bndind, bndtype);
320
321 UpdateQueueInfo(queue, vstatus, ii, me, from, to, myrinfo, oldnnbrs,
322 nupd, updptr, updind, bndtype);
323
324 ASSERT(myrinfo->nnbrs <= xadj[ii+1]-xadj[ii]);
325 }
326 }
327
328 graph->nbnd = nbnd;
329
330 /* Reset the vstatus and associated data structures */
331 for (i=0; i<nupd; i++) {
332 ASSERT(updptr[updind[i]] != -1);
333 ASSERT(vstatus[updind[i]] != VPQSTATUS_NOTPRESENT);
334 vstatus[updind[i]] = VPQSTATUS_NOTPRESENT;
335 updptr[updind[i]] = -1;
336 }
337
338 if (ctrl->dbglvl&METIS_DBG_REFINE) {
339 printf("\t[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL", Nb: %6"PRIDX"."
340 " Nmoves: %5"PRIDX", Cut: %6"PRIDX", Vol: %6"PRIDX,
341 pwgts[iargmin(nparts, pwgts)], imax(nparts, pwgts),
342 ComputeLoadImbalance(graph, nparts, ctrl->pijbm),
343 graph->nbnd, nmoved, graph->mincut, ComputeVolume(graph, where));
344 if (ctrl->minconn)
345 printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
346 printf("\n");
347 }
348
349 if (nmoved == 0 || (omode == OMODE_REFINE && graph->mincut == oldcut))
350 break;
351 }
352
353 rpqDestroy(queue);
354
355 WCOREPOP;
356 }
357
358
359 /*************************************************************************/
360 /*! K-way refinement that minimizes the communication volume. This is a
361 greedy routine and the vertices are visited in decreasing gv order.
362
363 \param graph is the graph that is being refined.
364 \param niter is the number of refinement iterations.
365 \param ffactor is the \em fudge-factor for allowing positive gain moves
366 to violate the max-pwgt constraint.
367
368 */
369 /**************************************************************************/
370 void Greedy_KWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter,
371 real_t ffactor, idx_t omode)
372 {
373 /* Common variables to all types of kway-refinement/balancing routines */
374 idx_t i, ii, iii, j, k, l, pass, nvtxs, nparts, gain;
375 idx_t from, me, to, oldcut, vwgt;
376 idx_t *xadj, *adjncy;
377 idx_t *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt, *itpwgts;
378 idx_t nmoved, nupd, *vstatus, *updptr, *updind;
379 idx_t maxndoms, *safetos=NULL, *nads=NULL, *doms=NULL, **adids=NULL, **adwgts=NULL;
380 idx_t *bfslvl=NULL, *bfsind=NULL, *bfsmrk=NULL;
381 idx_t bndtype = (omode == OMODE_REFINE ? BNDTYPE_REFINE : BNDTYPE_BALANCE);
382
383 /* Volume-specific/different variables */
384 ipq_t *queue;
385 idx_t oldvol, xgain;
386 idx_t *vmarker, *pmarker, *modind;
387 vkrinfo_t *myrinfo;
388 vnbr_t *mynbrs;
389
390 WCOREPUSH;
391
392 /* Link the graph fields */
393 nvtxs = graph->nvtxs;
394 xadj = graph->xadj;
395 adjncy = graph->adjncy;
396 bndptr = graph->bndptr;
397 bndind = graph->bndind;
398 where = graph->where;
399 pwgts = graph->pwgts;
400
401 nparts = ctrl->nparts;
402
403 /* Setup the weight intervals of the various subdomains */
404 minwgt = iwspacemalloc(ctrl, nparts);
405 maxwgt = iwspacemalloc(ctrl, nparts);
406 itpwgts = iwspacemalloc(ctrl, nparts);
407
408 for (i=0; i<nparts; i++) {
409 itpwgts[i] = ctrl->tpwgts[i]*graph->tvwgt[0];
410 maxwgt[i] = ctrl->tpwgts[i]*graph->tvwgt[0]*ctrl->ubfactors[0];
411 minwgt[i] = ctrl->tpwgts[i]*graph->tvwgt[0]*(1.0/ctrl->ubfactors[0]);
412 }
413
414 perm = iwspacemalloc(ctrl, nvtxs);
415
416
417 /* This stores the valid target subdomains. It is used when ctrl->minconn to
418 control the subdomains to which moves are allowed to be made.
419 When ctrl->minconn is false, the default values of 2 allow all moves to
420 go through and it does not interfere with the zero-gain move selection. */
421 safetos = iset(nparts, 2, iwspacemalloc(ctrl, nparts));
422
423 if (ctrl->minconn) {
424 ComputeSubDomainGraph(ctrl, graph);
425
426 nads = ctrl->nads;
427 adids = ctrl->adids;
428 adwgts = ctrl->adwgts;
429 doms = iset(nparts, 0, ctrl->pvec1);
430 }
431
432
433 /* Setup updptr, updind like boundary info to keep track of the vertices whose
434 vstatus's need to be reset at the end of the inner iteration */
435 vstatus = iset(nvtxs, VPQSTATUS_NOTPRESENT, iwspacemalloc(ctrl, nvtxs));
436 updptr = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
437 updind = iwspacemalloc(ctrl, nvtxs);
438
439 if (ctrl->contig) {
440 /* The arrays that will be used for limited check of articulation points */
441 bfslvl = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
442 bfsind = iwspacemalloc(ctrl, nvtxs);
443 bfsmrk = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
444 }
445
446 /* Vol-refinement specific working arrays */
447 modind = iwspacemalloc(ctrl, nvtxs);
448 vmarker = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
449 pmarker = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
450
451 if (ctrl->dbglvl&METIS_DBG_REFINE) {
452 printf("%s: [%6"PRIDX" %6"PRIDX"]-[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL
453 ", Nv-Nb[%6"PRIDX" %6"PRIDX"], Cut: %5"PRIDX", Vol: %5"PRIDX,
454 (omode == OMODE_REFINE ? "GRV" : "GBV"),
455 pwgts[iargmin(nparts, pwgts)], imax(nparts, pwgts), minwgt[0], maxwgt[0],
456 ComputeLoadImbalance(graph, nparts, ctrl->pijbm),
457 graph->nvtxs, graph->nbnd, graph->mincut, graph->minvol);
458 if (ctrl->minconn)
459 printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
460 printf("\n");
461 }
462
463 queue = ipqCreate(nvtxs);
464
465
466 /*=====================================================================
467 * The top-level refinement loop
468 *======================================================================*/
469 for (pass=0; pass<niter; pass++) {
470 ASSERT(ComputeVolume(graph, where) == graph->minvol);
471
472 if (omode == OMODE_BALANCE) {
473 /* Check to see if things are out of balance, given the tolerance */
474 for (i=0; i<nparts; i++) {
475 if (pwgts[i] > maxwgt[i])
476 break;
477 }
478 if (i == nparts) /* Things are balanced. Return right away */
479 break;
480 }
481
482 oldcut = graph->mincut;
483 oldvol = graph->minvol;
484 nupd = 0;
485
486 if (ctrl->minconn)
487 maxndoms = imax(nparts, nads);
488
489 /* Insert the boundary vertices in the priority queue */
490 irandArrayPermute(graph->nbnd, perm, graph->nbnd/4, 1);
491 for (ii=0; ii<graph->nbnd; ii++) {
492 i = bndind[perm[ii]];
493 ipqInsert(queue, i, graph->vkrinfo[i].gv);
494 vstatus[i] = VPQSTATUS_PRESENT;
495 ListInsert(nupd, updind, updptr, i);
496 }
497
498 /* Start extracting vertices from the queue and try to move them */
499 for (nmoved=0, iii=0;;iii++) {
500 if ((i = ipqGetTop(queue)) == -1)
501 break;
502 vstatus[i] = VPQSTATUS_EXTRACTED;
503
504 myrinfo = graph->vkrinfo+i;
505 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
506
507 from = where[i];
508 vwgt = graph->vwgt[i];
509
510 /* Prevent moves that make 'from' domain underbalanced */
511 if (omode == OMODE_REFINE) {
512 if (myrinfo->nid > 0 && pwgts[from]-vwgt < minwgt[from])
513 continue;
514 }
515 else { /* OMODE_BALANCE */
516 if (pwgts[from]-vwgt < minwgt[from])
517 continue;
518 }
519
520 if (ctrl->contig && IsArticulationNode(i, xadj, adjncy, where, bfslvl, bfsind, bfsmrk))
521 continue;
522
523 if (ctrl->minconn)
524 SelectSafeTargetSubdomains(myrinfo, mynbrs, nads, adids, maxndoms, safetos, doms);
525
526 xgain = (myrinfo->nid == 0 && myrinfo->ned > 0 ? graph->vsize[i] : 0);
527
528 /* Find the most promising subdomain to move to */
529 if (omode == OMODE_REFINE) {
530 for (k=myrinfo->nnbrs-1; k>=0; k--) {
531 if (!safetos[to=mynbrs[k].pid])
532 continue;
533 gain = mynbrs[k].gv + xgain;
534 if (gain >= 0 && pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain)
535 break;
536 }
537 if (k < 0)
538 continue; /* break out if you did not find a candidate */
539
540 for (j=k-1; j>=0; j--) {
541 if (!safetos[to=mynbrs[j].pid])
542 continue;
543 gain = mynbrs[j].gv + xgain;
544 if ((mynbrs[j].gv > mynbrs[k].gv &&
545 pwgts[to]+vwgt <= maxwgt[to]+ffactor*gain)
546 ||
547 (mynbrs[j].gv == mynbrs[k].gv &&
548 mynbrs[j].ned > mynbrs[k].ned &&
549 pwgts[to]+vwgt <= maxwgt[to])
550 ||
551 (mynbrs[j].gv == mynbrs[k].gv &&
552 mynbrs[j].ned == mynbrs[k].ned &&
553 itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid])
554 )
555 k = j;
556 }
557 to = mynbrs[k].pid;
558
559 ASSERT(xgain+mynbrs[k].gv >= 0);
560
561 j = 0;
562 if (xgain+mynbrs[k].gv > 0 || mynbrs[k].ned-myrinfo->nid > 0)
563 j = 1;
564 else if (mynbrs[k].ned-myrinfo->nid == 0) {
565 if ((iii%2 == 0 && safetos[to] == 2) ||
566 pwgts[from] >= maxwgt[from] ||
567 itpwgts[from]*(pwgts[to]+vwgt) < itpwgts[to]*pwgts[from])
568 j = 1;
569 }
570 if (j == 0)
571 continue;
572 }
573 else { /* OMODE_BALANCE */
574 for (k=myrinfo->nnbrs-1; k>=0; k--) {
575 if (!safetos[to=mynbrs[k].pid])
576 continue;
577 if (pwgts[to]+vwgt <= maxwgt[to] ||
578 itpwgts[from]*(pwgts[to]+vwgt) <= itpwgts[to]*pwgts[from])
579 break;
580 }
581 if (k < 0)
582 continue; /* break out if you did not find a candidate */
583
584 for (j=k-1; j>=0; j--) {
585 if (!safetos[to=mynbrs[j].pid])
586 continue;
587 if (itpwgts[mynbrs[k].pid]*pwgts[to] < itpwgts[to]*pwgts[mynbrs[k].pid])
588 k = j;
589 }
590 to = mynbrs[k].pid;
591
592 if (pwgts[from] < maxwgt[from] && pwgts[to] > minwgt[to] &&
593 (xgain+mynbrs[k].gv < 0 ||
594 (xgain+mynbrs[k].gv == 0 && mynbrs[k].ned-myrinfo->nid < 0))
595 )
596 continue;
597 }
598
599
600 /*=====================================================================
601 * If we got here, we can now move the vertex from 'from' to 'to'
602 *======================================================================*/
603 INC_DEC(pwgts[to], pwgts[from], vwgt);
604 graph->mincut -= mynbrs[k].ned-myrinfo->nid;
605 graph->minvol -= (xgain+mynbrs[k].gv);
606 where[i] = to;
607 nmoved++;
608
609 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
610 printf("\t\tMoving %6"PRIDX" from %3"PRIDX" to %3"PRIDX". "
611 "Gain: [%4"PRIDX" %4"PRIDX"]. Cut: %6"PRIDX", Vol: %6"PRIDX"\n",
612 i, from, to, xgain+mynbrs[k].gv, mynbrs[k].ned-myrinfo->nid,
613 graph->mincut, graph->minvol));
614
615 /* Update the subdomain connectivity information */
616 if (ctrl->minconn) {
617 /* take care of i's move itself */
618 UpdateEdgeSubDomainGraph(ctrl, from, to, myrinfo->nid-mynbrs[k].ned, &maxndoms);
619
620 /* take care of the adjancent vertices */
621 for (j=xadj[i]; j<xadj[i+1]; j++) {
622 me = where[adjncy[j]];
623 if (me != from && me != to) {
624 UpdateEdgeSubDomainGraph(ctrl, from, me, -1, &maxndoms);
625 UpdateEdgeSubDomainGraph(ctrl, to, me, 1, &maxndoms);
626 }
627 }
628 }
629
630 /* Update the id/ed/gains/bnd/queue of potentially affected nodes */
631 KWayVolUpdate(ctrl, graph, i, from, to, queue, vstatus, &nupd, updptr,
632 updind, bndtype, vmarker, pmarker, modind);
633
634 /*CheckKWayVolPartitionParams(ctrl, graph); */
635 }
636
637
638 /* Reset the vstatus and associated data structures */
639 for (i=0; i<nupd; i++) {
640 ASSERT(updptr[updind[i]] != -1);
641 ASSERT(vstatus[updind[i]] != VPQSTATUS_NOTPRESENT);
642 vstatus[updind[i]] = VPQSTATUS_NOTPRESENT;
643 updptr[updind[i]] = -1;
644 }
645
646 if (ctrl->dbglvl&METIS_DBG_REFINE) {
647 printf("\t[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL", Nb: %6"PRIDX"."
648 " Nmoves: %5"PRIDX", Cut: %6"PRIDX", Vol: %6"PRIDX,
649 pwgts[iargmin(nparts, pwgts)], imax(nparts, pwgts),
650 ComputeLoadImbalance(graph, nparts, ctrl->pijbm),
651 graph->nbnd, nmoved, graph->mincut, graph->minvol);
652 if (ctrl->minconn)
653 printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
654 printf("\n");
655 }
656
657 if (nmoved == 0 ||
658 (omode == OMODE_REFINE && graph->minvol == oldvol && graph->mincut == oldcut))
659 break;
660 }
661
662 ipqDestroy(queue);
663
664 WCOREPOP;
665 }
666
667
668 /*************************************************************************/
669 /*! K-way partitioning optimization in which the vertices are visited in
670 decreasing ed/sqrt(nnbrs)-id order. Note this is just an
671 approximation, as the ed is often split across different subdomains
672 and the sqrt(nnbrs) is just a crude approximation.
673
674 \param graph is the graph that is being refined.
675 \param niter is the number of refinement iterations.
676 \param ffactor is the \em fudge-factor for allowing positive gain moves
677 to violate the max-pwgt constraint.
678 \param omode is the type of optimization that will performed among
679 OMODE_REFINE and OMODE_BALANCE
680
681
682 */
683 /**************************************************************************/
684 void Greedy_McKWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter,
685 real_t ffactor, idx_t omode)
686 {
687 /* Common variables to all types of kway-refinement/balancing routines */
688 idx_t i, ii, iii, j, k, l, pass, nvtxs, ncon, nparts, gain;
689 idx_t from, me, to, cto, oldcut;
690 idx_t *xadj, *vwgt, *adjncy, *adjwgt;
691 idx_t *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt;
692 idx_t nmoved, nupd, *vstatus, *updptr, *updind;
693 idx_t maxndoms, *safetos=NULL, *nads=NULL, *doms=NULL, **adids=NULL, **adwgts=NULL;
694 idx_t *bfslvl=NULL, *bfsind=NULL, *bfsmrk=NULL;
695 idx_t bndtype = (omode == OMODE_REFINE ? BNDTYPE_REFINE : BNDTYPE_BALANCE);
696 real_t *ubfactors, *pijbm;
697 real_t origbal;
698
699 /* Edgecut-specific/different variables */
700 idx_t nbnd, oldnnbrs;
701 rpq_t *queue;
702 real_t rgain;
703 ckrinfo_t *myrinfo;
704 cnbr_t *mynbrs;
705
706 WCOREPUSH;
707
708 /* Link the graph fields */
709 nvtxs = graph->nvtxs;
710 ncon = graph->ncon;
711 xadj = graph->xadj;
712 vwgt = graph->vwgt;
713 adjncy = graph->adjncy;
714 adjwgt = graph->adjwgt;
715
716 bndind = graph->bndind;
717 bndptr = graph->bndptr;
718
719 where = graph->where;
720 pwgts = graph->pwgts;
721
722 nparts = ctrl->nparts;
723 pijbm = ctrl->pijbm;
724
725
726 /* Determine the ubfactors. The method used is different based on omode.
727 When OMODE_BALANCE, the ubfactors are those supplied by the user.
728 When OMODE_REFINE, the ubfactors are the max of the current partition
729 and the user-specified ones. */
730 ubfactors = rwspacemalloc(ctrl, ncon);
731 ComputeLoadImbalanceVec(graph, nparts, pijbm, ubfactors);
732 origbal = rvecmaxdiff(ncon, ubfactors, ctrl->ubfactors);
733 if (omode == OMODE_BALANCE) {
734 rcopy(ncon, ctrl->ubfactors, ubfactors);
735 }
736 else {
737 for (i=0; i<ncon; i++)
738 ubfactors[i] = (ubfactors[i] > ctrl->ubfactors[i] ? ubfactors[i] : ctrl->ubfactors[i]);
739 }
740
741
742 /* Setup the weight intervals of the various subdomains */
743 minwgt = iwspacemalloc(ctrl, nparts*ncon);
744 maxwgt = iwspacemalloc(ctrl, nparts*ncon);
745
746 for (i=0; i<nparts; i++) {
747 for (j=0; j<ncon; j++) {
748 maxwgt[i*ncon+j] = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*ubfactors[j];
749 /*minwgt[i*ncon+j] = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*(.9/ubfactors[j]);*/
750 minwgt[i*ncon+j] = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*.2;
751 }
752 }
753
754 perm = iwspacemalloc(ctrl, nvtxs);
755
756
757 /* This stores the valid target subdomains. It is used when ctrl->minconn to
758 control the subdomains to which moves are allowed to be made.
759 When ctrl->minconn is false, the default values of 2 allow all moves to
760 go through and it does not interfere with the zero-gain move selection. */
761 safetos = iset(nparts, 2, iwspacemalloc(ctrl, nparts));
762
763 if (ctrl->minconn) {
764 ComputeSubDomainGraph(ctrl, graph);
765
766 nads = ctrl->nads;
767 adids = ctrl->adids;
768 adwgts = ctrl->adwgts;
769 doms = iset(nparts, 0, ctrl->pvec1);
770 }
771
772
773 /* Setup updptr, updind like boundary info to keep track of the vertices whose
774 vstatus's need to be reset at the end of the inner iteration */
775 vstatus = iset(nvtxs, VPQSTATUS_NOTPRESENT, iwspacemalloc(ctrl, nvtxs));
776 updptr = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
777 updind = iwspacemalloc(ctrl, nvtxs);
778
779 if (ctrl->contig) {
780 /* The arrays that will be used for limited check of articulation points */
781 bfslvl = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
782 bfsind = iwspacemalloc(ctrl, nvtxs);
783 bfsmrk = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
784 }
785
786 if (ctrl->dbglvl&METIS_DBG_REFINE) {
787 printf("%s: [%6"PRIDX" %6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL"(%.3"PRREAL"),"
788 " Nv-Nb[%6"PRIDX" %6"PRIDX"], Cut: %6"PRIDX", (%"PRIDX")",
789 (omode == OMODE_REFINE ? "GRC" : "GBC"),
790 imin(nparts*ncon, pwgts), imax(nparts*ncon, pwgts), imax(nparts*ncon, maxwgt),
791 ComputeLoadImbalance(graph, nparts, pijbm), origbal,
792 graph->nvtxs, graph->nbnd, graph->mincut, niter);
793 if (ctrl->minconn)
794 printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
795 printf("\n");
796 }
797
798 queue = rpqCreate(nvtxs);
799
800
801 /*=====================================================================
802 * The top-level refinement loop
803 *======================================================================*/
804 for (pass=0; pass<niter; pass++) {
805 ASSERT(ComputeCut(graph, where) == graph->mincut);
806
807 /* In balancing mode, exit as soon as balance is reached */
808 if (omode == OMODE_BALANCE && IsBalanced(ctrl, graph, 0))
809 break;
810
811 oldcut = graph->mincut;
812 nbnd = graph->nbnd;
813 nupd = 0;
814
815 if (ctrl->minconn)
816 maxndoms = imax(nparts, nads);
817
818 /* Insert the boundary vertices in the priority queue */
819 irandArrayPermute(nbnd, perm, nbnd/4, 1);
820 for (ii=0; ii<nbnd; ii++) {
821 i = bndind[perm[ii]];
822 rgain = (graph->ckrinfo[i].nnbrs > 0 ?
823 1.0*graph->ckrinfo[i].ed/sqrt(graph->ckrinfo[i].nnbrs) : 0.0)
824 - graph->ckrinfo[i].id;
825 rpqInsert(queue, i, rgain);
826 vstatus[i] = VPQSTATUS_PRESENT;
827 ListInsert(nupd, updind, updptr, i);
828 }
829
830 /* Start extracting vertices from the queue and try to move them */
831 for (nmoved=0, iii=0;;iii++) {
832 if ((i = rpqGetTop(queue)) == -1)
833 break;
834 vstatus[i] = VPQSTATUS_EXTRACTED;
835
836 myrinfo = graph->ckrinfo+i;
837 mynbrs = ctrl->cnbrpool + myrinfo->inbr;
838
839 from = where[i];
840
841 /* Prevent moves that make 'from' domain underbalanced */
842 if (omode == OMODE_REFINE) {
843 if (myrinfo->id > 0 &&
844 !ivecaxpygez(ncon, -1, vwgt+i*ncon, pwgts+from*ncon, minwgt+from*ncon))
845 continue;
846 }
847 else { /* OMODE_BALANCE */
848 if (!ivecaxpygez(ncon, -1, vwgt+i*ncon, pwgts+from*ncon, minwgt+from*ncon))
849 continue;
850 }
851
852 if (ctrl->contig && IsArticulationNode(i, xadj, adjncy, where, bfslvl, bfsind, bfsmrk))
853 continue;
854
855 if (ctrl->minconn)
856 SelectSafeTargetSubdomains(myrinfo, mynbrs, nads, adids, maxndoms, safetos, doms);
857
858 /* Find the most promising subdomain to move to */
859 if (omode == OMODE_REFINE) {
860 for (k=myrinfo->nnbrs-1; k>=0; k--) {
861 if (!safetos[to=mynbrs[k].pid])
862 continue;
863 gain = mynbrs[k].ed-myrinfo->id;
864 if (gain >= 0 && ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon))
865 break;
866 }
867 if (k < 0)
868 continue; /* break out if you did not find a candidate */
869
870 cto = to;
871 for (j=k-1; j>=0; j--) {
872 if (!safetos[to=mynbrs[j].pid])
873 continue;
874 if ((mynbrs[j].ed > mynbrs[k].ed &&
875 ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon))
876 ||
877 (mynbrs[j].ed == mynbrs[k].ed &&
878 BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
879 1, pwgts+cto*ncon, pijbm+cto*ncon,
880 1, pwgts+to*ncon, pijbm+to*ncon))) {
881 k = j;
882 cto = to;
883 }
884 }
885 to = cto;
886
887 gain = mynbrs[k].ed-myrinfo->id;
888 if (!(gain > 0
889 || (gain == 0
890 && (BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
891 -1, pwgts+from*ncon, pijbm+from*ncon,
892 +1, pwgts+to*ncon, pijbm+to*ncon)
893 || (iii%2 == 0 && safetos[to] == 2)
894 )
895 )
896 )
897 )
898 continue;
899 }
900 else { /* OMODE_BALANCE */
901 for (k=myrinfo->nnbrs-1; k>=0; k--) {
902 if (!safetos[to=mynbrs[k].pid])
903 continue;
904 if (ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon) ||
905 BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
906 -1, pwgts+from*ncon, pijbm+from*ncon,
907 +1, pwgts+to*ncon, pijbm+to*ncon))
908 break;
909 }
910 if (k < 0)
911 continue; /* break out if you did not find a candidate */
912
913 cto = to;
914 for (j=k-1; j>=0; j--) {
915 if (!safetos[to=mynbrs[j].pid])
916 continue;
917 if (BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
918 1, pwgts+cto*ncon, pijbm+cto*ncon,
919 1, pwgts+to*ncon, pijbm+to*ncon)) {
920 k = j;
921 cto = to;
922 }
923 }
924 to = cto;
925
926 if (mynbrs[k].ed-myrinfo->id < 0 &&
927 !BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
928 -1, pwgts+from*ncon, pijbm+from*ncon,
929 +1, pwgts+to*ncon, pijbm+to*ncon))
930 continue;
931 }
932
933
934
935 /*=====================================================================
936 * If we got here, we can now move the vertex from 'from' to 'to'
937 *======================================================================*/
938 graph->mincut -= mynbrs[k].ed-myrinfo->id;
939 nmoved++;
940
941 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
942 printf("\t\tMoving %6"PRIDX" to %3"PRIDX". Gain: %4"PRIDX". Cut: %6"PRIDX"\n",
943 i, to, mynbrs[k].ed-myrinfo->id, graph->mincut));
944
945 /* Update the subdomain connectivity information */
946 if (ctrl->minconn) {
947 /* take care of i's move itself */
948 UpdateEdgeSubDomainGraph(ctrl, from, to, myrinfo->id-mynbrs[k].ed, &maxndoms);
949
950 /* take care of the adjancent vertices */
951 for (j=xadj[i]; j<xadj[i+1]; j++) {
952 me = where[adjncy[j]];
953 if (me != from && me != to) {
954 UpdateEdgeSubDomainGraph(ctrl, from, me, -adjwgt[j], &maxndoms);
955 UpdateEdgeSubDomainGraph(ctrl, to, me, adjwgt[j], &maxndoms);
956 }
957 }
958 }
959
960 /* Update ID/ED and BND related information for the moved vertex */
961 iaxpy(ncon, 1, vwgt+i*ncon, 1, pwgts+to*ncon, 1);
962 iaxpy(ncon, -1, vwgt+i*ncon, 1, pwgts+from*ncon, 1);
963 UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where,
964 nbnd, bndptr, bndind, bndtype);
965
966 /* Update the degrees of adjacent vertices */
967 for (j=xadj[i]; j<xadj[i+1]; j++) {
968 ii = adjncy[j];
969 me = where[ii];
970 myrinfo = graph->ckrinfo+ii;
971
972 oldnnbrs = myrinfo->nnbrs;
973
974 UpdateAdjacentVertexInfoAndBND(ctrl, ii, xadj[ii+1]-xadj[ii], me,
975 from, to, myrinfo, adjwgt[j], nbnd, bndptr, bndind, bndtype);
976
977 UpdateQueueInfo(queue, vstatus, ii, me, from, to, myrinfo, oldnnbrs,
978 nupd, updptr, updind, bndtype);
979
980 ASSERT(myrinfo->nnbrs <= xadj[ii+1]-xadj[ii]);
981 }
982 }
983
984 graph->nbnd = nbnd;
985
986 /* Reset the vstatus and associated data structures */
987 for (i=0; i<nupd; i++) {
988 ASSERT(updptr[updind[i]] != -1);
989 ASSERT(vstatus[updind[i]] != VPQSTATUS_NOTPRESENT);
990 vstatus[updind[i]] = VPQSTATUS_NOTPRESENT;
991 updptr[updind[i]] = -1;
992 }
993
994 if (ctrl->dbglvl&METIS_DBG_REFINE) {
995 printf("\t[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL", Nb: %6"PRIDX"."
996 " Nmoves: %5"PRIDX", Cut: %6"PRIDX", Vol: %6"PRIDX,
997 imin(nparts*ncon, pwgts), imax(nparts*ncon, pwgts),
998 ComputeLoadImbalance(graph, nparts, pijbm),
999 graph->nbnd, nmoved, graph->mincut, ComputeVolume(graph, where));
1000 if (ctrl->minconn)
1001 printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
1002 printf("\n");
1003 }
1004
1005 if (nmoved == 0 || (omode == OMODE_REFINE && graph->mincut == oldcut))
1006 break;
1007 }
1008
1009 rpqDestroy(queue);
1010
1011 WCOREPOP;
1012 }
1013
1014
1015 /*************************************************************************/
1016 /*! K-way refinement that minimizes the communication volume. This is a
1017 greedy routine and the vertices are visited in decreasing gv order.
1018
1019 \param graph is the graph that is being refined.
1020 \param niter is the number of refinement iterations.
1021 \param ffactor is the \em fudge-factor for allowing positive gain moves
1022 to violate the max-pwgt constraint.
1023
1024 */
1025 /**************************************************************************/
1026 void Greedy_McKWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter,
1027 real_t ffactor, idx_t omode)
1028 {
1029 /* Common variables to all types of kway-refinement/balancing routines */
1030 idx_t i, ii, iii, j, k, l, pass, nvtxs, ncon, nparts, gain;
1031 idx_t from, me, to, cto, oldcut;
1032 idx_t *xadj, *vwgt, *adjncy;
1033 idx_t *where, *pwgts, *perm, *bndptr, *bndind, *minwgt, *maxwgt;
1034 idx_t nmoved, nupd, *vstatus, *updptr, *updind;
1035 idx_t maxndoms, *safetos=NULL, *nads=NULL, *doms=NULL, **adids=NULL, **adwgts=NULL;
1036 idx_t *bfslvl=NULL, *bfsind=NULL, *bfsmrk=NULL;
1037 idx_t bndtype = (omode == OMODE_REFINE ? BNDTYPE_REFINE : BNDTYPE_BALANCE);
1038 real_t *ubfactors, *pijbm;
1039 real_t origbal;
1040
1041 /* Volume-specific/different variables */
1042 ipq_t *queue;
1043 idx_t oldvol, xgain;
1044 idx_t *vmarker, *pmarker, *modind;
1045 vkrinfo_t *myrinfo;
1046 vnbr_t *mynbrs;
1047
1048 WCOREPUSH;
1049
1050 /* Link the graph fields */
1051 nvtxs = graph->nvtxs;
1052 ncon = graph->ncon;
1053 xadj = graph->xadj;
1054 vwgt = graph->vwgt;
1055 adjncy = graph->adjncy;
1056 bndptr = graph->bndptr;
1057 bndind = graph->bndind;
1058 where = graph->where;
1059 pwgts = graph->pwgts;
1060
1061 nparts = ctrl->nparts;
1062 pijbm = ctrl->pijbm;
1063
1064
1065 /* Determine the ubfactors. The method used is different based on omode.
1066 When OMODE_BALANCE, the ubfactors are those supplied by the user.
1067 When OMODE_REFINE, the ubfactors are the max of the current partition
1068 and the user-specified ones. */
1069 ubfactors = rwspacemalloc(ctrl, ncon);
1070 ComputeLoadImbalanceVec(graph, nparts, pijbm, ubfactors);
1071 origbal = rvecmaxdiff(ncon, ubfactors, ctrl->ubfactors);
1072 if (omode == OMODE_BALANCE) {
1073 rcopy(ncon, ctrl->ubfactors, ubfactors);
1074 }
1075 else {
1076 for (i=0; i<ncon; i++)
1077 ubfactors[i] = (ubfactors[i] > ctrl->ubfactors[i] ? ubfactors[i] : ctrl->ubfactors[i]);
1078 }
1079
1080
1081 /* Setup the weight intervals of the various subdomains */
1082 minwgt = iwspacemalloc(ctrl, nparts*ncon);
1083 maxwgt = iwspacemalloc(ctrl, nparts*ncon);
1084
1085 for (i=0; i<nparts; i++) {
1086 for (j=0; j<ncon; j++) {
1087 maxwgt[i*ncon+j] = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*ubfactors[j];
1088 /*minwgt[i*ncon+j] = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*(.9/ubfactors[j]); */
1089 minwgt[i*ncon+j] = ctrl->tpwgts[i*ncon+j]*graph->tvwgt[j]*.2;
1090 }
1091 }
1092
1093 perm = iwspacemalloc(ctrl, nvtxs);
1094
1095
1096 /* This stores the valid target subdomains. It is used when ctrl->minconn to
1097 control the subdomains to which moves are allowed to be made.
1098 When ctrl->minconn is false, the default values of 2 allow all moves to
1099 go through and it does not interfere with the zero-gain move selection. */
1100 safetos = iset(nparts, 2, iwspacemalloc(ctrl, nparts));
1101
1102 if (ctrl->minconn) {
1103 ComputeSubDomainGraph(ctrl, graph);
1104
1105 nads = ctrl->nads;
1106 adids = ctrl->adids;
1107 adwgts = ctrl->adwgts;
1108 doms = iset(nparts, 0, ctrl->pvec1);
1109 }
1110
1111
1112 /* Setup updptr, updind like boundary info to keep track of the vertices whose
1113 vstatus's need to be reset at the end of the inner iteration */
1114 vstatus = iset(nvtxs, VPQSTATUS_NOTPRESENT, iwspacemalloc(ctrl, nvtxs));
1115 updptr = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
1116 updind = iwspacemalloc(ctrl, nvtxs);
1117
1118 if (ctrl->contig) {
1119 /* The arrays that will be used for limited check of articulation points */
1120 bfslvl = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
1121 bfsind = iwspacemalloc(ctrl, nvtxs);
1122 bfsmrk = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
1123 }
1124
1125 /* Vol-refinement specific working arrays */
1126 modind = iwspacemalloc(ctrl, nvtxs);
1127 vmarker = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
1128 pmarker = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
1129
1130 if (ctrl->dbglvl&METIS_DBG_REFINE) {
1131 printf("%s: [%6"PRIDX" %6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL"(%.3"PRREAL"),"
1132 ", Nv-Nb[%6"PRIDX" %6"PRIDX"], Cut: %5"PRIDX", Vol: %5"PRIDX", (%"PRIDX")",
1133 (omode == OMODE_REFINE ? "GRV" : "GBV"),
1134 imin(nparts*ncon, pwgts), imax(nparts*ncon, pwgts), imax(nparts*ncon, maxwgt),
1135 ComputeLoadImbalance(graph, nparts, pijbm), origbal,
1136 graph->nvtxs, graph->nbnd, graph->mincut, graph->minvol, niter);
1137 if (ctrl->minconn)
1138 printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
1139 printf("\n");
1140 }
1141
1142 queue = ipqCreate(nvtxs);
1143
1144
1145 /*=====================================================================
1146 * The top-level refinement loop
1147 *======================================================================*/
1148 for (pass=0; pass<niter; pass++) {
1149 ASSERT(ComputeVolume(graph, where) == graph->minvol);
1150
1151 /* In balancing mode, exit as soon as balance is reached */
1152 if (omode == OMODE_BALANCE && IsBalanced(ctrl, graph, 0))
1153 break;
1154
1155 oldcut = graph->mincut;
1156 oldvol = graph->minvol;
1157 nupd = 0;
1158
1159 if (ctrl->minconn)
1160 maxndoms = imax(nparts, nads);
1161
1162 /* Insert the boundary vertices in the priority queue */
1163 irandArrayPermute(graph->nbnd, perm, graph->nbnd/4, 1);
1164 for (ii=0; ii<graph->nbnd; ii++) {
1165 i = bndind[perm[ii]];
1166 ipqInsert(queue, i, graph->vkrinfo[i].gv);
1167 vstatus[i] = VPQSTATUS_PRESENT;
1168 ListInsert(nupd, updind, updptr, i);
1169 }
1170
1171 /* Start extracting vertices from the queue and try to move them */
1172 for (nmoved=0, iii=0;;iii++) {
1173 if ((i = ipqGetTop(queue)) == -1)
1174 break;
1175 vstatus[i] = VPQSTATUS_EXTRACTED;
1176
1177 myrinfo = graph->vkrinfo+i;
1178 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
1179
1180 from = where[i];
1181
1182 /* Prevent moves that make 'from' domain underbalanced */
1183 if (omode == OMODE_REFINE) {
1184 if (myrinfo->nid > 0 &&
1185 !ivecaxpygez(ncon, -1, vwgt+i*ncon, pwgts+from*ncon, minwgt+from*ncon))
1186 continue;
1187 }
1188 else { /* OMODE_BALANCE */
1189 if (!ivecaxpygez(ncon, -1, vwgt+i*ncon, pwgts+from*ncon, minwgt+from*ncon))
1190 continue;
1191 }
1192
1193 if (ctrl->contig && IsArticulationNode(i, xadj, adjncy, where, bfslvl, bfsind, bfsmrk))
1194 continue;
1195
1196 if (ctrl->minconn)
1197 SelectSafeTargetSubdomains(myrinfo, mynbrs, nads, adids, maxndoms, safetos, doms);
1198
1199 xgain = (myrinfo->nid == 0 && myrinfo->ned > 0 ? graph->vsize[i] : 0);
1200
1201 /* Find the most promising subdomain to move to */
1202 if (omode == OMODE_REFINE) {
1203 for (k=myrinfo->nnbrs-1; k>=0; k--) {
1204 if (!safetos[to=mynbrs[k].pid])
1205 continue;
1206 gain = mynbrs[k].gv + xgain;
1207 if (gain >= 0 && ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon))
1208 break;
1209 }
1210 if (k < 0)
1211 continue; /* break out if you did not find a candidate */
1212
1213 cto = to;
1214 for (j=k-1; j>=0; j--) {
1215 if (!safetos[to=mynbrs[j].pid])
1216 continue;
1217 gain = mynbrs[j].gv + xgain;
1218 if ((mynbrs[j].gv > mynbrs[k].gv &&
1219 ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon))
1220 ||
1221 (mynbrs[j].gv == mynbrs[k].gv &&
1222 mynbrs[j].ned > mynbrs[k].ned &&
1223 ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon))
1224 ||
1225 (mynbrs[j].gv == mynbrs[k].gv &&
1226 mynbrs[j].ned == mynbrs[k].ned &&
1227 BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
1228 1, pwgts+cto*ncon, pijbm+cto*ncon,
1229 1, pwgts+to*ncon, pijbm+to*ncon))) {
1230 k = j;
1231 cto = to;
1232 }
1233 }
1234 to = cto;
1235
1236 j = 0;
1237 if (xgain+mynbrs[k].gv > 0 || mynbrs[k].ned-myrinfo->nid > 0)
1238 j = 1;
1239 else if (mynbrs[k].ned-myrinfo->nid == 0) {
1240 if ((iii%2 == 0 && safetos[to] == 2) ||
1241 BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
1242 -1, pwgts+from*ncon, pijbm+from*ncon,
1243 +1, pwgts+to*ncon, pijbm+to*ncon))
1244 j = 1;
1245 }
1246 if (j == 0)
1247 continue;
1248 }
1249 else { /* OMODE_BALANCE */
1250 for (k=myrinfo->nnbrs-1; k>=0; k--) {
1251 if (!safetos[to=mynbrs[k].pid])
1252 continue;
1253 if (ivecaxpylez(ncon, 1, vwgt+i*ncon, pwgts+to*ncon, maxwgt+to*ncon) ||
1254 BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
1255 -1, pwgts+from*ncon, pijbm+from*ncon,
1256 +1, pwgts+to*ncon, pijbm+to*ncon))
1257 break;
1258 }
1259 if (k < 0)
1260 continue; /* break out if you did not find a candidate */
1261
1262 cto = to;
1263 for (j=k-1; j>=0; j--) {
1264 if (!safetos[to=mynbrs[j].pid])
1265 continue;
1266 if (BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
1267 1, pwgts+cto*ncon, pijbm+cto*ncon,
1268 1, pwgts+to*ncon, pijbm+to*ncon)) {
1269 k = j;
1270 cto = to;
1271 }
1272 }
1273 to = cto;
1274
1275 if ((xgain+mynbrs[k].gv < 0 ||
1276 (xgain+mynbrs[k].gv == 0 && mynbrs[k].ned-myrinfo->nid < 0))
1277 &&
1278 !BetterBalanceKWay(ncon, vwgt+i*ncon, ubfactors,
1279 -1, pwgts+from*ncon, pijbm+from*ncon,
1280 +1, pwgts+to*ncon, pijbm+to*ncon))
1281 continue;
1282 }
1283
1284
1285 /*=====================================================================
1286 * If we got here, we can now move the vertex from 'from' to 'to'
1287 *======================================================================*/
1288 graph->mincut -= mynbrs[k].ned-myrinfo->nid;
1289 graph->minvol -= (xgain+mynbrs[k].gv);
1290 where[i] = to;
1291 nmoved++;
1292
1293 IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO,
1294 printf("\t\tMoving %6"PRIDX" from %3"PRIDX" to %3"PRIDX". "
1295 "Gain: [%4"PRIDX" %4"PRIDX"]. Cut: %6"PRIDX", Vol: %6"PRIDX"\n",
1296 i, from, to, xgain+mynbrs[k].gv, mynbrs[k].ned-myrinfo->nid,
1297 graph->mincut, graph->minvol));
1298
1299 /* Update the subdomain connectivity information */
1300 if (ctrl->minconn) {
1301 /* take care of i's move itself */
1302 UpdateEdgeSubDomainGraph(ctrl, from, to, myrinfo->nid-mynbrs[k].ned, &maxndoms);
1303
1304 /* take care of the adjancent vertices */
1305 for (j=xadj[i]; j<xadj[i+1]; j++) {
1306 me = where[adjncy[j]];
1307 if (me != from && me != to) {
1308 UpdateEdgeSubDomainGraph(ctrl, from, me, -1, &maxndoms);
1309 UpdateEdgeSubDomainGraph(ctrl, to, me, 1, &maxndoms);
1310 }
1311 }
1312 }
1313
1314 /* Update pwgts */
1315 iaxpy(ncon, 1, vwgt+i*ncon, 1, pwgts+to*ncon, 1);
1316 iaxpy(ncon, -1, vwgt+i*ncon, 1, pwgts+from*ncon, 1);
1317
1318 /* Update the id/ed/gains/bnd/queue of potentially affected nodes */
1319 KWayVolUpdate(ctrl, graph, i, from, to, queue, vstatus, &nupd, updptr,
1320 updind, bndtype, vmarker, pmarker, modind);
1321
1322 /*CheckKWayVolPartitionParams(ctrl, graph); */
1323 }
1324
1325
1326 /* Reset the vstatus and associated data structures */
1327 for (i=0; i<nupd; i++) {
1328 ASSERT(updptr[updind[i]] != -1);
1329 ASSERT(vstatus[updind[i]] != VPQSTATUS_NOTPRESENT);
1330 vstatus[updind[i]] = VPQSTATUS_NOTPRESENT;
1331 updptr[updind[i]] = -1;
1332 }
1333
1334 if (ctrl->dbglvl&METIS_DBG_REFINE) {
1335 printf("\t[%6"PRIDX" %6"PRIDX"], Bal: %5.3"PRREAL", Nb: %6"PRIDX"."
1336 " Nmoves: %5"PRIDX", Cut: %6"PRIDX", Vol: %6"PRIDX,
1337 imin(nparts*ncon, pwgts), imax(nparts*ncon, pwgts),
1338 ComputeLoadImbalance(graph, nparts, pijbm),
1339 graph->nbnd, nmoved, graph->mincut, graph->minvol);
1340 if (ctrl->minconn)
1341 printf(", Doms: [%3"PRIDX" %4"PRIDX"]", imax(nparts, nads), isum(nparts, nads,1));
1342 printf("\n");
1343 }
1344
1345 if (nmoved == 0 ||
1346 (omode == OMODE_REFINE && graph->minvol == oldvol && graph->mincut == oldcut))
1347 break;
1348 }
1349
1350 ipqDestroy(queue);
1351
1352 WCOREPOP;
1353 }
1354
1355
1356 /*************************************************************************/
1357 /*! This function performs an approximate articulation vertex test.
1358 It assumes that the bfslvl, bfsind, and bfsmrk arrays are initialized
1359 appropriately. */
1360 /*************************************************************************/
1361 idx_t IsArticulationNode(idx_t i, idx_t *xadj, idx_t *adjncy, idx_t *where,
1362 idx_t *bfslvl, idx_t *bfsind, idx_t *bfsmrk)
1363 {
1364 idx_t ii, j, k=0, head, tail, nhits, tnhits, from, BFSDEPTH=5;
1365
1366 from = where[i];
1367
1368 /* Determine if the vertex is safe to move from a contiguity standpoint */
1369 for (tnhits=0, j=xadj[i]; j<xadj[i+1]; j++) {
1370 if (where[adjncy[j]] == from) {
1371 ASSERT(bfsmrk[adjncy[j]] == 0);
1372 ASSERT(bfslvl[adjncy[j]] == 0);
1373 bfsmrk[k=adjncy[j]] = 1;
1374 tnhits++;
1375 }
1376 }
1377
1378 /* Easy cases */
1379 if (tnhits == 0)
1380 return 0;
1381 if (tnhits == 1) {
1382 bfsmrk[k] = 0;
1383 return 0;
1384 }
1385
1386 ASSERT(bfslvl[i] == 0);
1387 bfslvl[i] = 1;
1388
1389 bfsind[0] = k; /* That was the last one from the previous loop */
1390 bfslvl[k] = 1;
1391 bfsmrk[k] = 0;
1392 head = 0;
1393 tail = 1;
1394
1395 /* Do a limited BFS traversal to see if you can get to all the other nodes */
1396 for (nhits=1; head<tail; ) {
1397 ii = bfsind[head++];
1398 for (j=xadj[ii]; j<xadj[ii+1]; j++) {
1399 if (where[k=adjncy[j]] == from) {
1400 if (bfsmrk[k]) {
1401 bfsmrk[k] = 0;
1402 if (++nhits == tnhits)
1403 break;
1404 }
1405 if (bfslvl[k] == 0 && bfslvl[ii] < BFSDEPTH) {
1406 bfsind[tail++] = k;
1407 bfslvl[k] = bfslvl[ii]+1;
1408 }
1409 }
1410 }
1411 if (nhits == tnhits)
1412 break;
1413 }
1414
1415 /* Reset the various BFS related arrays */
1416 bfslvl[i] = 0;
1417 for (j=0; j<tail; j++)
1418 bfslvl[bfsind[j]] = 0;
1419
1420
1421 /* Reset the bfsmrk array for the next vertex when has not already being cleared */
1422 if (nhits < tnhits) {
1423 for (j=xadj[i]; j<xadj[i+1]; j++)
1424 if (where[adjncy[j]] == from)
1425 bfsmrk[adjncy[j]] = 0;
1426 }
1427
1428 return (nhits != tnhits);
1429 }
1430
1431
1432 /*************************************************************************/
1433 /*!
1434 This function updates the edge and volume gains due to a vertex movement.
1435 v from 'from' to 'to'.
1436
1437 \param ctrl is the control structure.
1438 \param graph is the graph being partitioned.
1439 \param v is the vertex that is moving.
1440 \param from is the original partition of v.
1441 \param to is the new partition of v.
1442 \param queue is the priority queue. If the queue is NULL, no priority-queue
1443 related updates are performed.
1444 \param vstatus is an array that marks the status of the vertex in terms
1445 of the priority queue. If queue is NULL, this parameter is ignored.
1446 \param r_nqupd is the number of vertices that have been inserted/removed
1447 from the queue. If queue is NULL, this parameter is ignored.
1448 \param updptr stores the index of each vertex in updind. If queue is NULL,
1449 this parameter is ignored.
1450 \param updind is the list of vertices that have been inserted/removed from
1451 the queue. If queue is NULL, this parameter is ignored.
1452 \param vmarker is of size nvtxs and is used internally as a temporary array.
1453 On entry and return all of its entries are 0.
1454 \param pmarker is of sie nparts and is used internally as a temporary marking
1455 array. On entry and return all of its entries are -1.
1456 \param modind is an array of size nvtxs and is used to keep track of the
1457 list of vertices whose gains need to be updated.
1458 */
1459 /*************************************************************************/
1460 void KWayVolUpdate(ctrl_t *ctrl, graph_t *graph, idx_t v, idx_t from,
1461 idx_t to, ipq_t *queue, idx_t *vstatus, idx_t *r_nupd, idx_t *updptr,
1462 idx_t *updind, idx_t bndtype, idx_t *vmarker, idx_t *pmarker,
1463 idx_t *modind)
1464 {
1465 idx_t i, ii, iii, j, jj, k, kk, l, u, nmod, other, me, myidx;
1466 idx_t *xadj, *vsize, *adjncy, *where;
1467 vkrinfo_t *myrinfo, *orinfo;
1468 vnbr_t *mynbrs, *onbrs;
1469
1470 xadj = graph->xadj;
1471 adjncy = graph->adjncy;
1472 vsize = graph->vsize;
1473 where = graph->where;
1474
1475 myrinfo = graph->vkrinfo+v;
1476 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
1477
1478
1479 /*======================================================================
1480 * Remove the contributions on the gain made by 'v'.
1481 *=====================================================================*/
1482 for (k=0; k<myrinfo->nnbrs; k++)
1483 pmarker[mynbrs[k].pid] = k;
1484 pmarker[from] = k;
1485
1486 myidx = pmarker[to]; /* Keep track of the index in mynbrs of the 'to' domain */
1487
1488 for (j=xadj[v]; j<xadj[v+1]; j++) {
1489 ii = adjncy[j];
1490 other = where[ii];
1491 orinfo = graph->vkrinfo+ii;
1492 onbrs = ctrl->vnbrpool + orinfo->inbr;
1493
1494 if (other == from) {
1495 for (k=0; k<orinfo->nnbrs; k++) {
1496 if (pmarker[onbrs[k].pid] == -1)
1497 onbrs[k].gv += vsize[v];
1498 }
1499 }
1500 else {
1501 ASSERT(pmarker[other] != -1);
1502
1503 if (mynbrs[pmarker[other]].ned > 1) {
1504 for (k=0; k<orinfo->nnbrs; k++) {
1505 if (pmarker[onbrs[k].pid] == -1)
1506 onbrs[k].gv += vsize[v];
1507 }
1508 }
1509 else { /* There is only one connection */
1510 for (k=0; k<orinfo->nnbrs; k++) {
1511 if (pmarker[onbrs[k].pid] != -1)
1512 onbrs[k].gv -= vsize[v];
1513 }
1514 }
1515 }
1516 }
1517
1518 for (k=0; k<myrinfo->nnbrs; k++)
1519 pmarker[mynbrs[k].pid] = -1;
1520 pmarker[from] = -1;
1521
1522
1523 /*======================================================================
1524 * Update the id/ed of vertex 'v'
1525 *=====================================================================*/
1526 if (myidx == -1) {
1527 myidx = myrinfo->nnbrs++;
1528 ASSERT(myidx < xadj[v+1]-xadj[v]);
1529 mynbrs[myidx].ned = 0;
1530 }
1531 myrinfo->ned += myrinfo->nid-mynbrs[myidx].ned;
1532 SWAP(myrinfo->nid, mynbrs[myidx].ned, j);
1533 if (mynbrs[myidx].ned == 0)
1534 mynbrs[myidx] = mynbrs[--myrinfo->nnbrs];
1535 else
1536 mynbrs[myidx].pid = from;
1537
1538
1539 /*======================================================================
1540 * Update the degrees of adjacent vertices and their volume gains
1541 *=====================================================================*/
1542 vmarker[v] = 1;
1543 modind[0] = v;
1544 nmod = 1;
1545 for (j=xadj[v]; j<xadj[v+1]; j++) {
1546 ii = adjncy[j];
1547 me = where[ii];
1548
1549 if (!vmarker[ii]) { /* The marking is done for boundary and max gv calculations */
1550 vmarker[ii] = 2;
1551 modind[nmod++] = ii;
1552 }
1553
1554 myrinfo = graph->vkrinfo+ii;
1555 if (myrinfo->inbr == -1)
1556 myrinfo->inbr = vnbrpoolGetNext(ctrl, xadj[ii+1]-xadj[ii]+1);
1557 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
1558
1559 if (me == from) {
1560 INC_DEC(myrinfo->ned, myrinfo->nid, 1);
1561 }
1562 else if (me == to) {
1563 INC_DEC(myrinfo->nid, myrinfo->ned, 1);
1564 }
1565
1566 /* Remove the edgeweight from the 'pid == from' entry of the vertex */
1567 if (me != from) {
1568 for (k=0; k<myrinfo->nnbrs; k++) {
1569 if (mynbrs[k].pid == from) {
1570 if (mynbrs[k].ned == 1) {
1571 mynbrs[k] = mynbrs[--myrinfo->nnbrs];
1572 vmarker[ii] = 1; /* You do a complete .gv calculation */
1573
1574 /* All vertices adjacent to 'ii' need to be updated */
1575 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
1576 u = adjncy[jj];
1577 other = where[u];
1578 orinfo = graph->vkrinfo+u;
1579 onbrs = ctrl->vnbrpool + orinfo->inbr;
1580
1581 for (kk=0; kk<orinfo->nnbrs; kk++) {
1582 if (onbrs[kk].pid == from) {
1583 onbrs[kk].gv -= vsize[ii];
1584 if (!vmarker[u]) { /* Need to update boundary etc */
1585 vmarker[u] = 2;
1586 modind[nmod++] = u;
1587 }
1588 break;
1589 }
1590 }
1591 }
1592 }
1593 else {
1594 mynbrs[k].ned--;
1595
1596 /* Update the gv due to single 'ii' connection to 'from' */
1597 if (mynbrs[k].ned == 1) {
1598 /* find the vertex 'u' that 'ii' was connected into 'from' */
1599 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
1600 u = adjncy[jj];
1601 other = where[u];
1602
1603 if (other == from) {
1604 orinfo = graph->vkrinfo+u;
1605 onbrs = ctrl->vnbrpool + orinfo->inbr;
1606
1607 /* The following is correct because domains in common
1608 between ii and u will lead to a reduction over the
1609 previous gain, whereas domains only in u but not in
1610 ii, will lead to no change as opposed to the earlier
1611 increase */
1612 for (kk=0; kk<orinfo->nnbrs; kk++)
1613 onbrs[kk].gv += vsize[ii];
1614
1615 if (!vmarker[u]) { /* Need to update boundary etc */
1616 vmarker[u] = 2;
1617 modind[nmod++] = u;
1618 }
1619 break;
1620 }
1621 }
1622 }
1623 }
1624 break;
1625 }
1626 }
1627 }
1628
1629
1630 /* Add the edgeweight to the 'pid == to' entry of the vertex */
1631 if (me != to) {
1632 for (k=0; k<myrinfo->nnbrs; k++) {
1633 if (mynbrs[k].pid == to) {
1634 mynbrs[k].ned++;
1635
1636 /* Update the gv due to non-single 'ii' connection to 'to' */
1637 if (mynbrs[k].ned == 2) {
1638 /* find the vertex 'u' that 'ii' was connected into 'to' */
1639 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
1640 u = adjncy[jj];
1641 other = where[u];
1642
1643 if (u != v && other == to) {
1644 orinfo = graph->vkrinfo+u;
1645 onbrs = ctrl->vnbrpool + orinfo->inbr;
1646 for (kk=0; kk<orinfo->nnbrs; kk++)
1647 onbrs[kk].gv -= vsize[ii];
1648
1649 if (!vmarker[u]) { /* Need to update boundary etc */
1650 vmarker[u] = 2;
1651 modind[nmod++] = u;
1652 }
1653 break;
1654 }
1655 }
1656 }
1657 break;
1658 }
1659 }
1660
1661 if (k == myrinfo->nnbrs) {
1662 mynbrs[myrinfo->nnbrs].pid = to;
1663 mynbrs[myrinfo->nnbrs++].ned = 1;
1664 vmarker[ii] = 1; /* You do a complete .gv calculation */
1665
1666 /* All vertices adjacent to 'ii' need to be updated */
1667 for (jj=xadj[ii]; jj<xadj[ii+1]; jj++) {
1668 u = adjncy[jj];
1669 other = where[u];
1670 orinfo = graph->vkrinfo+u;
1671 onbrs = ctrl->vnbrpool + orinfo->inbr;
1672
1673 for (kk=0; kk<orinfo->nnbrs; kk++) {
1674 if (onbrs[kk].pid == to) {
1675 onbrs[kk].gv += vsize[ii];
1676 if (!vmarker[u]) { /* Need to update boundary etc */
1677 vmarker[u] = 2;
1678 modind[nmod++] = u;
1679 }
1680 break;
1681 }
1682 }
1683 }
1684 }
1685 }
1686
1687 ASSERT(myrinfo->nnbrs <= xadj[ii+1]-xadj[ii]);
1688 }
1689
1690
1691 /*======================================================================
1692 * Add the contributions on the volume gain due to 'v'
1693 *=====================================================================*/
1694 myrinfo = graph->vkrinfo+v;
1695 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
1696 for (k=0; k<myrinfo->nnbrs; k++)
1697 pmarker[mynbrs[k].pid] = k;
1698 pmarker[to] = k;
1699
1700 for (j=xadj[v]; j<xadj[v+1]; j++) {
1701 ii = adjncy[j];
1702 other = where[ii];
1703 orinfo = graph->vkrinfo+ii;
1704 onbrs = ctrl->vnbrpool + orinfo->inbr;
1705
1706 if (other == to) {
1707 for (k=0; k<orinfo->nnbrs; k++) {
1708 if (pmarker[onbrs[k].pid] == -1)
1709 onbrs[k].gv -= vsize[v];
1710 }
1711 }
1712 else {
1713 ASSERT(pmarker[other] != -1);
1714
1715 if (mynbrs[pmarker[other]].ned > 1) {
1716 for (k=0; k<orinfo->nnbrs; k++) {
1717 if (pmarker[onbrs[k].pid] == -1)
1718 onbrs[k].gv -= vsize[v];
1719 }
1720 }
1721 else { /* There is only one connection */
1722 for (k=0; k<orinfo->nnbrs; k++) {
1723 if (pmarker[onbrs[k].pid] != -1)
1724 onbrs[k].gv += vsize[v];
1725 }
1726 }
1727 }
1728 }
1729 for (k=0; k<myrinfo->nnbrs; k++)
1730 pmarker[mynbrs[k].pid] = -1;
1731 pmarker[to] = -1;
1732
1733
1734 /*======================================================================
1735 * Recompute the volume information of the 'hard' nodes, and update the
1736 * max volume gain for all the modified vertices and the priority queue
1737 *=====================================================================*/
1738 for (iii=0; iii<nmod; iii++) {
1739 i = modind[iii];
1740 me = where[i];
1741
1742 myrinfo = graph->vkrinfo+i;
1743 mynbrs = ctrl->vnbrpool + myrinfo->inbr;
1744
1745 if (vmarker[i] == 1) { /* Only complete gain updates go through */
1746 for (k=0; k<myrinfo->nnbrs; k++)
1747 mynbrs[k].gv = 0;
1748
1749 for (j=xadj[i]; j<xadj[i+1]; j++) {
1750 ii = adjncy[j];
1751 other = where[ii];
1752 orinfo = graph->vkrinfo+ii;
1753 onbrs = ctrl->vnbrpool + orinfo->inbr;
1754
1755 for (kk=0; kk<orinfo->nnbrs; kk++)
1756 pmarker[onbrs[kk].pid] = kk;
1757 pmarker[other] = 1;
1758
1759 if (me == other) {
1760 /* Find which domains 'i' is connected and 'ii' is not and update their gain */
1761 for (k=0; k<myrinfo->nnbrs; k++) {
1762 if (pmarker[mynbrs[k].pid] == -1)
1763 mynbrs[k].gv -= vsize[ii];
1764 }
1765 }
1766 else {
1767 ASSERT(pmarker[me] != -1);
1768
1769 /* I'm the only connection of 'ii' in 'me' */
1770 if (onbrs[pmarker[me]].ned == 1) {
1771 /* Increase the gains for all the common domains between 'i' and 'ii' */
1772 for (k=0; k<myrinfo->nnbrs; k++) {
1773 if (pmarker[mynbrs[k].pid] != -1)
1774 mynbrs[k].gv += vsize[ii];
1775 }
1776 }
1777 else {
1778 /* Find which domains 'i' is connected and 'ii' is not and update their gain */
1779 for (k=0; k<myrinfo->nnbrs; k++) {
1780 if (pmarker[mynbrs[k].pid] == -1)
1781 mynbrs[k].gv -= vsize[ii];
1782 }
1783 }
1784 }
1785
1786 for (kk=0; kk<orinfo->nnbrs; kk++)
1787 pmarker[onbrs[kk].pid] = -1;
1788 pmarker[other] = -1;
1789
1790 }
1791 }
1792
1793 /* Compute the overall gv for that node */
1794 myrinfo->gv = IDX_MIN;
1795 for (k=0; k<myrinfo->nnbrs; k++) {
1796 if (mynbrs[k].gv > myrinfo->gv)
1797 myrinfo->gv = mynbrs[k].gv;
1798 }
1799
1800 /* Add the xtra gain due to id == 0 */
1801 if (myrinfo->ned > 0 && myrinfo->nid == 0)
1802 myrinfo->gv += vsize[i];
1803
1804
1805 /*======================================================================
1806 * Maintain a consistent boundary
1807 *=====================================================================*/
1808 if (bndtype == BNDTYPE_REFINE) {
1809 if (myrinfo->gv >= 0 && graph->bndptr[i] == -1)
1810 BNDInsert(graph->nbnd, graph->bndind, graph->bndptr, i);
1811
1812 if (myrinfo->gv < 0 && graph->bndptr[i] != -1)
1813 BNDDelete(graph->nbnd, graph->bndind, graph->bndptr, i);
1814 }
1815 else {
1816 if (myrinfo->ned > 0 && graph->bndptr[i] == -1)
1817 BNDInsert(graph->nbnd, graph->bndind, graph->bndptr, i);
1818
1819 if (myrinfo->ned == 0 && graph->bndptr[i] != -1)
1820 BNDDelete(graph->nbnd, graph->bndind, graph->bndptr, i);
1821 }
1822
1823
1824 /*======================================================================
1825 * Update the priority queue appropriately (if allowed)
1826 *=====================================================================*/
1827 if (queue != NULL) {
1828 if (vstatus[i] != VPQSTATUS_EXTRACTED) {
1829 if (graph->bndptr[i] != -1) { /* In-boundary vertex */
1830 if (vstatus[i] == VPQSTATUS_PRESENT) {
1831 ipqUpdate(queue, i, myrinfo->gv);
1832 }
1833 else {
1834 ipqInsert(queue, i, myrinfo->gv);
1835 vstatus[i] = VPQSTATUS_PRESENT;
1836 ListInsert(*r_nupd, updind, updptr, i);
1837 }
1838 }
1839 else { /* Off-boundary vertex */
1840 if (vstatus[i] == VPQSTATUS_PRESENT) {
1841 ipqDelete(queue, i);
1842 vstatus[i] = VPQSTATUS_NOTPRESENT;
1843 ListDelete(*r_nupd, updind, updptr, i);
1844 }
1845 }
1846 }
1847 }
1848
1849 vmarker[i] = 0;
1850 }
1851 }
1852
Charm++ is a parallel object-oriented programming language based on C++