kwayfm.c
Go to the documentation of this file.
1 
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 /*************************************************************************/
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 /*************************************************************************/
59 /**************************************************************************/
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 
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 /*************************************************************************/
369 /**************************************************************************/
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 
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 /*************************************************************************/
683 /**************************************************************************/
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 
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 /*************************************************************************/
1025 /**************************************************************************/
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 
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 /*************************************************************************/
1360 /*************************************************************************/
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 /*************************************************************************/
1459 /*************************************************************************/
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 
idx_t idx_t idx_t idx_t * vwgt
idx_t ned
idx_t * bndind
#define rvecmaxdiff
Definition: rename.h:135
#define ivecaxpygez
Definition: rename.h:139
void Greedy_McKWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
Definition: kwayfm.c:684
#define UpdateQueueInfo(queue, vstatus, vid, me, from, to, myrinfo, oldnnbrs, nupd, updptr, updind, bndtype)
real_t * tpwgts
#define iwspacemalloc
Definition: rename.h:256
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define irandArrayPermute
Definition: gklib_rename.h:62
idx_t * xadj
#define IDX_MIN
vnbr_t * vnbrpool
#define ipqDestroy
Definition: gklib_rename.h:49
#define rcopy
Definition: gklib_rename.h:80
#define vnbrpoolGetNext
Definition: rename.h:262
idx_t * pwgts
idx_t * adjwgt
idx_t * bndptr
idx_t idx_t * xadj
#define rwspacemalloc
Definition: rename.h:257
idx_t minvol
idx_t * where
idx_t pid
EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE FixedSegmentReturnType< internal::get_fixed_value< NType >::value >::Type tail(NType n)
#define BNDTYPE_BALANCE
Definition: libmetis/defs.h:31
void Greedy_KWayCutOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
Definition: kwayfm.c:60
idx_t idx_t idx_t idx_t idx_t idx_t idx_t * nparts
#define WCOREPUSH
idx_t nvtxs
idx_t * vsize
void gk_errexit(int signum, char *f_str,...)
Definition: error.c:77
mdbglvl_et dbglvl
#define ivecaxpylez
Definition: rename.h:138
NonlinearFactorGraph graph
void KWayVolUpdate(ctrl_t *ctrl, graph_t *graph, idx_t v, idx_t from, idx_t to, ipq_t *queue, idx_t *vstatus, idx_t *r_nupd, idx_t *updptr, idx_t *updind, idx_t bndtype, idx_t *vmarker, idx_t *pmarker, idx_t *modind)
Definition: kwayfm.c:1460
#define VPQSTATUS_PRESENT
Definition: libmetis/defs.h:38
#define ipqUpdate
Definition: gklib_rename.h:59
idx_t pid
#define ComputeLoadImbalance
Definition: rename.h:143
idx_t idx_t idx_t idx_t idx_t * vsize
#define PRIDX
#define ipqInsert
Definition: gklib_rename.h:53
#define ASSERT(expression)
Definition: ccolamd.c:872
#define ComputeLoadImbalanceVec
Definition: rename.h:146
static const Line3 l(Rot3(), 1, 1)
#define OMODE_BALANCE
Definition: libmetis/defs.h:35
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define SIGERR
Definition: gk_defs.h:38
#define rpqCreate
Definition: gklib_rename.h:98
#define UpdateEdgeSubDomainGraph
Definition: rename.h:162
#define ListDelete(n, lind, lptr, i)
int32_t idx_t
void Greedy_KWayOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
Definition: kwayfm.c:20
cnbr_t * cnbrpool
#define BNDTYPE_REFINE
Definition: libmetis/defs.h:30
idx_t nparts
#define rpqInsert
Definition: gklib_rename.h:104
Array< int, Dynamic, 1 > v
real_t * pijbm
idx_t idx_t idx_t idx_t idx_t * perm
idx_t ncon
#define iaxpy
Definition: gklib_rename.h:27
idx_t * nads
#define VPQSTATUS_NOTPRESENT
Definition: libmetis/defs.h:40
float real_t
idx_t * ncon
#define NULL
Definition: ccolamd.c:609
#define ComputeVolume
Definition: rename.h:63
idx_t mincut
#define rpqGetTop
Definition: gklib_rename.h:102
idx_t gv
#define isum
Definition: gklib_rename.h:72
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
#define INC_DEC(a, b, val)
Definition: gk_macros.h:20
idx_t * pvec1
#define ComputeSubDomainGraph
Definition: rename.h:161
real_t * ubfactors
#define iset
Definition: gklib_rename.h:67
idx_t idx_t idx_t idx_t * where
idx_t * adjncy
idx_t * tvwgt
EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE FixedSegmentReturnType< internal::get_fixed_value< NType >::value >::Type head(NType n)
idx_t contig
#define SelectSafeTargetSubdomains(myrinfo, mynbrs, nads, adids, maxndoms, safetos, vtmp)
idx_t idx_t idx_t * adjncy
idx_t ** adids
#define ipqDelete
Definition: gklib_rename.h:48
#define UpdateAdjacentVertexInfoAndBND(ctrl, vid, adjlen, me, from, to, myrinfo, ewgt, nbnd, bndptr, bndind, bndtype)
#define PRREAL
#define UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where, nbnd, bndptr, bndind, bndtype)
#define iargmin
Definition: gklib_rename.h:25
idx_t IsArticulationNode(idx_t i, idx_t *xadj, idx_t *adjncy, idx_t *where, idx_t *bfslvl, idx_t *bfsind, idx_t *bfsmrk)
Definition: kwayfm.c:1361
#define ListInsert(n, lind, lptr, i)
#define WCOREPOP
Jet< T, N > sqrt(const Jet< T, N > &f)
Definition: jet.h:418
idx_t ed
#define imax
Definition: gklib_rename.h:43
#define BetterBalanceKWay
Definition: rename.h:142
#define ipqGetTop
Definition: gklib_rename.h:51
#define OMODE_REFINE
Definition: libmetis/defs.h:34
idx_t ** adwgts
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
void Greedy_KWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
Definition: kwayfm.c:370
#define IsBalanced
Definition: rename.h:129
#define ipqCreate
Definition: gklib_rename.h:47
idx_t minconn
#define ComputeCut
Definition: rename.h:62
#define imin
Definition: gklib_rename.h:44
#define SWAP
std::ptrdiff_t j
mobjtype_et objtype
vkrinfo_t * vkrinfo
#define rpqDestroy
Definition: gklib_rename.h:100
ckrinfo_t * ckrinfo
void Greedy_McKWayVolOptimize(ctrl_t *ctrl, graph_t *graph, idx_t niter, real_t ffactor, idx_t omode)
Definition: kwayfm.c:1026
#define VPQSTATUS_EXTRACTED
Definition: libmetis/defs.h:39
idx_t * vwgt


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:30