balance.c
Go to the documentation of this file.
1 
11 #include "metislib.h"
12 
13 /*************************************************************************
14 * This function is the entry poidx_t of the bisection balancing algorithms.
15 **************************************************************************/
16 void Balance2Way(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
17 {
18  if (ComputeLoadImbalanceDiff(graph, 2, ctrl->pijbm, ctrl->ubfactors) <= 0)
19  return;
20 
21  if (graph->ncon == 1) {
22  /* return right away if the balance is OK */
23  if (fabs(ntpwgts[0]*graph->tvwgt[0]-graph->pwgts[0]) < 3*graph->tvwgt[0]/graph->nvtxs)
24  return;
25 
26  if (graph->nbnd > 0)
27  Bnd2WayBalance(ctrl, graph, ntpwgts);
28  else
29  General2WayBalance(ctrl, graph, ntpwgts);
30  }
31  else {
32  McGeneral2WayBalance(ctrl, graph, ntpwgts);
33  }
34 }
35 
36 
37 /*************************************************************************
38 * This function balances two partitions by moving boundary nodes
39 * from the domain that is overweight to the one that is underweight.
40 **************************************************************************/
41 void Bnd2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
42 {
43  idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
44  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
45  idx_t *moved, *perm;
46  rpq_t *queue;
47  idx_t higain, mincut, mindiff;
48  idx_t tpwgts[2];
49 
50  WCOREPUSH;
51 
52  nvtxs = graph->nvtxs;
53  xadj = graph->xadj;
54  vwgt = graph->vwgt;
55  adjncy = graph->adjncy;
56  adjwgt = graph->adjwgt;
57  where = graph->where;
58  id = graph->id;
59  ed = graph->ed;
60  pwgts = graph->pwgts;
61  bndptr = graph->bndptr;
62  bndind = graph->bndind;
63 
64  moved = iwspacemalloc(ctrl, nvtxs);
65  perm = iwspacemalloc(ctrl, nvtxs);
66 
67  /* Determine from which domain you will be moving data */
68  tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];
69  tpwgts[1] = graph->tvwgt[0] - tpwgts[0];
70  mindiff = iabs(tpwgts[0]-pwgts[0]);
71  from = (pwgts[0] < tpwgts[0] ? 1 : 0);
72  to = (from+1)%2;
73 
75  printf("Partitions: [%6"PRIDX" %6"PRIDX"] T[%6"PRIDX" %6"PRIDX"], Nv-Nb[%6"PRIDX" %6"PRIDX"]. ICut: %6"PRIDX" [B]\n",
76  pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd,
77  graph->mincut));
78 
79  queue = rpqCreate(nvtxs);
80 
81  iset(nvtxs, -1, moved);
82 
83  ASSERT(ComputeCut(graph, where) == graph->mincut);
84  ASSERT(CheckBnd(graph));
85 
86  /* Insert the boundary nodes of the proper partition whose size is OK in the priority queue */
87  nbnd = graph->nbnd;
88  irandArrayPermute(nbnd, perm, nbnd/5, 1);
89  for (ii=0; ii<nbnd; ii++) {
90  i = perm[ii];
91  ASSERT(ed[bndind[i]] > 0 || id[bndind[i]] == 0);
92  ASSERT(bndptr[bndind[i]] != -1);
93  if (where[bndind[i]] == from && vwgt[bndind[i]] <= mindiff)
94  rpqInsert(queue, bndind[i], ed[bndind[i]]-id[bndind[i]]);
95  }
96 
97  mincut = graph->mincut;
98  for (nswaps=0; nswaps<nvtxs; nswaps++) {
99  if ((higain = rpqGetTop(queue)) == -1)
100  break;
101  ASSERT(bndptr[higain] != -1);
102 
103  if (pwgts[to]+vwgt[higain] > tpwgts[to])
104  break;
105 
106  mincut -= (ed[higain]-id[higain]);
107  INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
108 
109  where[higain] = to;
110  moved[higain] = nswaps;
111 
113  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], mincut, pwgts[0], pwgts[1]));
114 
115  /**************************************************************
116  * Update the id[i]/ed[i] values of the affected nodes
117  ***************************************************************/
118  SWAP(id[higain], ed[higain], tmp);
119  if (ed[higain] == 0 && xadj[higain] < xadj[higain+1])
120  BNDDelete(nbnd, bndind, bndptr, higain);
121 
122  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
123  k = adjncy[j];
124  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
125  INC_DEC(id[k], ed[k], kwgt);
126 
127  /* Update its boundary information and queue position */
128  if (bndptr[k] != -1) { /* If k was a boundary vertex */
129  if (ed[k] == 0) { /* Not a boundary vertex any more */
130  BNDDelete(nbnd, bndind, bndptr, k);
131  if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff) /* Remove it if in the queues */
132  rpqDelete(queue, k);
133  }
134  else { /* If it has not been moved, update its position in the queue */
135  if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
136  rpqUpdate(queue, k, ed[k]-id[k]);
137  }
138  }
139  else {
140  if (ed[k] > 0) { /* It will now become a boundary vertex */
141  BNDInsert(nbnd, bndind, bndptr, k);
142  if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
143  rpqInsert(queue, k, ed[k]-id[k]);
144  }
145  }
146  }
147  }
148 
149  IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
150  printf("\tMinimum cut: %6"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, pwgts[0], pwgts[1], nbnd));
151 
152  graph->mincut = mincut;
153  graph->nbnd = nbnd;
154 
155  rpqDestroy(queue);
156 
157  WCOREPOP;
158 }
159 
160 
161 /*************************************************************************
162 * This function balances two partitions by moving the highest gain
163 * (including negative gain) vertices to the other domain.
164 * It is used only when tha unbalance is due to non contigous
165 * subdomains. That is, the are no boundary vertices.
166 * It moves vertices from the domain that is overweight to the one that
167 * is underweight.
168 **************************************************************************/
170 {
171  idx_t i, ii, j, k, kwgt, nvtxs, nbnd, nswaps, from, to, pass, me, tmp;
172  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *id, *ed, *bndptr, *bndind, *pwgts;
173  idx_t *moved, *perm;
174  rpq_t *queue;
175  idx_t higain, mincut, mindiff;
176  idx_t tpwgts[2];
177 
178  WCOREPUSH;
179 
180  nvtxs = graph->nvtxs;
181  xadj = graph->xadj;
182  vwgt = graph->vwgt;
183  adjncy = graph->adjncy;
184  adjwgt = graph->adjwgt;
185  where = graph->where;
186  id = graph->id;
187  ed = graph->ed;
188  pwgts = graph->pwgts;
189  bndptr = graph->bndptr;
190  bndind = graph->bndind;
191 
192  moved = iwspacemalloc(ctrl, nvtxs);
193  perm = iwspacemalloc(ctrl, nvtxs);
194 
195  /* Determine from which domain you will be moving data */
196  tpwgts[0] = graph->tvwgt[0]*ntpwgts[0];
197  tpwgts[1] = graph->tvwgt[0] - tpwgts[0];
198  mindiff = iabs(tpwgts[0]-pwgts[0]);
199  from = (pwgts[0] < tpwgts[0] ? 1 : 0);
200  to = (from+1)%2;
201 
202  IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
203  printf("Partitions: [%6"PRIDX" %6"PRIDX"] T[%6"PRIDX" %6"PRIDX"], Nv-Nb[%6"PRIDX" %6"PRIDX"]. ICut: %6"PRIDX" [B]\n",
204  pwgts[0], pwgts[1], tpwgts[0], tpwgts[1], graph->nvtxs, graph->nbnd, graph->mincut));
205 
206  queue = rpqCreate(nvtxs);
207 
208  iset(nvtxs, -1, moved);
209 
210  ASSERT(ComputeCut(graph, where) == graph->mincut);
211  ASSERT(CheckBnd(graph));
212 
213  /* Insert the nodes of the proper partition whose size is OK in the priority queue */
214  irandArrayPermute(nvtxs, perm, nvtxs/5, 1);
215  for (ii=0; ii<nvtxs; ii++) {
216  i = perm[ii];
217  if (where[i] == from && vwgt[i] <= mindiff)
218  rpqInsert(queue, i, ed[i]-id[i]);
219  }
220 
221  mincut = graph->mincut;
222  nbnd = graph->nbnd;
223  for (nswaps=0; nswaps<nvtxs; nswaps++) {
224  if ((higain = rpqGetTop(queue)) == -1)
225  break;
226 
227  if (pwgts[to]+vwgt[higain] > tpwgts[to])
228  break;
229 
230  mincut -= (ed[higain]-id[higain]);
231  INC_DEC(pwgts[to], pwgts[from], vwgt[higain]);
232 
233  where[higain] = to;
234  moved[higain] = nswaps;
235 
237  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], mincut, pwgts[0], pwgts[1]));
238 
239  /**************************************************************
240  * Update the id[i]/ed[i] values of the affected nodes
241  ***************************************************************/
242  SWAP(id[higain], ed[higain], tmp);
243  if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
244  BNDDelete(nbnd, bndind, bndptr, higain);
245  if (ed[higain] > 0 && bndptr[higain] == -1)
246  BNDInsert(nbnd, bndind, bndptr, higain);
247 
248  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
249  k = adjncy[j];
250 
251  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
252  INC_DEC(id[k], ed[k], kwgt);
253 
254  /* Update the queue position */
255  if (moved[k] == -1 && where[k] == from && vwgt[k] <= mindiff)
256  rpqUpdate(queue, k, ed[k]-id[k]);
257 
258  /* Update its boundary information */
259  if (ed[k] == 0 && bndptr[k] != -1)
260  BNDDelete(nbnd, bndind, bndptr, k);
261  else if (ed[k] > 0 && bndptr[k] == -1)
262  BNDInsert(nbnd, bndind, bndptr, k);
263  }
264  }
265 
266  IFSET(ctrl->dbglvl, METIS_DBG_REFINE,
267  printf("\tMinimum cut: %6"PRIDX", PWGTS: [%6"PRIDX" %6"PRIDX"], NBND: %6"PRIDX"\n", mincut, pwgts[0], pwgts[1], nbnd));
268 
269  graph->mincut = mincut;
270  graph->nbnd = nbnd;
271 
272  rpqDestroy(queue);
273 
274  WCOREPOP;
275 }
276 
277 
278 /*************************************************************************
279 * This function performs an edge-based FM refinement
280 **************************************************************************/
282 {
283  idx_t i, ii, j, k, l, kwgt, nvtxs, ncon, nbnd, nswaps, from, to, pass,
284  me, limit, tmp, cnum;
285  idx_t *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts, *id, *ed, *bndptr, *bndind;
286  idx_t *moved, *swaps, *perm, *qnum, *qsizes;
287  idx_t higain, mincut, newcut, mincutorder;
288  real_t *invtvwgt, *minbalv, *newbalv, minbal, newbal;
289  rpq_t **queues;
290 
291  WCOREPUSH;
292 
293  nvtxs = graph->nvtxs;
294  ncon = graph->ncon;
295  xadj = graph->xadj;
296  vwgt = graph->vwgt;
297  adjncy = graph->adjncy;
298  adjwgt = graph->adjwgt;
299  invtvwgt = graph->invtvwgt;
300  where = graph->where;
301  id = graph->id;
302  ed = graph->ed;
303  pwgts = graph->pwgts;
304  bndptr = graph->bndptr;
305  bndind = graph->bndind;
306 
307  moved = iwspacemalloc(ctrl, nvtxs);
308  swaps = iwspacemalloc(ctrl, nvtxs);
309  perm = iwspacemalloc(ctrl, nvtxs);
310  qnum = iwspacemalloc(ctrl, nvtxs);
311  newbalv = rwspacemalloc(ctrl, ncon);
312  minbalv = rwspacemalloc(ctrl, ncon);
313  qsizes = iwspacemalloc(ctrl, 2*ncon);
314 
315  limit = gk_min(gk_max(0.01*nvtxs, 15), 100);
316 
317  /* Initialize the queues */
318  queues = (rpq_t **)wspacemalloc(ctrl, 2*ncon*sizeof(rpq_t *));
319  for (i=0; i<2*ncon; i++) {
320  queues[i] = rpqCreate(nvtxs);
321  qsizes[i] = 0;
322  }
323 
324  for (i=0; i<nvtxs; i++) {
325  qnum[i] = iargmax_nrm(ncon, vwgt+i*ncon, invtvwgt);
326  qsizes[2*qnum[i]+where[i]]++;
327  }
328 
329 
330  /* for the empty queues, move into them vertices from other queues */
331  for (from=0; from<2; from++) {
332  for (j=0; j<ncon; j++) {
333  if (qsizes[2*j+from] == 0) {
334  for (i=0; i<nvtxs; i++) {
335  if (where[i] != from)
336  continue;
337 
338  k = iargmax2_nrm(ncon, vwgt+i*ncon, invtvwgt);
339  if (k == j &&
340  qsizes[2*qnum[i]+from] > qsizes[2*j+from] &&
341  vwgt[i*ncon+qnum[i]]*invtvwgt[qnum[i]] < 1.3*vwgt[i*ncon+j]*invtvwgt[j]) {
342  qsizes[2*qnum[i]+from]--;
343  qsizes[2*j+from]++;
344  qnum[i] = j;
345  }
346  }
347  }
348  }
349  }
350 
351 
352  minbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ctrl->ubfactors, minbalv);
353  ASSERT(minbal > 0.0);
354 
355  newcut = mincut = graph->mincut;
356  mincutorder = -1;
357 
358  if (ctrl->dbglvl&METIS_DBG_REFINE) {
359  printf("Parts: [");
360  for (l=0; l<ncon; l++)
361  printf("(%6"PRIDX" %6"PRIDX" %.3"PRREAL" %.3"PRREAL") ",
362  pwgts[l], pwgts[ncon+l], ntpwgts[l], ntpwgts[ncon+l]);
363  printf("] Nv-Nb[%5"PRIDX", %5"PRIDX"]. ICut: %6"PRIDX", LB: %+.3"PRREAL" [B]\n",
364  graph->nvtxs, graph->nbnd, graph->mincut, minbal);
365  }
366 
367  iset(nvtxs, -1, moved);
368 
369  ASSERT(ComputeCut(graph, where) == graph->mincut);
370  ASSERT(CheckBnd(graph));
371 
372  /* Insert all nodes in the priority queues */
373  nbnd = graph->nbnd;
374  irandArrayPermute(nvtxs, perm, nvtxs/10, 1);
375  for (ii=0; ii<nvtxs; ii++) {
376  i = perm[ii];
377  rpqInsert(queues[2*qnum[i]+where[i]], i, ed[i]-id[i]);
378  }
379 
380  for (nswaps=0; nswaps<nvtxs; nswaps++) {
381  if (minbal <= 0.0)
382  break;
383 
384  SelectQueue(graph, ctrl->pijbm, ctrl->ubfactors, queues, &from, &cnum);
385  to = (from+1)%2;
386 
387  if (from == -1 || (higain = rpqGetTop(queues[2*cnum+from])) == -1)
388  break;
389 
390  newcut -= (ed[higain]-id[higain]);
391 
392  iaxpy(ncon, 1, vwgt+higain*ncon, 1, pwgts+to*ncon, 1);
393  iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
394  newbal = ComputeLoadImbalanceDiffVec(graph, 2, ctrl->pijbm, ctrl->ubfactors, newbalv);
395 
396  if (newbal < minbal || (newbal == minbal &&
397  (newcut < mincut ||
398  (newcut == mincut && BetterBalance2Way(ncon, minbalv, newbalv))))) {
399  mincut = newcut;
400  minbal = newbal;
401  mincutorder = nswaps;
402  rcopy(ncon, newbalv, minbalv);
403  }
404  else if (nswaps-mincutorder > limit) { /* We hit the limit, undo last move */
405  newcut += (ed[higain]-id[higain]);
406  iaxpy(ncon, 1, vwgt+higain*ncon, 1, pwgts+from*ncon, 1);
407  iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+to*ncon, 1);
408  break;
409  }
410 
411  where[higain] = to;
412  moved[higain] = nswaps;
413  swaps[nswaps] = higain;
414 
415  if (ctrl->dbglvl&METIS_DBG_MOVEINFO) {
416  printf("Moved %6"PRIDX" from %"PRIDX"(%"PRIDX"). Gain: %5"PRIDX", "
417  "Cut: %5"PRIDX", NPwgts: ", higain, from, cnum, ed[higain]-id[higain], newcut);
418  for (l=0; l<ncon; l++)
419  printf("(%6"PRIDX", %6"PRIDX") ", pwgts[l], pwgts[ncon+l]);
420  printf(", %+.3"PRREAL" LB: %+.3"PRREAL"\n", minbal, newbal);
421  }
422 
423 
424  /**************************************************************
425  * Update the id[i]/ed[i] values of the affected nodes
426  ***************************************************************/
427  SWAP(id[higain], ed[higain], tmp);
428  if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
429  BNDDelete(nbnd, bndind, bndptr, higain);
430  if (ed[higain] > 0 && bndptr[higain] == -1)
431  BNDInsert(nbnd, bndind, bndptr, higain);
432 
433  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
434  k = adjncy[j];
435 
436  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
437  INC_DEC(id[k], ed[k], kwgt);
438 
439  /* Update the queue position */
440  if (moved[k] == -1)
441  rpqUpdate(queues[2*qnum[k]+where[k]], k, ed[k]-id[k]);
442 
443  /* Update its boundary information */
444  if (ed[k] == 0 && bndptr[k] != -1)
445  BNDDelete(nbnd, bndind, bndptr, k);
446  else if (ed[k] > 0 && bndptr[k] == -1)
447  BNDInsert(nbnd, bndind, bndptr, k);
448  }
449  }
450 
451 
452 
453  /****************************************************************
454  * Roll back computations
455  *****************************************************************/
456  for (nswaps--; nswaps>mincutorder; nswaps--) {
457  higain = swaps[nswaps];
458 
459  to = where[higain] = (where[higain]+1)%2;
460  SWAP(id[higain], ed[higain], tmp);
461  if (ed[higain] == 0 && bndptr[higain] != -1 && xadj[higain] < xadj[higain+1])
462  BNDDelete(nbnd, bndind, bndptr, higain);
463  else if (ed[higain] > 0 && bndptr[higain] == -1)
464  BNDInsert(nbnd, bndind, bndptr, higain);
465 
466  iaxpy(ncon, 1, vwgt+higain*ncon, 1, pwgts+to*ncon, 1);
467  iaxpy(ncon, -1, vwgt+higain*ncon, 1, pwgts+((to+1)%2)*ncon, 1);
468  for (j=xadj[higain]; j<xadj[higain+1]; j++) {
469  k = adjncy[j];
470 
471  kwgt = (to == where[k] ? adjwgt[j] : -adjwgt[j]);
472  INC_DEC(id[k], ed[k], kwgt);
473 
474  if (bndptr[k] != -1 && ed[k] == 0)
475  BNDDelete(nbnd, bndind, bndptr, k);
476  if (bndptr[k] == -1 && ed[k] > 0)
477  BNDInsert(nbnd, bndind, bndptr, k);
478  }
479  }
480 
481  if (ctrl->dbglvl&METIS_DBG_REFINE) {
482  printf("\tMincut: %6"PRIDX" at %5"PRIDX", NBND: %6"PRIDX", NPwgts: [",
483  mincut, mincutorder, nbnd);
484  for (l=0; l<ncon; l++)
485  printf("(%6"PRIDX", %6"PRIDX") ", pwgts[l], pwgts[ncon+l]);
486  printf("], LB: %.3"PRREAL"\n", ComputeLoadImbalance(graph, 2, ctrl->pijbm));
487  }
488 
489  graph->mincut = mincut;
490  graph->nbnd = nbnd;
491 
492 
493  for (i=0; i<2*ncon; i++)
494  rpqDestroy(queues[i]);
495 
496  WCOREPOP;
497 }
498 
#define iabs
idx_t idx_t idx_t idx_t * vwgt
idx_t * bndind
#define SelectQueue
Definition: rename.h:77
#define iwspacemalloc
Definition: rename.h:256
#define BNDDelete(nbnd, bndind, bndptr, vtx)
void General2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
Definition: balance.c:169
#define irandArrayPermute
Definition: gklib_rename.h:62
#define ComputeLoadImbalanceDiff
Definition: rename.h:144
idx_t * xadj
#define rcopy
Definition: gklib_rename.h:80
void Balance2Way(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
Definition: balance.c:16
idx_t * pwgts
idx_t * adjwgt
idx_t * bndptr
idx_t idx_t * xadj
#define rwspacemalloc
Definition: rename.h:257
#define iargmax2_nrm
Definition: rename.h:244
idx_t * where
#define WCOREPUSH
idx_t nvtxs
idx_t * id
mdbglvl_et dbglvl
Real fabs(const Real &a)
NonlinearFactorGraph graph
static const Similarity3 id
idx_t * ed
#define ComputeLoadImbalance
Definition: rename.h:143
#define PRIDX
#define ASSERT(expression)
Definition: ccolamd.c:872
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
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
void Bnd2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
Definition: balance.c:41
#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
#define PRREAL
#define WCOREPOP
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
real_t * invtvwgt
void McGeneral2WayBalance(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts)
Definition: balance.c:281
#define ComputeCut
Definition: rename.h:62
#define SWAP
std::ptrdiff_t j
#define rpqDestroy
Definition: gklib_rename.h:100
#define wspacemalloc
Definition: rename.h:253
idx_t * vwgt


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:33:56