sfm.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * sfm.c
5  *
6  * This file contains code that implementes an FM-based separator refinement
7  *
8  * Started 8/1/97
9  * George
10  *
11  * $Id: sfm.c 10874 2011-10-17 23:13:00Z karypis $
12  *
13  */
14 
15 #include "metislib.h"
16 
17 
18 /*************************************************************************/
20 /**************************************************************************/
22 {
23  idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind;
24  idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
25  idx_t *mptr, *mind, *moved, *swaps;
26  rpq_t *queues[2];
27  nrinfo_t *rinfo;
28  idx_t higain, oldgain, mincut, initcut, mincutorder;
29  idx_t pass, to, other, limit;
30  idx_t badmaxpwgt, mindiff, newdiff;
31  idx_t u[2], g[2];
32  real_t mult;
33 
34  WCOREPUSH;
35 
36  nvtxs = graph->nvtxs;
37  xadj = graph->xadj;
38  adjncy = graph->adjncy;
39  vwgt = graph->vwgt;
40 
41  bndind = graph->bndind;
42  bndptr = graph->bndptr;
43  where = graph->where;
44  pwgts = graph->pwgts;
45  rinfo = graph->nrinfo;
46 
47  queues[0] = rpqCreate(nvtxs);
48  queues[1] = rpqCreate(nvtxs);
49 
50  moved = iwspacemalloc(ctrl, nvtxs);
51  swaps = iwspacemalloc(ctrl, nvtxs);
52  mptr = iwspacemalloc(ctrl, nvtxs+1);
53  mind = iwspacemalloc(ctrl, 2*nvtxs);
54 
55  mult = 0.5*ctrl->ubfactors[0];
56  badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]+pwgts[2]));
57 
59  printf("Partitions-N2: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX"\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
60 
61  for (pass=0; pass<niter; pass++) {
62  iset(nvtxs, -1, moved);
63  rpqReset(queues[0]);
64  rpqReset(queues[1]);
65 
66  mincutorder = -1;
67  initcut = mincut = graph->mincut;
68  nbnd = graph->nbnd;
69 
70  /* use the swaps array in place of the traditional perm array to save memory */
71  irandArrayPermute(nbnd, swaps, nbnd, 1);
72  for (ii=0; ii<nbnd; ii++) {
73  i = bndind[swaps[ii]];
74  ASSERT(where[i] == 2);
75  rpqInsert(queues[0], i, vwgt[i]-rinfo[i].edegrees[1]);
76  rpqInsert(queues[1], i, vwgt[i]-rinfo[i].edegrees[0]);
77  }
78 
79  ASSERT(CheckNodeBnd(graph, nbnd));
81 
82  limit = (ctrl->compress ? gk_min(5*nbnd, 400) : gk_min(2*nbnd, 300));
83 
84  /******************************************************
85  * Get into the FM loop
86  *******************************************************/
87  mptr[0] = nmind = 0;
88  mindiff = iabs(pwgts[0]-pwgts[1]);
89  to = (pwgts[0] < pwgts[1] ? 0 : 1);
90  for (nswaps=0; nswaps<nvtxs; nswaps++) {
91  u[0] = rpqSeeTopVal(queues[0]);
92  u[1] = rpqSeeTopVal(queues[1]);
93  if (u[0] != -1 && u[1] != -1) {
94  g[0] = vwgt[u[0]]-rinfo[u[0]].edegrees[1];
95  g[1] = vwgt[u[1]]-rinfo[u[1]].edegrees[0];
96 
97  to = (g[0] > g[1] ? 0 : (g[0] < g[1] ? 1 : pass%2));
98 
99  if (pwgts[to]+vwgt[u[to]] > badmaxpwgt)
100  to = (to+1)%2;
101  }
102  else if (u[0] == -1 && u[1] == -1) {
103  break;
104  }
105  else if (u[0] != -1 && pwgts[0]+vwgt[u[0]] <= badmaxpwgt) {
106  to = 0;
107  }
108  else if (u[1] != -1 && pwgts[1]+vwgt[u[1]] <= badmaxpwgt) {
109  to = 1;
110  }
111  else
112  break;
113 
114  other = (to+1)%2;
115 
116  higain = rpqGetTop(queues[to]);
117  if (moved[higain] == -1) /* Delete if it was in the separator originally */
118  rpqDelete(queues[other], higain);
119 
120  ASSERT(bndptr[higain] != -1);
121 
122  /* The following check is to ensure we break out if there is a posibility
123  of over-running the mind array. */
124  if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1)
125  break;
126 
127  pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
128 
129  newdiff = iabs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
130  if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
131  mincut = pwgts[2];
132  mincutorder = nswaps;
133  mindiff = newdiff;
134  }
135  else {
136  if (nswaps - mincutorder > 2*limit ||
137  (nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {
138  pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);
139  break; /* No further improvement, break out */
140  }
141  }
142 
143  BNDDelete(nbnd, bndind, bndptr, higain);
144  pwgts[to] += vwgt[higain];
145  where[higain] = to;
146  moved[higain] = nswaps;
147  swaps[nswaps] = higain;
148 
149 
150  /**********************************************************
151  * Update the degrees of the affected nodes
152  ***********************************************************/
153  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
154  k = adjncy[j];
155  if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
156  oldgain = vwgt[k]-rinfo[k].edegrees[to];
157  rinfo[k].edegrees[to] += vwgt[higain];
158  if (moved[k] == -1 || moved[k] == -(2+other))
159  rpqUpdate(queues[other], k, oldgain-vwgt[higain]);
160  }
161  else if (where[k] == other) { /* This vertex is pulled into the separator */
162  ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));
163  BNDInsert(nbnd, bndind, bndptr, k);
164 
165  mind[nmind++] = k; /* Keep track for rollback */
166  where[k] = 2;
167  pwgts[other] -= vwgt[k];
168 
169  edegrees = rinfo[k].edegrees;
170  edegrees[0] = edegrees[1] = 0;
171  for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
172  kk = adjncy[jj];
173  if (where[kk] != 2)
174  edegrees[where[kk]] += vwgt[kk];
175  else {
176  oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
177  rinfo[kk].edegrees[other] -= vwgt[k];
178  if (moved[kk] == -1 || moved[kk] == -(2+to))
179  rpqUpdate(queues[to], kk, oldgain+vwgt[k]);
180  }
181  }
182 
183  /* Insert the new vertex into the priority queue. Only one side! */
184  if (moved[k] == -1) {
185  rpqInsert(queues[to], k, vwgt[k]-edegrees[other]);
186  moved[k] = -(2+to);
187  }
188  }
189  }
190  mptr[nswaps+1] = nmind;
191 
193  printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] [%4"PRIDX" %4"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]\n", higain, to, g[to], g[other], vwgt[u[to]], vwgt[u[other]], pwgts[0], pwgts[1], pwgts[2]));
194 
195  }
196 
197 
198  /****************************************************************
199  * Roll back computation
200  *****************************************************************/
201  for (nswaps--; nswaps>mincutorder; nswaps--) {
202  higain = swaps[nswaps];
203 
205 
206  to = where[higain];
207  other = (to+1)%2;
208  INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
209  where[higain] = 2;
210  BNDInsert(nbnd, bndind, bndptr, higain);
211 
212  edegrees = rinfo[higain].edegrees;
213  edegrees[0] = edegrees[1] = 0;
214  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
215  k = adjncy[j];
216  if (where[k] == 2)
217  rinfo[k].edegrees[to] -= vwgt[higain];
218  else
219  edegrees[where[k]] += vwgt[k];
220  }
221 
222  /* Push nodes out of the separator */
223  for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
224  k = mind[j];
225  ASSERT(where[k] == 2);
226  where[k] = other;
227  INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
228  BNDDelete(nbnd, bndind, bndptr, k);
229  for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
230  kk = adjncy[jj];
231  if (where[kk] == 2)
232  rinfo[kk].edegrees[other] += vwgt[k];
233  }
234  }
235  }
236 
237  ASSERT(mincut == pwgts[2]);
238 
240  printf("\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
241 
242  graph->mincut = mincut;
243  graph->nbnd = nbnd;
244 
245  if (mincutorder == -1 || mincut >= initcut)
246  break;
247  }
248 
249  rpqDestroy(queues[0]);
250  rpqDestroy(queues[1]);
251 
252  WCOREPOP;
253 }
254 
255 
256 /*************************************************************************/
262 /**************************************************************************/
264 {
265  idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, nmind, iend;
266  idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
267  idx_t *mptr, *mind, *swaps;
268  rpq_t *queue;
269  nrinfo_t *rinfo;
270  idx_t higain, mincut, initcut, mincutorder;
271  idx_t pass, to, other, limit;
272  idx_t badmaxpwgt, mindiff, newdiff;
273  real_t mult;
274 
275  WCOREPUSH;
276 
277  nvtxs = graph->nvtxs;
278  xadj = graph->xadj;
279  adjncy = graph->adjncy;
280  vwgt = graph->vwgt;
281 
282  bndind = graph->bndind;
283  bndptr = graph->bndptr;
284  where = graph->where;
285  pwgts = graph->pwgts;
286  rinfo = graph->nrinfo;
287 
288  queue = rpqCreate(nvtxs);
289 
290  swaps = iwspacemalloc(ctrl, nvtxs);
291  mptr = iwspacemalloc(ctrl, nvtxs+1);
292  mind = iwspacemalloc(ctrl, 2*nvtxs);
293 
294  mult = 0.5*ctrl->ubfactors[0];
295  badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]+pwgts[2]));
296 
298  printf("Partitions-N1: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX"\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
299 
300  to = (pwgts[0] < pwgts[1] ? 1 : 0);
301  for (pass=0; pass<2*niter; pass++) { /* the 2*niter is for the two sides */
302  other = to;
303  to = (to+1)%2;
304 
305  rpqReset(queue);
306 
307  mincutorder = -1;
308  initcut = mincut = graph->mincut;
309  nbnd = graph->nbnd;
310 
311  /* use the swaps array in place of the traditional perm array to save memory */
312  irandArrayPermute(nbnd, swaps, nbnd, 1);
313  for (ii=0; ii<nbnd; ii++) {
314  i = bndind[swaps[ii]];
315  ASSERT(where[i] == 2);
316  rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[other]);
317  }
318 
319  ASSERT(CheckNodeBnd(graph, nbnd));
321 
322  limit = (ctrl->compress ? gk_min(5*nbnd, 500) : gk_min(3*nbnd, 300));
323 
324  /******************************************************
325  * Get into the FM loop
326  *******************************************************/
328  mptr[0] = nmind = 0;
329  mindiff = iabs(pwgts[0]-pwgts[1]);
330  for (nswaps=0; nswaps<nvtxs; nswaps++) {
331  if ((higain = rpqGetTop(queue)) == -1)
332  break;
333 
334  ASSERT(bndptr[higain] != -1);
335 
336  /* The following check is to ensure we break out if there is a posibility
337  of over-running the mind array. */
338  if (nmind + xadj[higain+1]-xadj[higain] >= 2*nvtxs-1)
339  break;
340 
341  if (pwgts[to]+vwgt[higain] > badmaxpwgt)
342  break; /* No point going any further. Balance will be bad */
343 
344  pwgts[2] -= (vwgt[higain]-rinfo[higain].edegrees[other]);
345 
346  newdiff = iabs(pwgts[to]+vwgt[higain] - (pwgts[other]-rinfo[higain].edegrees[other]));
347  if (pwgts[2] < mincut || (pwgts[2] == mincut && newdiff < mindiff)) {
348  mincut = pwgts[2];
349  mincutorder = nswaps;
350  mindiff = newdiff;
351  }
352  else {
353  if (nswaps - mincutorder > 3*limit ||
354  (nswaps - mincutorder > limit && pwgts[2] > 1.10*mincut)) {
355  pwgts[2] += (vwgt[higain]-rinfo[higain].edegrees[other]);
356  break; /* No further improvement, break out */
357  }
358  }
359 
360  BNDDelete(nbnd, bndind, bndptr, higain);
361  pwgts[to] += vwgt[higain];
362  where[higain] = to;
363  swaps[nswaps] = higain;
364 
365 
366  /**********************************************************
367  * Update the degrees of the affected nodes
368  ***********************************************************/
370  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
371  k = adjncy[j];
372 
373  if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
374  rinfo[k].edegrees[to] += vwgt[higain];
375  }
376  else if (where[k] == other) { /* This vertex is pulled into the separator */
377  ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));
378  BNDInsert(nbnd, bndind, bndptr, k);
379 
380  mind[nmind++] = k; /* Keep track for rollback */
381  where[k] = 2;
382  pwgts[other] -= vwgt[k];
383 
384  edegrees = rinfo[k].edegrees;
385  edegrees[0] = edegrees[1] = 0;
386  for (jj=xadj[k], iend=xadj[k+1]; jj<iend; jj++) {
387  kk = adjncy[jj];
388  if (where[kk] != 2)
389  edegrees[where[kk]] += vwgt[kk];
390  else {
391  rinfo[kk].edegrees[other] -= vwgt[k];
392 
393  /* Since the moves are one-sided this vertex has not been moved yet */
394  rpqUpdate(queue, kk, vwgt[kk]-rinfo[kk].edegrees[other]);
395  }
396  }
397 
398  /* Insert the new vertex into the priority queue. Safe due to one-sided moves */
399  rpqInsert(queue, k, vwgt[k]-edegrees[other]);
400  }
401  }
402  mptr[nswaps+1] = nmind;
404 
405 
407  printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %5"PRIDX" [%5"PRIDX"] \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"] [%3"PRIDX" %2"PRIDX"]\n",
408  higain, to, (vwgt[higain]-rinfo[higain].edegrees[other]), vwgt[higain],
409  pwgts[0], pwgts[1], pwgts[2], nswaps, limit));
410  }
412 
413 
414  /****************************************************************
415  * Roll back computation
416  *****************************************************************/
418  for (nswaps--; nswaps>mincutorder; nswaps--) {
419  higain = swaps[nswaps];
420 
422  ASSERT(where[higain] == to);
423 
424  INC_DEC(pwgts[2], pwgts[to], vwgt[higain]);
425  where[higain] = 2;
426  BNDInsert(nbnd, bndind, bndptr, higain);
427 
428  edegrees = rinfo[higain].edegrees;
429  edegrees[0] = edegrees[1] = 0;
430  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
431  k = adjncy[j];
432  if (where[k] == 2)
433  rinfo[k].edegrees[to] -= vwgt[higain];
434  else
435  edegrees[where[k]] += vwgt[k];
436  }
437 
438  /* Push nodes out of the separator */
439  for (j=mptr[nswaps]; j<mptr[nswaps+1]; j++) {
440  k = mind[j];
441  ASSERT(where[k] == 2);
442  where[k] = other;
443  INC_DEC(pwgts[other], pwgts[2], vwgt[k]);
444  BNDDelete(nbnd, bndind, bndptr, k);
445  for (jj=xadj[k], iend=xadj[k+1]; jj<iend; jj++) {
446  kk = adjncy[jj];
447  if (where[kk] == 2)
448  rinfo[kk].edegrees[other] += vwgt[k];
449  }
450  }
451  }
453 
454  ASSERT(mincut == pwgts[2]);
455 
457  printf("\tMinimum sep: %6"PRIDX" at %5"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, mincutorder, pwgts[0], pwgts[1], nbnd));
458 
459  graph->mincut = mincut;
460  graph->nbnd = nbnd;
461 
462  if (pass%2 == 1 && (mincutorder == -1 || mincut >= initcut))
463  break;
464  }
465 
466  rpqDestroy(queue);
467 
468  WCOREPOP;
469 }
470 
471 
472 /*************************************************************************/
475 /*************************************************************************/
477 {
478  idx_t i, ii, j, k, jj, kk, nvtxs, nbnd, nswaps, gain;
479  idx_t badmaxpwgt, higain, oldgain, pass, to, other;
480  idx_t *xadj, *vwgt, *adjncy, *where, *pwgts, *edegrees, *bndind, *bndptr;
481  idx_t *perm, *moved;
482  rpq_t *queue;
483  nrinfo_t *rinfo;
484  real_t mult;
485 
486  nvtxs = graph->nvtxs;
487  xadj = graph->xadj;
488  adjncy = graph->adjncy;
489  vwgt = graph->vwgt;
490 
491  bndind = graph->bndind;
492  bndptr = graph->bndptr;
493  where = graph->where;
494  pwgts = graph->pwgts;
495  rinfo = graph->nrinfo;
496 
497  mult = 0.5*ctrl->ubfactors[0];
498 
499  badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]));
500  if (gk_max(pwgts[0], pwgts[1]) < badmaxpwgt)
501  return;
502  if (iabs(pwgts[0]-pwgts[1]) < 3*graph->tvwgt[0]/nvtxs)
503  return;
504 
505  WCOREPUSH;
506 
507  to = (pwgts[0] < pwgts[1] ? 0 : 1);
508  other = (to+1)%2;
509 
510  queue = rpqCreate(nvtxs);
511 
512  perm = iwspacemalloc(ctrl, nvtxs);
513  moved = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
514 
516  printf("Partitions: [%6"PRIDX" %6"PRIDX"] Nv-Nb[%6"PRIDX" %6"PRIDX"]. ISep: %6"PRIDX" [B]\n", pwgts[0], pwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
517 
518  nbnd = graph->nbnd;
519  irandArrayPermute(nbnd, perm, nbnd, 1);
520  for (ii=0; ii<nbnd; ii++) {
521  i = bndind[perm[ii]];
522  ASSERT(where[i] == 2);
523  rpqInsert(queue, i, vwgt[i]-rinfo[i].edegrees[other]);
524  }
525 
526  ASSERT(CheckNodeBnd(graph, nbnd));
528 
529  /******************************************************
530  * Get into the FM loop
531  *******************************************************/
532  for (nswaps=0; nswaps<nvtxs; nswaps++) {
533  if ((higain = rpqGetTop(queue)) == -1)
534  break;
535 
536  moved[higain] = 1;
537 
538  gain = vwgt[higain]-rinfo[higain].edegrees[other];
539  badmaxpwgt = (idx_t)(mult*(pwgts[0]+pwgts[1]));
540 
541  /* break if other is now underwight */
542  if (pwgts[to] > pwgts[other])
543  break;
544 
545  /* break if balance is achieved and no +ve or zero gain */
546  if (gain < 0 && pwgts[other] < badmaxpwgt)
547  break;
548 
549  /* skip this vertex if it will violate balance on the other side */
550  if (pwgts[to]+vwgt[higain] > badmaxpwgt)
551  continue;
552 
553  ASSERT(bndptr[higain] != -1);
554 
555  pwgts[2] -= gain;
556 
557  BNDDelete(nbnd, bndind, bndptr, higain);
558  pwgts[to] += vwgt[higain];
559  where[higain] = to;
560 
562  printf("Moved %6"PRIDX" to %3"PRIDX", Gain: %3"PRIDX", \t[%5"PRIDX" %5"PRIDX" %5"PRIDX"]\n", higain, to, vwgt[higain]-rinfo[higain].edegrees[other], pwgts[0], pwgts[1], pwgts[2]));
563 
564 
565  /**********************************************************
566  * Update the degrees of the affected nodes
567  ***********************************************************/
568  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
569  k = adjncy[j];
570  if (where[k] == 2) { /* For the in-separator vertices modify their edegree[to] */
571  rinfo[k].edegrees[to] += vwgt[higain];
572  }
573  else if (where[k] == other) { /* This vertex is pulled into the separator */
574  ASSERTP(bndptr[k] == -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", k, bndptr[k], where[k]));
575  BNDInsert(nbnd, bndind, bndptr, k);
576 
577  where[k] = 2;
578  pwgts[other] -= vwgt[k];
579 
580  edegrees = rinfo[k].edegrees;
581  edegrees[0] = edegrees[1] = 0;
582  for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
583  kk = adjncy[jj];
584  if (where[kk] != 2)
585  edegrees[where[kk]] += vwgt[kk];
586  else {
587  ASSERT(bndptr[kk] != -1);
588  oldgain = vwgt[kk]-rinfo[kk].edegrees[other];
589  rinfo[kk].edegrees[other] -= vwgt[k];
590 
591  if (moved[kk] == -1)
592  rpqUpdate(queue, kk, oldgain+vwgt[k]);
593  }
594  }
595 
596  /* Insert the new vertex into the priority queue */
597  rpqInsert(queue, k, vwgt[k]-edegrees[other]);
598  }
599  }
600  }
601 
603  printf("\tBalanced sep: %6"PRIDX" at %4"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", pwgts[2], nswaps, pwgts[0], pwgts[1], nbnd));
604 
605  graph->mincut = pwgts[2];
606  graph->nbnd = nbnd;
607 
608  rpqDestroy(queue);
609 
610  WCOREPOP;
611 }
612 
#define iabs
idx_t idx_t idx_t idx_t * vwgt
idx_t * bndind
#define iwspacemalloc
Definition: rename.h:256
#define gk_startcputimer(tmr)
Definition: gk_macros.h:33
#define BNDDelete(nbnd, bndind, bndptr, vtx)
#define irandArrayPermute
Definition: gklib_rename.h:62
idx_t * xadj
#define CheckNodeBnd
Definition: rename.h:67
#define gk_stopcputimer(tmr)
Definition: gk_macros.h:34
idx_t * pwgts
idx_t * bndptr
#define ASSERTP(expr, msg)
Definition: gk_macros.h:131
idx_t idx_t * xadj
idx_t * where
idx_t compress
double Aux3Tmr
#define WCOREPUSH
idx_t nvtxs
mdbglvl_et dbglvl
#define CheckNodePartitionParams
Definition: rename.h:69
NonlinearFactorGraph graph
double Aux2Tmr
nrinfo_t * nrinfo
void g(const string &key, int i)
Definition: testBTree.cpp:41
#define PRIDX
#define ASSERT(expression)
Definition: ccolamd.c:872
void FM_2WayNodeBalance(ctrl_t *ctrl, graph_t *graph)
Definition: sfm.c:476
#define rpqSeeTopVal
Definition: gklib_rename.h:109
#define BNDInsert(nbnd, bndind, bndptr, vtx)
idx_t edegrees[2]
#define rpqCreate
Definition: gklib_rename.h:98
#define gk_max(a, b)
Definition: gk_macros.h:16
int32_t idx_t
#define rpqInsert
Definition: gklib_rename.h:104
#define gk_min(a, b)
Definition: gk_macros.h:17
idx_t idx_t idx_t idx_t idx_t * perm
float real_t
idx_t mincut
#define rpqGetTop
Definition: gklib_rename.h:102
void FM_2WayNodeRefine1Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter)
Definition: sfm.c:263
double Aux1Tmr
#define INC_DEC(a, b, val)
Definition: gk_macros.h:20
#define rpqDelete
Definition: gklib_rename.h:99
real_t * ubfactors
#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 FM_2WayNodeRefine2Sided(ctrl_t *ctrl, graph_t *graph, idx_t niter)
Definition: sfm.c:21
#define WCOREPOP
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
std::ptrdiff_t j
#define rpqDestroy
Definition: gklib_rename.h:100
#define rpqReset
Definition: gklib_rename.h:106
idx_t * vwgt


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:35:42