fm.c
Go to the documentation of this file.
1 
11 #include "metislib.h"
12 
13 
14 /*************************************************************************
15 * This function performs an edge-based FM refinement
16 **************************************************************************/
17 void FM_2WayRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
18 {
19  if (graph->ncon == 1)
20  FM_2WayCutRefine(ctrl, graph, ntpwgts, niter);
21  else
22  FM_Mc2WayCutRefine(ctrl, graph, ntpwgts, niter);
23 }
24 
25 
26 /*************************************************************************/
28 /*************************************************************************/
29 void FM_2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
30 {
31  idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, limit, tmp;
32  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
33  idx_t *moved, *swaps, *perm;
34  rpq_t *queues[2];
35  idx_t higain, mincut, mindiff, origdiff, initcut, newcut, mincutorder, avgvwgt;
36  idx_t tpwgts[2];
37 
38  WCOREPUSH;
39 
40  nvtxs = graph->nvtxs;
41  xadj = graph->xadj;
42  vwgt = graph->vwgt;
43  adjncy = graph->adjncy;
44  adjwgt = graph->adjwgt;
45  where = graph->where;
46  id = graph->id;
47  ed = graph->ed;
48  pwgts = graph->pwgts;
49  bndptr = graph->bndptr;
50  bndind = graph->bndind;
51 
52  moved = iwspacemalloc(ctrl, nvtxs);
53  swaps = iwspacemalloc(ctrl, nvtxs);
54  perm = iwspacemalloc(ctrl, nvtxs);
55 
56  tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];
57  tpwgts[1] = graph->tvwgt[0]-tpwgts[0];
58 
59  limit = gk_min(gk_max(0.01*nvtxs, 15), 100);
60  avgvwgt = gk_min((pwgts[0]+pwgts[1])/20, 2*(pwgts[0]+pwgts[1])/nvtxs);
61 
62  queues[0] = rpqCreate(nvtxs);
63  queues[1] = rpqCreate(nvtxs);
64 
66  Print2WayRefineStats(ctrl, graph, ntpwgts, 0, -2));
67 
68  origdiff = iabs(tpwgts[0]-pwgts[0]);
69  iset(nvtxs, -1, moved);
70  for (pass=0; pass<niter; pass++) { /* Do a number of passes */
71  rpqReset(queues[0]);
72  rpqReset(queues[1]);
73 
74  mincutorder = -1;
75  newcut = mincut = initcut = graph->mincut;
76  mindiff = iabs(tpwgts[0]-pwgts[0]);
77 
78  ASSERT(ComputeCut(graph, where) == graph->mincut);
79  ASSERT(CheckBnd(graph));
80 
81  /* Insert boundary nodes in the priority queues */
82  nbnd = graph->nbnd;
83  irandArrayPermute(nbnd, perm, nbnd, 1);
84  for (ii=0; ii<nbnd; ii++) {
85  i = perm[ii];
86  ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);
87  ASSERT(bndptr[bndind[i]] != -1);
88  rpqInsert(queues[where[bndind[i]]], bndind[i], ed[bndind[i]]-id[bndind[i]]);
89  }
90 
91  for (nswaps=0; nswaps<nvtxs; nswaps++) {
92  from = (tpwgts[0]-pwgts[0] < tpwgts[1]-pwgts[1] ? 0 : 1);
93  to = (from+1)%2;
94 
95  if ((higain = rpqGetTop(queues[from])) == -1)
96  break;
97  ASSERT(bndptr[higain] != -1);
98 
99  newcut -= (ed[higain]-id[higain]);
100  INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
101 
102  if ((newcut < mincut && iabs(tpwgts[0]-pwgts[0]) <= origdiff+avgvwgt) ||
103  (newcut == mincut && iabs(tpwgts[0]-pwgts[0]) < mindiff)) {
104  mincut = newcut;
105  mindiff = iabs(tpwgts[0]-pwgts[0]);
106  mincutorder = nswaps;
107  }
108  else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
109  newcut += (ed[higain]-id[higain]);
110  INC_DEC(pwgts[from], pwgts[to], vwgt[higain]);
111  break;
112  }
113 
114  where[higain] = to;
115  moved[higain] = nswaps;
116  swaps[nswaps] = higain;
117 
119  printf("Moved %6"PRIDX" from %"PRIDX". [%3"PRIDX" %3"PRIDX"] %5"PRIDX" [%4"PRIDX" %4"PRIDX"]\n", higain, from, ed[higain]-id[higain], vwgt[higain], newcut, pwgts[0], pwgts[1]));
120 
121  /**************************************************************
122  * Update the id[i]/ed[i] values of the affected nodes
123  ***************************************************************/
124  SWAP(id[higain], ed[higain], tmp);
125  if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])
126  BNDDelete(nbnd, bndind, bndptr, higain);
127 
128  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
129  k = adjncy[j];
130 
131  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
132  INC_DEC(id[k], ed[k], kwgt);
133 
134  /* Update its boundary information and queue position */
135  if (bndptr[k] != -1) { /* If k was a boundary vertex */
136  if (ed[k] == 0) { /* Not a boundary vertex any more */
137  BNDDelete(nbnd, bndind, bndptr, k);
138  if (moved[k] == -1) /* Remove it if in the queues */
139  rpqDelete(queues[where[k]], k);
140  }
141  else { /* If it has not been moved, update its position in the queue */
142  if (moved[k] == -1)
143  rpqUpdate(queues[where[k]], k, ed[k]-id[k]);
144  }
145  }
146  else {
147  if (ed[k] > 0) { /* It will now become a boundary vertex */
148  BNDInsert(nbnd, bndind, bndptr, k);
149  if (moved[k] == -1)
150  rpqInsert(queues[where[k]], k, ed[k]-id[k]);
151  }
152  }
153  }
154 
155  }
156 
157 
158  /****************************************************************
159  * Roll back computations
160  *****************************************************************/
161  for (i=0; i<nswaps; i++)
162  moved[swaps[i]] = -1; /* reset moved array */
163  for (nswaps--; nswaps>mincutorder; nswaps--) {
164  higain = swaps[nswaps];
165 
166  to = where[higain] = (where[higain]+1)%2;
167  SWAP(id[higain], ed[higain], tmp);
168  if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
169  BNDDelete(nbnd, bndind, bndptr, higain);
170  else if (ed[higain] > 0 && bndptr[higain] == -1)
171  BNDInsert(nbnd, bndind, bndptr, higain);
172 
173  INC_DEC(pwgts[to], pwgts[(to+1)%2], vwgt[higain]);
174  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
175  k = adjncy[j];
176 
177  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
178  INC_DEC(id[k], ed[k], kwgt);
179 
180  if (bndptr[k] != -1 && ed[k] == 0)
181  BNDDelete(nbnd, bndind, bndptr, k);
182  if (bndptr[k] == -1 && ed[k] > 0)
183  BNDInsert(nbnd, bndind, bndptr, k);
184  }
185  }
186 
187  graph->mincut = mincut;
188  graph->nbnd = nbnd;
189 
190  IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
191  Print2WayRefineStats(ctrl, graph, ntpwgts, 0, mincutorder));
192 
193  if (mincutorder <= 0 || mincut == initcut)
194  break;
195  }
196 
197  rpqDestroy(queues[0]);
198  rpqDestroy(queues[1]);
199 
200  WCOREPOP;
201 }
202 
203 
204 /*************************************************************************/
206 /*************************************************************************/
207 void FM_Mc2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
208 {
209  idx_t i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass,
210  me, limit, tmp, cnum;
211  idx_t *xadj, *adjncy, *vwgt, *adjwgt, *pwgts, *where, *id, *ed,
212  *bndptr, *bndind;
213  idx_t *moved, *swaps, *perm, *qnum;
214  idx_t higain, mincut, initcut, newcut, mincutorder;
215  real_t *invtvwgt, *ubfactors, *minbalv, *newbalv;
216  real_t origbal, minbal, newbal, rgain, ffactor;
217  rpq_t **queues;
218 
219  WCOREPUSH;
220 
221  nvtxs = graph->nvtxs;
222  ncon = graph->ncon;
223  xadj = graph->xadj;
224  vwgt = graph->vwgt;
225  adjncy = graph->adjncy;
226  adjwgt = graph->adjwgt;
227  invtvwgt = graph->invtvwgt;
228  where = graph->where;
229  id = graph->id;
230  ed = graph->ed;
231  pwgts = graph->pwgts;
232  bndptr = graph->bndptr;
233  bndind = graph->bndind;
234 
235  moved = iwspacemalloc(ctrl, nvtxs);
236  swaps = iwspacemalloc(ctrl, nvtxs);
237  perm = iwspacemalloc(ctrl, nvtxs);
238  qnum = iwspacemalloc(ctrl, nvtxs);
239  ubfactors = rwspacemalloc(ctrl, ncon);
240  newbalv = rwspacemalloc(ctrl, ncon);
241  minbalv = rwspacemalloc(ctrl, ncon);
242 
243  limit = gk_min(gk_max(0.01*nvtxs, 25), 150);
244 
245 
246  /* Determine a fudge factor to allow the refinement routines to get out
247  of tight balancing constraints. */
248  ffactor = .5/gk_max(20, nvtxs);
249 
250  /* Initialize the queues */
251  queues = (rpq_t **)wspacemalloc(ctrl, 2*ncon*sizeof(rpq_t *));
252  for (i=0; i<2*ncon; i++)
253  queues[i] = rpqCreate(nvtxs);
254  for (i=0; i<nvtxs; i++)
255  qnum[i] = iargmax_nrm(ncon, vwgt+i*ncon, invtvwgt);
256 
257  /* Determine the unbalance tolerance for each constraint. The tolerance is
258  equal to the maximum of the original load imbalance and the user-supplied
259  allowed tolerance. The rationale behind this approach is to allow the
260  refinement routine to improve the cut, without having to worry about fixing
261  load imbalance problems. The load imbalance is addressed by the balancing
262  routines. */
263  origbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ctrl->ubfactors, ubfactors);
264  for (i=0; i<ncon; i++)
265  ubfactors[i] = (ubfactors[i] > 0 ? ctrl->ubfactors[i]+ubfactors[i] : ctrl->ubfactors[i]);
266 
267 
268  IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
269  Print2WayRefineStats(ctrl, graph, ntpwgts, origbal, -2));
270 
271  iset(nvtxs, -1, moved);
272  for (pass=0; pass<niter; pass++) { /* Do a number of passes */
273  for (i=0; i<2*ncon; i++)
274  rpqReset(queues[i]);
275 
276  mincutorder = -1;
277  newcut = mincut = initcut = graph->mincut;
278 
279  minbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ubfactors, minbalv);
280 
281  ASSERT(ComputeCut(graph, where) == graph->mincut);
282  ASSERT(CheckBnd(graph));
283 
284  /* Insert boundary nodes in the priority queues */
285  nbnd = graph->nbnd;
286  irandArrayPermute(nbnd, perm, nbnd/5, 1);
287  for (ii=0; ii<nbnd; ii++) {
288  i = bndind[perm[ii]];
289  ASSERT(ed[i] > 0 || id[i] == 0);
290  ASSERT(bndptr[i] != -1);
291  //rgain = 1.0*(ed[i]-id[i])/sqrt(vwgt[i*ncon+qnum[i]]+1);
292  //rgain = (ed[i]-id[i] > 0 ? 1.0*(ed[i]-id[i])/sqrt(vwgt[i*ncon+qnum[i]]+1) : ed[i]-id[i]);
293  rgain = ed[i]-id[i];
294  rpqInsert(queues[2*qnum[i]+where[i]], i, rgain);
295  }
296 
297  for (nswaps=0; nswaps<nvtxs; nswaps++) {
298  SelectQueue(graph, ctrl->pijbm, ubfactors, queues, &from, &cnum);
299 
300  to = (from+1)%2;
301 
302  if (from == -1 || (higain = rpqGetTop(queues[2*cnum+from])) == -1)
303  break;
304  ASSERT(bndptr[higain] != -1);
305 
306  newcut -= (ed[higain]-id[higain]);
307 
308  iaxpy(ncon, 1, vwgt+higain*ncon, 1, pwgts+to*ncon, 1);
309  iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
310  newbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ubfactors, newbalv);
311 
312  if ((newcut < mincut && newbal <= ffactor) ||
313  (newcut == mincut && (newbal < minbal ||
314  (newbal == minbal && BetterBalance2Way(ncon, minbalv, newbalv))))) {
315  mincut = newcut;
316  minbal = newbal;
317  mincutorder = nswaps;
318  rcopy(ncon, newbalv, minbalv);
319  }
320  else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
321  newcut += (ed[higain]-id[higain]);
322  iaxpy(ncon, 1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
323  iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+to*ncon, 1);
324  break;
325  }
326 
327  where[higain] = to;
328  moved[higain] = nswaps;
329  swaps[nswaps] = higain;
330 
331  if (ctrl->dbglvl&METIS_DBG_MOVEINFO) {
332  printf("Moved%6"PRIDX" from %"PRIDX"(%"PRIDX") Gain:%5"PRIDX", "
333  "Cut:%5"PRIDX", NPwgts:", higain, from, cnum, ed[higain]-id[higain], newcut);
334  for (l=0; l<ncon; l++)
335  printf("(%.3"PRREAL" %.3"PRREAL")", pwgts[l]*invtvwgt[l], pwgts[ncon+l]*invtvwgt[l]);
336  printf(" %+.3"PRREAL" LB: %.3"PRREAL"(%+.3"PRREAL")\n",
337  minbal, ComputeLoadImbalance(graph, 2, ctrl->pijbm), newbal);
338  }
339 
340 
341  /**************************************************************
342  * Update the id[i]/ed[i] values of the affected nodes
343  ***************************************************************/
344  SWAP(id[higain], ed[higain], tmp);
345  if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])
346  BNDDelete(nbnd, bndind, bndptr, higain);
347 
348  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
349  k = adjncy[j];
350 
351  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
352  INC_DEC(id[k], ed[k], kwgt);
353 
354  /* Update its boundary information and queue position */
355  if (bndptr[k] != -1) { /* If k was a boundary vertex */
356  if (ed[k] == 0) { /* Not a boundary vertex any more */
357  BNDDelete(nbnd, bndind, bndptr, k);
358  if (moved[k] == -1) /* Remove it if in the queues */
359  rpqDelete(queues[2*qnum[k]+where[k]], k);
360  }
361  else { /* If it has not been moved, update its position in the queue */
362  if (moved[k] == -1) {
363  //rgain = 1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1);
364  //rgain = (ed[k]-id[k] > 0 ?
365  // 1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1) : ed[k]-id[k]);
366  rgain = ed[k]-id[k];
367  rpqUpdate(queues[2*qnum[k]+where[k]], k, rgain);
368  }
369  }
370  }
371  else {
372  if (ed[k] > 0) { /* It will now become a boundary vertex */
373  BNDInsert(nbnd, bndind, bndptr, k);
374  if (moved[k] == -1) {
375  //rgain = 1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1);
376  //rgain = (ed[k]-id[k] > 0 ?
377  // 1.0*(ed[k]-id[k])/sqrt(vwgt[k*ncon+qnum[k]]+1) : ed[k]-id[k]);
378  rgain = ed[k]-id[k];
379  rpqInsert(queues[2*qnum[k]+where[k]], k, rgain);
380  }
381  }
382  }
383  }
384 
385  }
386 
387 
388  /****************************************************************
389  * Roll back computations
390  *****************************************************************/
391  for (i=0; i<nswaps; i++)
392  moved[swaps[i]] = -1; /* reset moved array */
393  for (nswaps--; nswaps>mincutorder; nswaps--) {
394  higain = swaps[nswaps];
395 
396  to = where[higain] = (where[higain]+1)%2;
397  SWAP(id[higain], ed[higain], tmp);
398  if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
399  BNDDelete(nbnd, bndind, bndptr, higain);
400  else if (ed[higain] > 0 && bndptr[higain] == -1)
401  BNDInsert(nbnd, bndind, bndptr, higain);
402 
403  iaxpy(ncon, 1, vwgt+higain*ncon, 1, pwgts+to*ncon, 1);
404  iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+((to+1)%2)*ncon, 1);
405  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
406  k = adjncy[j];
407 
408  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
409  INC_DEC(id[k], ed[k], kwgt);
410 
411  if (bndptr[k] != -1 && ed[k] == 0)
412  BNDDelete(nbnd, bndind, bndptr, k);
413  if (bndptr[k] == -1 && ed[k] > 0)
414  BNDInsert(nbnd, bndind, bndptr, k);
415  }
416  }
417 
418  graph->mincut = mincut;
419  graph->nbnd = nbnd;
420 
421  IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
422  Print2WayRefineStats(ctrl, graph, ntpwgts, minbal, mincutorder));
423 
424  if (mincutorder <= 0 || mincut == initcut)
425  break;
426  }
427 
428  for (i=0; i<2*ncon; i++)
429  rpqDestroy(queues[i]);
430 
431  WCOREPOP;
432 }
433 
434 
435 /*************************************************************************/
438 /*************************************************************************/
439 void SelectQueue(graph_t *graph, real_t *pijbm, real_t *ubfactors,
440  rpq_t **queues, idx_t *from, idx_t *cnum)
441 {
442  idx_t ncon, i, part;
443  real_t max, tmp;
444 
445  ncon = graph->ncon;
446 
447  *from = -1;
448  *cnum = -1;
449 
450  /* First determine the side and the queue, irrespective of the presence of nodes.
451  The side & queue is determined based on the most violated balancing constraint. */
452  for (max=0.0, part=0; part<2; part++) {
453  for (i=0; i<ncon; i++) {
454  tmp = graph->pwgts[part*ncon+i]*pijbm[part*ncon+i] - ubfactors[i];
455  /* the '=' in the test bellow is to ensure that under tight constraints
456  the partition that is at the max is selected */
457  if (tmp >= max) {
458  max = tmp;
459  *from = part;
460  *cnum = i;
461  }
462  }
463  }
464 
465 
466  if (*from != -1) {
467  /* in case the desired queue is empty, select a queue from the same side */
468  if (rpqLength(queues[2*(*cnum)+(*from)]) == 0) {
469  for (i=0; i<ncon; i++) {
470  if (rpqLength(queues[2*i+(*from)]) > 0) {
471  max = graph->pwgts[(*from)*ncon+i]*pijbm[(*from)*ncon+i] - ubfactors[i];
472  *cnum = i;
473  break;
474  }
475  }
476 
477  for (i++; i<ncon; i++) {
478  tmp = graph->pwgts[(*from)*ncon+i]*pijbm[(*from)*ncon+i] - ubfactors[i];
479  if (tmp > max && rpqLength(queues[2*i+(*from)]) > 0) {
480  max = tmp;
481  *cnum = i;
482  }
483  }
484  }
485 
486  /*
487  printf("Selected1 %"PRIDX"(%"PRIDX") -> %"PRIDX" [%5"PRREAL"]\n",
488  *from, *cnum, rpqLength(queues[2*(*cnum)+(*from)]), max);
489  */
490  }
491  else {
492  /* the partitioning does not violate balancing constraints, in which case select
493  a queue based on cut criteria */
494  for (part=0; part<2; part++) {
495  for (i=0; i<ncon; i++) {
496  if (rpqLength(queues[2*i+part]) > 0 &&
497  (*from == -1 || rpqSeeTopKey(queues[2*i+part]) > max)) {
498  max = rpqSeeTopKey(queues[2*i+part]);
499  *from = part;
500  *cnum = i;
501  }
502  }
503  }
504  /*
505  printf("Selected2 %"PRIDX"(%"PRIDX") -> %"PRIDX"\n",
506  *from, *cnum, rpqLength(queues[2*(*cnum)+(*from)]), max);
507  */
508  }
509 }
510 
511 
512 /*************************************************************************/
514 /*************************************************************************/
516  real_t deltabal, idx_t mincutorder)
517 {
518  int i;
519 
520  if (mincutorder == -2) {
521  printf("Parts: ");
522  printf("Nv-Nb[%5"PRIDX" %5"PRIDX"] ICut: %6"PRIDX,
523  graph->nvtxs, graph->nbnd, graph->mincut);
524  printf(" [");
525  for (i=0; i<graph->ncon; i++)
526  printf("(%.3"PRREAL" %.3"PRREAL" T:%.3"PRREAL" %.3"PRREAL")",
527  graph->pwgts[i]*graph->invtvwgt[i],
528  graph->pwgts[graph->ncon+i]*graph->invtvwgt[i],
529  ntpwgts[i], ntpwgts[graph->ncon+i]);
530  printf("] LB: %.3"PRREAL"(%+.3"PRREAL")\n",
531  ComputeLoadImbalance(graph, 2, ctrl->pijbm), deltabal);
532  }
533  else {
534  printf("\tMincut: %6"PRIDX" at %5"PRIDX" NBND %6"PRIDX" NPwgts: [",
535  graph->mincut, mincutorder, graph->nbnd);
536  for (i=0; i<graph->ncon; i++)
537  printf("(%.3"PRREAL" %.3"PRREAL")",
538  graph->pwgts[i]*graph->invtvwgt[i], graph->pwgts[graph->ncon+i]*graph->invtvwgt[i]);
539  printf("] LB: %.3"PRREAL"(%+.3"PRREAL")\n",
540  ComputeLoadImbalance(graph, 2, ctrl->pijbm), deltabal);
541  }
542 }
543 
#define iabs
idx_t idx_t idx_t idx_t * vwgt
idx_t * bndind
#define max(a, b)
Definition: datatypes.h:20
#define iwspacemalloc
Definition: rename.h:256
void SelectQueue(graph_t *graph, real_t *pijbm, real_t *ubfactors, rpq_t **queues, idx_t *from, idx_t *cnum)
Definition: fm.c:439
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t real_t idx_t idx_t idx_t * part
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define irandArrayPermute
Definition: gklib_rename.h:62
idx_t * xadj
#define rcopy
Definition: gklib_rename.h:80
idx_t * pwgts
idx_t * adjwgt
void FM_Mc2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
Definition: fm.c:207
#define rpqSeeTopKey
Definition: gklib_rename.h:108
idx_t * bndptr
idx_t idx_t * xadj
#define rwspacemalloc
Definition: rename.h:257
idx_t * where
#define WCOREPUSH
idx_t nvtxs
idx_t * id
mdbglvl_et dbglvl
NonlinearFactorGraph graph
static const Similarity3 id
idx_t * ed
#define ComputeLoadImbalance
Definition: rename.h:143
#define PRIDX
#define ASSERT(expression)
Definition: ccolamd.c:872
#define rpqLength
Definition: gklib_rename.h:105
static const Line3 l(Rot3(), 1, 1)
#define BNDInsert(nbnd, bndind, bndptr, vtx)
#define BetterBalance2Way
Definition: rename.h:141
#define rpqCreate
Definition: gklib_rename.h:98
#define gk_max(a, b)
Definition: gk_macros.h:16
int32_t idx_t
#define iargmax_nrm
Definition: rename.h:243
#define rpqInsert
Definition: gklib_rename.h:104
#define gk_min(a, b)
Definition: gk_macros.h:17
real_t * pijbm
idx_t idx_t idx_t idx_t idx_t * perm
idx_t ncon
#define CheckBnd
Definition: rename.h:65
#define iaxpy
Definition: gklib_rename.h:27
float real_t
idx_t * ncon
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
idx_t mincut
#define rpqGetTop
Definition: gklib_rename.h:102
void FM_2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
Definition: fm.c:29
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
#define INC_DEC(a, b, val)
Definition: gk_macros.h:20
#define ComputeLoadImbalanceDiffVec
Definition: rename.h:145
#define rpqDelete
Definition: gklib_rename.h:99
real_t * ubfactors
void FM_2WayRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
Definition: fm.c:17
#define iset
Definition: gklib_rename.h:67
idx_t idx_t idx_t idx_t * where
idx_t * adjncy
#define rpqUpdate
Definition: gklib_rename.h:110
idx_t * tvwgt
idx_t idx_t idx_t * adjncy
void Print2WayRefineStats(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, real_t deltabal, idx_t mincutorder)
Definition: fm.c:515
#define PRREAL
#define WCOREPOP
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
real_t * invtvwgt
#define ComputeCut
Definition: rename.h:62
#define SWAP
std::ptrdiff_t j
#define rpqDestroy
Definition: gklib_rename.h:100
#define rpqReset
Definition: gklib_rename.h:106
#define wspacemalloc
Definition: rename.h:253
idx_t * vwgt


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