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);
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);
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 
perm
idx_t idx_t idx_t idx_t idx_t * perm
Definition: include/metis.h:223
adjwgt
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
Definition: include/metis.h:198
ctrl_t::pijbm
real_t * pijbm
Definition: libmetis/struct.h:170
ComputeLoadImbalance
#define ComputeLoadImbalance
Definition: rename.h:143
FM_2WayRefine
void FM_2WayRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
Definition: fm.c:17
ctrl_t::ubfactors
real_t * ubfactors
Definition: libmetis/struct.h:167
ctrl_t
Definition: libmetis/struct.h:139
wspacemalloc
#define wspacemalloc
Definition: rename.h:253
tpwgts
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
Definition: include/metis.h:199
adjncy
idx_t idx_t idx_t * adjncy
Definition: include/metis.h:198
gk_min
#define gk_min(a, b)
Definition: gk_macros.h:17
rpqLength
#define rpqLength
Definition: gklib_rename.h:105
METIS_DBG_REFINE
@ METIS_DBG_REFINE
Definition: include/metis.h:343
IFSET
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
PRREAL
#define PRREAL
Definition: include/metis.h:135
BNDDelete
#define BNDDelete(nbnd, bndind, bndptr, vtx)
Definition: metis/libmetis/macros.h:68
SelectQueue
void SelectQueue(graph_t *graph, real_t *pijbm, real_t *ubfactors, rpq_t **queues, idx_t *from, idx_t *cnum)
Definition: fm.c:439
BNDInsert
#define BNDInsert(nbnd, bndind, bndptr, vtx)
Definition: metis/libmetis/macros.h:65
INC_DEC
#define INC_DEC(a, b, val)
Definition: gk_macros.h:20
Print2WayRefineStats
void Print2WayRefineStats(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, real_t deltabal, idx_t mincutorder)
Definition: fm.c:515
rpqSeeTopKey
#define rpqSeeTopKey
Definition: gklib_rename.h:108
FM_Mc2WayCutRefine
void FM_Mc2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
Definition: fm.c:207
ncon
idx_t * ncon
Definition: include/metis.h:197
id
static const Similarity3 id
Definition: testSimilarity3.cpp:44
CheckBnd
#define CheckBnd
Definition: rename.h:65
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
iabs
#define iabs
Definition: include/metis.h:110
rpqUpdate
#define rpqUpdate
Definition: gklib_rename.h:110
ComputeCut
#define ComputeCut
Definition: rename.h:62
rpqCreate
#define rpqCreate
Definition: gklib_rename.h:98
iaxpy
#define iaxpy
Definition: gklib_rename.h:27
FM_2WayCutRefine
void FM_2WayCutRefine(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niter)
Definition: fm.c:29
l
static const Line3 l(Rot3(), 1, 1)
rpqInsert
#define rpqInsert
Definition: gklib_rename.h:104
BetterBalance2Way
#define BetterBalance2Way
Definition: rename.h:141
WCOREPUSH
#define WCOREPUSH
Definition: metis/libmetis/macros.h:38
ComputeLoadImbalanceDiffVec
#define ComputeLoadImbalanceDiffVec
Definition: rename.h:145
rpqGetTop
#define rpqGetTop
Definition: gklib_rename.h:102
vwgt
idx_t idx_t idx_t idx_t * vwgt
Definition: include/metis.h:198
part
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
Definition: include/metis.h:200
ASSERT
#define ASSERT(expression)
Definition: ccolamd.c:872
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
iset
#define iset
Definition: gklib_rename.h:67
rpqDelete
#define rpqDelete
Definition: gklib_rename.h:99
rpqReset
#define rpqReset
Definition: gklib_rename.h:106
PRIDX
#define PRIDX
Definition: include/metis.h:107
real_t
float real_t
Definition: include/metis.h:132
ctrl_t::dbglvl
mdbglvl_et dbglvl
Definition: libmetis/struct.h:142
metislib.h
rcopy
#define rcopy
Definition: gklib_rename.h:80
WCOREPOP
#define WCOREPOP
Definition: metis/libmetis/macros.h:39
iargmax_nrm
#define iargmax_nrm
Definition: rename.h:243
where
idx_t idx_t idx_t idx_t * where
Definition: include/metis.h:240
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
gk_max
#define gk_max(a, b)
Definition: gk_macros.h:16
max
#define max(a, b)
Definition: datatypes.h:20
iwspacemalloc
#define iwspacemalloc
Definition: rename.h:256
irandArrayPermute
#define irandArrayPermute
Definition: gklib_rename.h:62
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
rpqDestroy
#define rpqDestroy
Definition: gklib_rename.h:100
rwspacemalloc
#define rwspacemalloc
Definition: rename.h:257
SWAP
#define SWAP
Definition: metis/libmetis/macros.h:28
graph_t
Definition: libmetis/struct.h:82
idx_t
int32_t idx_t
Definition: include/metis.h:101
METIS_DBG_MOVEINFO
@ METIS_DBG_MOVEINFO
Definition: include/metis.h:345


gtsam
Author(s):
autogenerated on Sat Nov 16 2024 04:02:17