kwayrefine.c
Go to the documentation of this file.
1 
11 #include "metislib.h"
12 
13 
14 /*************************************************************************/
16 /*************************************************************************/
17 void RefineKWay(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph)
18 {
19  idx_t i, nlevels, contig=ctrl->contig;
20  graph_t *ptr;
21 
23 
24  /* Determine how many levels are there */
25  for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++);
26 
27  /* Compute the parameters of the coarsest graph */
28  ComputeKWayPartitionParams(ctrl, graph);
29 
30  /* Try to minimize the sub-domain connectivity */
31  if (ctrl->minconn)
32  EliminateSubDomainEdges(ctrl, graph);
33 
34  /* Deal with contiguity constraints at the beginning */
35  if (contig && FindPartitionInducedComponents(graph, graph->where, NULL, NULL) > ctrl->nparts) {
36  EliminateComponents(ctrl, graph);
37 
39  Greedy_KWayOptimize(ctrl, graph, 5, 0, OMODE_BALANCE);
40 
41  ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
42  Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 0, OMODE_REFINE);
43 
44  ctrl->contig = 0;
45  }
46 
47  /* Refine each successively finer graph */
48  for (i=0; ;i++) {
49  if (ctrl->minconn && i == nlevels/2)
50  EliminateSubDomainEdges(ctrl, graph);
51 
53 
54  if (2*i >= nlevels && !IsBalanced(ctrl, graph, .02)) {
56  Greedy_KWayOptimize(ctrl, graph, 1, 0, OMODE_BALANCE);
57  ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
58  }
59 
60  Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 5.0, OMODE_REFINE);
61 
63 
64  /* Deal with contiguity constraints in the middle */
65  if (contig && i == nlevels/2) {
66  if (FindPartitionInducedComponents(graph, graph->where, NULL, NULL) > ctrl->nparts) {
67  EliminateComponents(ctrl, graph);
68 
69  if (!IsBalanced(ctrl, graph, .02)) {
70  ctrl->contig = 1;
72  Greedy_KWayOptimize(ctrl, graph, 5, 0, OMODE_BALANCE);
73 
74  ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
75  Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 0, OMODE_REFINE);
76  ctrl->contig = 0;
77  }
78  }
79  }
80 
81  if (graph == orggraph)
82  break;
83 
84  graph = graph->finer;
85 
87  ASSERT(graph->vwgt != NULL);
88 
89  ProjectKWayPartition(ctrl, graph);
91  }
92 
93  /* Deal with contiguity requirement at the end */
94  ctrl->contig = contig;
95  if (contig && FindPartitionInducedComponents(graph, graph->where, NULL, NULL) > ctrl->nparts)
96  EliminateComponents(ctrl, graph);
97 
98  if (!IsBalanced(ctrl, graph, 0.0)) {
100  Greedy_KWayOptimize(ctrl, graph, 10, 0, OMODE_BALANCE);
101 
102  ComputeKWayBoundary(ctrl, graph, BNDTYPE_REFINE);
103  Greedy_KWayOptimize(ctrl, graph, ctrl->niter, 0, OMODE_REFINE);
104  }
105 
106  if (ctrl->contig)
107  ASSERT(FindPartitionInducedComponents(graph, graph->where, NULL, NULL) == ctrl->nparts);
108 
110 }
111 
112 
113 /*************************************************************************/
115 /*************************************************************************/
117 {
118 
119  graph->pwgts = imalloc(ctrl->nparts*graph->ncon, "AllocateKWayPartitionMemory: pwgts");
120  graph->where = imalloc(graph->nvtxs, "AllocateKWayPartitionMemory: where");
121  graph->bndptr = imalloc(graph->nvtxs, "AllocateKWayPartitionMemory: bndptr");
122  graph->bndind = imalloc(graph->nvtxs, "AllocateKWayPartitionMemory: bndind");
123 
124  switch (ctrl->objtype) {
125  case METIS_OBJTYPE_CUT:
126  graph->ckrinfo = (ckrinfo_t *)gk_malloc(graph->nvtxs*sizeof(ckrinfo_t),
127  "AllocateKWayPartitionMemory: ckrinfo");
128  break;
129 
130  case METIS_OBJTYPE_VOL:
131  graph->vkrinfo = (vkrinfo_t *)gk_malloc(graph->nvtxs*sizeof(vkrinfo_t),
132  "AllocateKWayVolPartitionMemory: vkrinfo");
133 
134  /* This is to let the cut-based -minconn and -contig large-scale graph
135  changes to go through */
136  graph->ckrinfo = (ckrinfo_t *)graph->vkrinfo;
137  break;
138 
139  default:
140  gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
141  }
142 
143 }
144 
145 
146 /*************************************************************************/
148 /**************************************************************************/
150 {
151  idx_t i, j, k, l, nvtxs, ncon, nparts, nbnd, mincut, me, other;
152  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
153 
154  nparts = ctrl->nparts;
155 
156  nvtxs = graph->nvtxs;
157  ncon = graph->ncon;
158  xadj = graph->xadj;
159  vwgt = graph->vwgt;
160  adjncy = graph->adjncy;
161  adjwgt = graph->adjwgt;
162 
163  where = graph->where;
164  pwgts = iset(nparts*ncon, 0, graph->pwgts);
165  bndind = graph->bndind;
166  bndptr = iset(nvtxs, -1, graph->bndptr);
167 
168  nbnd = mincut = 0;
169 
170  /* Compute pwgts */
171  if (ncon == 1) {
172  for (i=0; i<nvtxs; i++) {
173  ASSERT(where[i] >= 0 && where[i] < nparts);
174  pwgts[where[i]] += vwgt[i];
175  }
176  }
177  else {
178  for (i=0; i<nvtxs; i++) {
179  me = where[i];
180  for (j=0; j<ncon; j++)
181  pwgts[me*ncon+j] += vwgt[i*ncon+j];
182  }
183  }
184 
185  /* Compute the required info for refinement */
186  switch (ctrl->objtype) {
187  case METIS_OBJTYPE_CUT:
188  {
189  ckrinfo_t *myrinfo;
190  cnbr_t *mynbrs;
191 
192  memset(graph->ckrinfo, 0, sizeof(ckrinfo_t)*nvtxs);
193  cnbrpoolReset(ctrl);
194 
195  for (i=0; i<nvtxs; i++) {
196  me = where[i];
197  myrinfo = graph->ckrinfo+i;
198 
199  for (j=xadj[i]; j<xadj[i+1]; j++) {
200  if (me == where[adjncy[j]])
201  myrinfo->id += adjwgt[j];
202  else
203  myrinfo->ed += adjwgt[j];
204  }
205 
206  /* Time to compute the particular external degrees */
207  if (myrinfo->ed > 0) {
208  mincut += myrinfo->ed;
209 
210  myrinfo->inbr = cnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
211  mynbrs = ctrl->cnbrpool + myrinfo->inbr;
212 
213  for (j=xadj[i]; j<xadj[i+1]; j++) {
214  other = where[adjncy[j]];
215  if (me != other) {
216  for (k=0; k<myrinfo->nnbrs; k++) {
217  if (mynbrs[k].pid == other) {
218  mynbrs[k].ed += adjwgt[j];
219  break;
220  }
221  }
222  if (k == myrinfo->nnbrs) {
223  mynbrs[k].pid = other;
224  mynbrs[k].ed = adjwgt[j];
225  myrinfo->nnbrs++;
226  }
227  }
228  }
229 
230  ASSERT(myrinfo->nnbrs <= xadj[i+1]-xadj[i]);
231 
232  /* Only ed-id>=0 nodes are considered to be in the boundary */
233  if (myrinfo->ed-myrinfo->id >= 0)
234  BNDInsert(nbnd, bndind, bndptr, i);
235  }
236  else {
237  myrinfo->inbr = -1;
238  }
239  }
240 
241  graph->mincut = mincut/2;
242  graph->nbnd = nbnd;
243 
244  }
245  ASSERT(CheckBnd2(graph));
246  break;
247 
248  case METIS_OBJTYPE_VOL:
249  {
250  vkrinfo_t *myrinfo;
251  vnbr_t *mynbrs;
252 
253  memset(graph->vkrinfo, 0, sizeof(vkrinfo_t)*nvtxs);
254  vnbrpoolReset(ctrl);
255 
256  /* Compute now the id/ed degrees */
257  for (i=0; i<nvtxs; i++) {
258  me = where[i];
259  myrinfo = graph->vkrinfo+i;
260 
261  for (j=xadj[i]; j<xadj[i+1]; j++) {
262  if (me == where[adjncy[j]])
263  myrinfo->nid++;
264  else
265  myrinfo->ned++;
266  }
267 
268  /* Time to compute the particular external degrees */
269  if (myrinfo->ned > 0) {
270  mincut += myrinfo->ned;
271 
272  myrinfo->inbr = vnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
273  mynbrs = ctrl->vnbrpool + myrinfo->inbr;
274 
275  for (j=xadj[i]; j<xadj[i+1]; j++) {
276  other = where[adjncy[j]];
277  if (me != other) {
278  for (k=0; k<myrinfo->nnbrs; k++) {
279  if (mynbrs[k].pid == other) {
280  mynbrs[k].ned++;
281  break;
282  }
283  }
284  if (k == myrinfo->nnbrs) {
285  mynbrs[k].gv = 0;
286  mynbrs[k].pid = other;
287  mynbrs[k].ned = 1;
288  myrinfo->nnbrs++;
289  }
290  }
291  }
292  ASSERT(myrinfo->nnbrs <= xadj[i+1]-xadj[i]);
293  }
294  else {
295  myrinfo->inbr = -1;
296  }
297  }
298  graph->mincut = mincut/2;
299 
300  ComputeKWayVolGains(ctrl, graph);
301  }
302  ASSERT(graph->minvol == ComputeVolume(graph, graph->where));
303  break;
304  default:
305  gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
306  }
307 
308 }
309 
310 
311 /*************************************************************************/
314 /*************************************************************************/
316 {
317  idx_t i, j, k, nvtxs, nbnd, nparts, me, other, istart, iend, tid, ted;
318  idx_t *xadj, *adjncy, *adjwgt;
319  idx_t *cmap, *where, *bndptr, *bndind, *cwhere, *htable;
320  graph_t *cgraph;
321 
322  WCOREPUSH;
323 
324  nparts = ctrl->nparts;
325 
326  cgraph = graph->coarser;
327  cwhere = cgraph->where;
328 
329  nvtxs = graph->nvtxs;
330  cmap = graph->cmap;
331  xadj = graph->xadj;
332  adjncy = graph->adjncy;
333  adjwgt = graph->adjwgt;
334 
335  AllocateKWayPartitionMemory(ctrl, graph);
336 
337  where = graph->where;
338  bndind = graph->bndind;
339  bndptr = iset(nvtxs, -1, graph->bndptr);
340 
341  htable = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
342 
343  /* Compute the required info for refinement */
344  switch (ctrl->objtype) {
345  case METIS_OBJTYPE_CUT:
346  ASSERT(CheckBnd2(cgraph));
347  {
348  ckrinfo_t *myrinfo;
349  cnbr_t *mynbrs;
350 
351  /* go through and project partition and compute id/ed for the nodes */
352  for (i=0; i<nvtxs; i++) {
353  k = cmap[i];
354  where[i] = cwhere[k];
355  cmap[i] = cgraph->ckrinfo[k].ed; /* For optimization */
356  }
357 
358  memset(graph->ckrinfo, 0, sizeof(ckrinfo_t)*nvtxs);
359  cnbrpoolReset(ctrl);
360 
361  for (nbnd=0, i=0; i<nvtxs; i++) {
362  istart = xadj[i];
363  iend = xadj[i+1];
364 
365  myrinfo = graph->ckrinfo+i;
366 
367  if (cmap[i] == 0) { /* Interior node. Note that cmap[i] = crinfo[cmap[i]].ed */
368  for (tid=0, j=istart; j<iend; j++)
369  tid += adjwgt[j];
370 
371  myrinfo->id = tid;
372  myrinfo->inbr = -1;
373  }
374  else { /* Potentially an interface node */
375  myrinfo->inbr = cnbrpoolGetNext(ctrl, iend-istart+1);
376  mynbrs = ctrl->cnbrpool + myrinfo->inbr;
377 
378  me = where[i];
379  for (tid=0, ted=0, j=istart; j<iend; j++) {
380  other = where[adjncy[j]];
381  if (me == other) {
382  tid += adjwgt[j];
383  }
384  else {
385  ted += adjwgt[j];
386  if ((k = htable[other]) == -1) {
387  htable[other] = myrinfo->nnbrs;
388  mynbrs[myrinfo->nnbrs].pid = other;
389  mynbrs[myrinfo->nnbrs++].ed = adjwgt[j];
390  }
391  else {
392  mynbrs[k].ed += adjwgt[j];
393  }
394  }
395  }
396  myrinfo->id = tid;
397  myrinfo->ed = ted;
398 
399  /* Remove space for edegrees if it was interior */
400  if (ted == 0) {
401  ctrl->nbrpoolcpos -= iend-istart+1;
402  myrinfo->inbr = -1;
403  }
404  else {
405  if (ted-tid >= 0)
406  BNDInsert(nbnd, bndind, bndptr, i);
407 
408  for (j=0; j<myrinfo->nnbrs; j++)
409  htable[mynbrs[j].pid] = -1;
410  }
411  }
412  }
413 
414  graph->nbnd = nbnd;
415 
416  }
417  ASSERT(CheckBnd2(graph));
418  break;
419 
420  case METIS_OBJTYPE_VOL:
421  {
422  vkrinfo_t *myrinfo;
423  vnbr_t *mynbrs;
424 
425  ASSERT(cgraph->minvol == ComputeVolume(cgraph, cgraph->where));
426 
427  /* go through and project partition and compute id/ed for the nodes */
428  for (i=0; i<nvtxs; i++) {
429  k = cmap[i];
430  where[i] = cwhere[k];
431  cmap[i] = cgraph->vkrinfo[k].ned; /* For optimization */
432  }
433 
434  memset(graph->vkrinfo, 0, sizeof(vkrinfo_t)*nvtxs);
435  vnbrpoolReset(ctrl);
436 
437  for (i=0; i<nvtxs; i++) {
438  istart = xadj[i];
439  iend = xadj[i+1];
440  myrinfo = graph->vkrinfo+i;
441 
442  if (cmap[i] == 0) { /* Note that cmap[i] = crinfo[cmap[i]].ed */
443  myrinfo->nid = iend-istart;
444  myrinfo->inbr = -1;
445  }
446  else { /* Potentially an interface node */
447  myrinfo->inbr = vnbrpoolGetNext(ctrl, iend-istart+1);
448  mynbrs = ctrl->vnbrpool + myrinfo->inbr;
449 
450  me = where[i];
451  for (tid=0, ted=0, j=istart; j<iend; j++) {
452  other = where[adjncy[j]];
453  if (me == other) {
454  tid++;
455  }
456  else {
457  ted++;
458  if ((k = htable[other]) == -1) {
459  htable[other] = myrinfo->nnbrs;
460  mynbrs[myrinfo->nnbrs].gv = 0;
461  mynbrs[myrinfo->nnbrs].pid = other;
462  mynbrs[myrinfo->nnbrs++].ned = 1;
463  }
464  else {
465  mynbrs[k].ned++;
466  }
467  }
468  }
469  myrinfo->nid = tid;
470  myrinfo->ned = ted;
471 
472  /* Remove space for edegrees if it was interior */
473  if (ted == 0) {
474  ctrl->nbrpoolcpos -= iend-istart+1;
475  myrinfo->inbr = -1;
476  }
477  else {
478  for (j=0; j<myrinfo->nnbrs; j++)
479  htable[mynbrs[j].pid] = -1;
480  }
481  }
482  }
483 
484  ComputeKWayVolGains(ctrl, graph);
485 
486  ASSERT(graph->minvol == ComputeVolume(graph, graph->where));
487  }
488  break;
489 
490  default:
491  gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
492  }
493 
494  graph->mincut = cgraph->mincut;
495  icopy(nparts*graph->ncon, cgraph->pwgts, graph->pwgts);
496 
497  FreeGraph(&graph->coarser);
498  graph->coarser = NULL;
499 
500  WCOREPOP;
501 }
502 
503 
504 /*************************************************************************/
506 /*************************************************************************/
508 {
509  idx_t i, nvtxs, nbnd;
510  idx_t *bndind, *bndptr;
511 
512  nvtxs = graph->nvtxs;
513  bndind = graph->bndind;
514  bndptr = iset(nvtxs, -1, graph->bndptr);
515 
516  nbnd = 0;
517 
518  switch (ctrl->objtype) {
519  case METIS_OBJTYPE_CUT:
520  /* Compute the boundary */
521  if (bndtype == BNDTYPE_REFINE) {
522  for (i=0; i<nvtxs; i++) {
523  if (graph->ckrinfo[i].ed-graph->ckrinfo[i].id >= 0)
524  BNDInsert(nbnd, bndind, bndptr, i);
525  }
526  }
527  else { /* BNDTYPE_BALANCE */
528  for (i=0; i<nvtxs; i++) {
529  if (graph->ckrinfo[i].ed > 0)
530  BNDInsert(nbnd, bndind, bndptr, i);
531  }
532  }
533  break;
534 
535  case METIS_OBJTYPE_VOL:
536  /* Compute the boundary */
537  if (bndtype == BNDTYPE_REFINE) {
538  for (i=0; i<nvtxs; i++) {
539  if (graph->vkrinfo[i].gv >= 0)
540  BNDInsert(nbnd, bndind, bndptr, i);
541  }
542  }
543  else { /* BNDTYPE_BALANCE */
544  for (i=0; i<nvtxs; i++) {
545  if (graph->vkrinfo[i].ned > 0)
546  BNDInsert(nbnd, bndind, bndptr, i);
547  }
548  }
549  break;
550 
551  default:
552  gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
553  }
554 
555  graph->nbnd = nbnd;
556 }
557 
558 
559 /*************************************************************************/
561 /*************************************************************************/
563 {
564  idx_t i, ii, j, k, l, nvtxs, nparts, me, other, pid;
565  idx_t *xadj, *vsize, *adjncy, *adjwgt, *where,
566  *bndind, *bndptr, *ophtable;
567  vkrinfo_t *myrinfo, *orinfo;
568  vnbr_t *mynbrs, *onbrs;
569 
570  WCOREPUSH;
571 
572  nparts = ctrl->nparts;
573 
574  nvtxs = graph->nvtxs;
575  xadj = graph->xadj;
576  vsize = graph->vsize;
577  adjncy = graph->adjncy;
578  adjwgt = graph->adjwgt;
579 
580  where = graph->where;
581  bndind = graph->bndind;
582  bndptr = iset(nvtxs, -1, graph->bndptr);
583 
584  ophtable = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
585 
586  /* Compute the volume gains */
587  graph->minvol = graph->nbnd = 0;
588  for (i=0; i<nvtxs; i++) {
589  myrinfo = graph->vkrinfo+i;
590  myrinfo->gv = IDX_MIN;
591 
592  if (myrinfo->nnbrs > 0) {
593  me = where[i];
594  mynbrs = ctrl->vnbrpool + myrinfo->inbr;
595 
596  graph->minvol += myrinfo->nnbrs*vsize[i];
597 
598  for (j=xadj[i]; j<xadj[i+1]; j++) {
599  ii = adjncy[j];
600  other = where[ii];
601  orinfo = graph->vkrinfo+ii;
602  onbrs = ctrl->vnbrpool + orinfo->inbr;
603 
604  for (k=0; k<orinfo->nnbrs; k++)
605  ophtable[onbrs[k].pid] = k;
606  ophtable[other] = 1; /* this is to simplify coding */
607 
608  if (me == other) {
609  /* Find which domains 'i' is connected to but 'ii' is not
610  and update their gain */
611  for (k=0; k<myrinfo->nnbrs; k++) {
612  if (ophtable[mynbrs[k].pid] == -1)
613  mynbrs[k].gv -= vsize[ii];
614  }
615  }
616  else {
617  ASSERT(ophtable[me] != -1);
618 
619  if (onbrs[ophtable[me]].ned == 1) {
620  /* I'm the only connection of 'ii' in 'me' */
621  /* Increase the gains for all the common domains between 'i' and 'ii' */
622  for (k=0; k<myrinfo->nnbrs; k++) {
623  if (ophtable[mynbrs[k].pid] != -1)
624  mynbrs[k].gv += vsize[ii];
625  }
626  }
627  else {
628  /* Find which domains 'i' is connected to and 'ii' is not
629  and update their gain */
630  for (k=0; k<myrinfo->nnbrs; k++) {
631  if (ophtable[mynbrs[k].pid] == -1)
632  mynbrs[k].gv -= vsize[ii];
633  }
634  }
635  }
636 
637  /* Reset the marker vector */
638  for (k=0; k<orinfo->nnbrs; k++)
639  ophtable[onbrs[k].pid] = -1;
640  ophtable[other] = -1;
641  }
642 
643  /* Compute the max vgain */
644  for (k=0; k<myrinfo->nnbrs; k++) {
645  if (mynbrs[k].gv > myrinfo->gv)
646  myrinfo->gv = mynbrs[k].gv;
647  }
648 
649  /* Add the extra gain due to id == 0 */
650  if (myrinfo->ned > 0 && myrinfo->nid == 0)
651  myrinfo->gv += vsize[i];
652  }
653 
654  if (myrinfo->gv >= 0)
655  BNDInsert(graph->nbnd, bndind, bndptr, i);
656  }
657 
658  WCOREPOP;
659 }
660 
661 
662 /*************************************************************************/
665 /*************************************************************************/
666 int IsBalanced(ctrl_t *ctrl, graph_t *graph, real_t ffactor)
667 {
668  return
669  (ComputeLoadImbalanceDiff(graph, ctrl->nparts, ctrl->pijbm, ctrl->ubfactors)
670  <= ffactor);
671 }
672 
void ComputeKWayPartitionParams(ctrl_t *ctrl, graph_t *graph)
Definition: kwayrefine.c:149
idx_t idx_t idx_t idx_t * vwgt
idx_t ned
idx_t * bndind
double RefTmr
void RefineKWay(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph)
Definition: kwayrefine.c:17
#define iwspacemalloc
Definition: rename.h:256
#define gk_startcputimer(tmr)
Definition: gk_macros.h:33
#define ComputeLoadImbalanceDiff
Definition: rename.h:144
idx_t * xadj
#define IDX_MIN
vnbr_t * vnbrpool
#define imalloc
Definition: gklib_rename.h:42
void AllocateKWayPartitionMemory(ctrl_t *ctrl, graph_t *graph)
Definition: kwayrefine.c:116
#define vnbrpoolGetNext
Definition: rename.h:262
#define gk_stopcputimer(tmr)
Definition: gk_macros.h:34
idx_t * pwgts
idx_t * adjwgt
struct graph_t * finer
#define cnbrpoolReset
Definition: rename.h:259
#define FreeGraph
Definition: rename.h:98
idx_t * bndptr
idx_t idx_t * xadj
idx_t minvol
idx_t * where
idx_t pid
#define EliminateComponents
Definition: rename.h:57
#define BNDTYPE_BALANCE
Definition: libmetis/defs.h:31
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
NonlinearFactorGraph graph
idx_t pid
size_t nbrpoolcpos
idx_t idx_t idx_t idx_t idx_t * vsize
struct graph_t * coarser
idx_t niter
#define ASSERT(expression)
Definition: ccolamd.c:872
static const Line3 l(Rot3(), 1, 1)
double UncoarsenTmr
#define OMODE_BALANCE
Definition: libmetis/defs.h:35
#define BNDInsert(nbnd, bndind, bndptr, vtx)
idx_t * cmap
#define SIGERR
Definition: gk_defs.h:38
int32_t idx_t
cnbr_t * cnbrpool
#define BNDTYPE_REFINE
Definition: libmetis/defs.h:30
idx_t nparts
#define EliminateSubDomainEdges
Definition: rename.h:164
real_t * pijbm
idx_t ncon
int IsBalanced(ctrl_t *ctrl, graph_t *graph, real_t ffactor)
Definition: kwayrefine.c:666
float real_t
idx_t * ncon
#define NULL
Definition: ccolamd.c:609
#define ComputeVolume
Definition: rename.h:63
idx_t mincut
idx_t gv
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
#define CheckBnd2
Definition: rename.h:66
real_t * ubfactors
#define iset
Definition: gklib_rename.h:67
#define icopy
Definition: gklib_rename.h:28
void * gk_malloc(size_t nbytes, char *msg)
Definition: memory.c:140
idx_t idx_t idx_t idx_t * where
idx_t * adjncy
#define cnbrpoolGetNext
Definition: rename.h:260
idx_t contig
idx_t idx_t idx_t * adjncy
void ComputeKWayVolGains(ctrl_t *ctrl, graph_t *graph)
Definition: kwayrefine.c:562
#define WCOREPOP
void ComputeKWayBoundary(ctrl_t *ctrl, graph_t *graph, idx_t bndtype)
Definition: kwayrefine.c:507
idx_t ed
#define OMODE_REFINE
Definition: libmetis/defs.h:34
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
void ProjectKWayPartition(ctrl_t *ctrl, graph_t *graph)
Definition: kwayrefine.c:315
#define vnbrpoolReset
Definition: rename.h:261
#define Greedy_KWayOptimize
Definition: rename.h:114
double ProjectTmr
idx_t minconn
std::ptrdiff_t j
mobjtype_et objtype
vkrinfo_t * vkrinfo
#define FindPartitionInducedComponents
Definition: rename.h:53
ckrinfo_t * ckrinfo
idx_t * vwgt


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