ometis.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * ometis.c
5  *
6  * This file contains the top level routines for the multilevel recursive
7  * bisection algorithm PMETIS.
8  *
9  * Started 7/24/97
10  * George
11  *
12  * $Id: ometis.c 10513 2011-07-07 22:06:03Z karypis $
13  *
14  */
15 
16 #include "metislib.h"
17 
18 
19 /*************************************************************************/
42 /*************************************************************************/
45 {
46  int sigrval=0, renumber=0;
47  idx_t i, ii, j, l, nnvtxs=0;
49  ctrl_t *ctrl;
50  idx_t *cptr, *cind, *piperm;
51  int numflag = 0;
52 
53  /* set up malloc cleaning code and signal catchers */
54  if (!gk_malloc_init())
55  return METIS_ERROR_MEMORY;
56 
57  gk_sigtrap();
58 
59  if ((sigrval = gk_sigcatch()) != 0)
60  goto SIGTHROW;
61 
62 
63  /* set up the run time parameters */
64  ctrl = SetupCtrl(METIS_OP_OMETIS, options, 1, 3, NULL, NULL);
65  if (!ctrl) {
66  gk_siguntrap();
67  return METIS_ERROR_INPUT;
68  }
69 
70  /* if required, change the numbering to 0 */
71  if (ctrl->numflag == 1) {
72  Change2CNumbering(*nvtxs, xadj, adjncy);
73  renumber = 1;
74  }
75 
76  IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));
78 
79  /* prune the dense columns */
80  if (ctrl->pfactor > 0.0) {
81  piperm = imalloc(*nvtxs, "OMETIS: piperm");
82 
83  graph = PruneGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, piperm, ctrl->pfactor);
84  if (graph == NULL) {
85  /* if there was no prunning, cleanup the pfactor */
86  gk_free((void **)&piperm, LTERM);
87  ctrl->pfactor = 0.0;
88  }
89  else {
90  nnvtxs = graph->nvtxs;
91  ctrl->compress = 0; /* disable compression if prunning took place */
92  }
93  }
94 
95  /* compress the graph; note that compression only happens if not prunning
96  has taken place. */
97  if (ctrl->compress) {
98  cptr = imalloc(*nvtxs+1, "OMETIS: cptr");
99  cind = imalloc(*nvtxs, "OMETIS: cind");
100 
101  graph = CompressGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, cptr, cind);
102  if (graph == NULL) {
103  /* if there was no compression, cleanup the compress flag */
104  gk_free((void **)&cptr, &cind, LTERM);
105  ctrl->compress = 0;
106  }
107  else {
108  nnvtxs = graph->nvtxs;
109  ctrl->cfactor = 1.0*(*nvtxs)/nnvtxs;
110  if (ctrl->cfactor > 1.5 && ctrl->nseps == 1)
111  ctrl->nseps = 2;
112  //ctrl->nseps = (idx_t)(ctrl->cfactor*ctrl->nseps);
113  }
114  }
115 
116  /* if no prunning and no compression, setup the graph in the normal way. */
117  if (ctrl->pfactor == 0.0 && ctrl->compress == 0)
118  graph = SetupGraph(ctrl, *nvtxs, 1, xadj, adjncy, vwgt, NULL, NULL);
119 
120  ASSERT(CheckGraph(graph, ctrl->numflag, 1));
121 
122  /* allocate workspace memory */
123  AllocateWorkSpace(ctrl, graph);
124 
125  /* do the nested dissection ordering */
126  if (ctrl->ccorder)
127  MlevelNestedDissectionCC(ctrl, graph, iperm, graph->nvtxs);
128  else
129  MlevelNestedDissection(ctrl, graph, iperm, graph->nvtxs);
130 
131 
132  if (ctrl->pfactor > 0.0) { /* Order any prunned vertices */
133  icopy(nnvtxs, iperm, perm); /* Use perm as an auxiliary array */
134  for (i=0; i<nnvtxs; i++)
135  iperm[piperm[i]] = perm[i];
136  for (i=nnvtxs; i<*nvtxs; i++)
137  iperm[piperm[i]] = i;
138 
139  gk_free((void **)&piperm, LTERM);
140  }
141  else if (ctrl->compress) { /* Uncompress the ordering */
142  /* construct perm from iperm */
143  for (i=0; i<nnvtxs; i++)
144  perm[iperm[i]] = i;
145  for (l=ii=0; ii<nnvtxs; ii++) {
146  i = perm[ii];
147  for (j=cptr[i]; j<cptr[i+1]; j++)
148  iperm[cind[j]] = l++;
149  }
150 
151  gk_free((void **)&cptr, &cind, LTERM);
152  }
153 
154  for (i=0; i<*nvtxs; i++)
155  perm[iperm[i]] = i;
156 
158  IFSET(ctrl->dbglvl, METIS_DBG_TIME, PrintTimers(ctrl));
159 
160  /* clean up */
161  FreeCtrl(&ctrl);
162 
163 SIGTHROW:
164  /* if required, change the numbering back to 1 */
165  if (renumber)
166  Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);
167 
168  gk_siguntrap();
170 
171  return metis_rcode(sigrval);
172 }
173 
174 
175 /*************************************************************************/
182 /*************************************************************************/
184  idx_t lastvtx)
185 {
186  idx_t i, j, nvtxs, nbnd;
187  idx_t *label, *bndind;
188  graph_t *lgraph, *rgraph;
189 
190  nvtxs = graph->nvtxs;
191 
192  MlevelNodeBisectionMultiple(ctrl, graph);
193 
195  printf("Nvtxs: %6"PRIDX", [%6"PRIDX" %6"PRIDX" %6"PRIDX"]\n",
196  graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
197 
198 
199  /* Order the nodes in the separator */
200  nbnd = graph->nbnd;
201  bndind = graph->bndind;
202  label = graph->label;
203  for (i=0; i<nbnd; i++)
204  order[label[bndind[i]]] = --lastvtx;
205 
206  SplitGraphOrder(ctrl, graph, &lgraph, &rgraph);
207 
208  /* Free the memory of the top level graph */
209  FreeGraph(&graph);
210 
211  /* Recurse on lgraph first, as its lastvtx depends on rgraph->nvtxs, which
212  will not be defined upon return from MlevelNestedDissection. */
213  if (lgraph->nvtxs > MMDSWITCH && lgraph->nedges > 0)
214  MlevelNestedDissection(ctrl, lgraph, order, lastvtx-rgraph->nvtxs);
215  else {
216  MMDOrder(ctrl, lgraph, order, lastvtx-rgraph->nvtxs);
217  FreeGraph(&lgraph);
218  }
219  if (rgraph->nvtxs > MMDSWITCH && rgraph->nedges > 0)
220  MlevelNestedDissection(ctrl, rgraph, order, lastvtx);
221  else {
222  MMDOrder(ctrl, rgraph, order, lastvtx);
223  FreeGraph(&rgraph);
224  }
225 }
226 
227 
228 /*************************************************************************/
235 /*************************************************************************/
237  idx_t lastvtx)
238 {
239  idx_t i, j, nvtxs, nbnd, ncmps, rnvtxs, snvtxs;
240  idx_t *label, *bndind;
241  idx_t *cptr, *cind;
242  graph_t **sgraphs;
243 
244  nvtxs = graph->nvtxs;
245 
246  MlevelNodeBisectionMultiple(ctrl, graph);
247 
249  printf("Nvtxs: %6"PRIDX", [%6"PRIDX" %6"PRIDX" %6"PRIDX"]\n",
250  graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
251 
252  /* Order the nodes in the separator */
253  nbnd = graph->nbnd;
254  bndind = graph->bndind;
255  label = graph->label;
256  for (i=0; i<nbnd; i++)
257  order[label[bndind[i]]] = --lastvtx;
258 
259  WCOREPUSH;
260  cptr = iwspacemalloc(ctrl, nvtxs+1);
261  cind = iwspacemalloc(ctrl, nvtxs);
262  ncmps = FindSepInducedComponents(ctrl, graph, cptr, cind);
263 
264  if (ctrl->dbglvl&METIS_DBG_INFO) {
265  if (ncmps > 2)
266  printf(" Bisection resulted in %"PRIDX" connected components\n", ncmps);
267  }
268 
269  sgraphs = SplitGraphOrderCC(ctrl, graph, ncmps, cptr, cind);
270 
271  WCOREPOP;
272 
273  /* Free the memory of the top level graph */
274  FreeGraph(&graph);
275 
276  /* Go and process the subgraphs */
277  for (rnvtxs=i=0; i<ncmps; i++) {
278  /* Save the number of vertices in sgraphs[i] because sgraphs[i] is freed
279  inside MlevelNestedDissectionCC, and as such it will be undefined. */
280  snvtxs = sgraphs[i]->nvtxs;
281 
282  if (sgraphs[i]->nvtxs > MMDSWITCH && sgraphs[i]->nedges > 0) {
283  MlevelNestedDissectionCC(ctrl, sgraphs[i], order, lastvtx-rnvtxs);
284  }
285  else {
286  MMDOrder(ctrl, sgraphs[i], order, lastvtx-rnvtxs);
287  FreeGraph(&sgraphs[i]);
288  }
289  rnvtxs += snvtxs;
290  }
291 
292  gk_free((void **)&sgraphs, LTERM);
293 }
294 
295 
296 /*************************************************************************/
299 /*************************************************************************/
301 {
302  idx_t i, mincut;
303  idx_t *bestwhere;
304 
305  /* if the graph is small, just find a single vertex separator */
306  if (ctrl->nseps == 1 || graph->nvtxs < (ctrl->compress ? 1000 : 2000)) {
307  MlevelNodeBisectionL2(ctrl, graph, LARGENIPARTS);
308  return;
309  }
310 
311  WCOREPUSH;
312 
313  bestwhere = iwspacemalloc(ctrl, graph->nvtxs);
314 
315  mincut = graph->tvwgt[0];
316  for (i=0; i<ctrl->nseps; i++) {
317  MlevelNodeBisectionL2(ctrl, graph, LARGENIPARTS);
318 
319  if (i == 0 || graph->mincut < mincut) {
320  mincut = graph->mincut;
321  if (i < ctrl->nseps-1)
322  icopy(graph->nvtxs, graph->where, bestwhere);
323  }
324 
325  if (mincut == 0)
326  break;
327 
328  if (i < ctrl->nseps-1)
329  FreeRData(graph);
330  }
331 
332  if (mincut != graph->mincut) {
333  icopy(graph->nvtxs, bestwhere, graph->where);
334  Compute2WayNodePartitionParams(ctrl, graph);
335  }
336 
337  WCOREPOP;
338 }
339 
340 
341 /*************************************************************************/
344 /*************************************************************************/
346 {
347  idx_t i, mincut, nruns=5;
348  graph_t *cgraph;
349  idx_t *bestwhere;
350 
351  /* if the graph is small, just find a single vertex separator */
352  if (graph->nvtxs < 5000) {
353  MlevelNodeBisectionL1(ctrl, graph, niparts);
354  return;
355  }
356 
357  WCOREPUSH;
358 
359  ctrl->CoarsenTo = gk_max(100, graph->nvtxs/30);
360 
361  cgraph = CoarsenGraphNlevels(ctrl, graph, 4);
362 
363  bestwhere = iwspacemalloc(ctrl, cgraph->nvtxs);
364 
365  mincut = graph->tvwgt[0];
366  for (i=0; i<nruns; i++) {
367  MlevelNodeBisectionL1(ctrl, cgraph, 0.7*niparts);
368 
369  if (i == 0 || cgraph->mincut < mincut) {
370  mincut = cgraph->mincut;
371  if (i < nruns-1)
372  icopy(cgraph->nvtxs, cgraph->where, bestwhere);
373  }
374 
375  if (mincut == 0)
376  break;
377 
378  if (i < nruns-1)
379  FreeRData(cgraph);
380  }
381 
382  if (mincut != cgraph->mincut)
383  icopy(cgraph->nvtxs, bestwhere, cgraph->where);
384 
385  WCOREPOP;
386 
387  Refine2WayNode(ctrl, graph, cgraph);
388 
389 }
390 
391 
392 /*************************************************************************/
394 /*************************************************************************/
396 {
397  graph_t *cgraph;
398 
399  ctrl->CoarsenTo = graph->nvtxs/8;
400  if (ctrl->CoarsenTo > 100)
401  ctrl->CoarsenTo = 100;
402  else if (ctrl->CoarsenTo < 40)
403  ctrl->CoarsenTo = 40;
404 
405  cgraph = CoarsenGraph(ctrl, graph);
406 
407  niparts = gk_max(1, (cgraph->nvtxs <= ctrl->CoarsenTo ? niparts/2: niparts));
408  /*niparts = (cgraph->nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);*/
409  InitSeparator(ctrl, cgraph, niparts);
410 
411  Refine2WayNode(ctrl, graph, cgraph);
412 }
413 
414 
415 /*************************************************************************/
421 /*************************************************************************/
422 void SplitGraphOrder(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph,
423  graph_t **r_rgraph)
424 {
425  idx_t i, ii, j, k, l, istart, iend, mypart, nvtxs, snvtxs[3], snedges[3];
426  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *label, *where, *bndptr, *bndind;
427  idx_t *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *slabel[2];
428  idx_t *rename;
429  idx_t *auxadjncy;
430  graph_t *lgraph, *rgraph;
431 
432  WCOREPUSH;
433 
435 
436  nvtxs = graph->nvtxs;
437  xadj = graph->xadj;
438  vwgt = graph->vwgt;
439  adjncy = graph->adjncy;
440  adjwgt = graph->adjwgt;
441  label = graph->label;
442  where = graph->where;
443  bndptr = graph->bndptr;
444  bndind = graph->bndind;
445  ASSERT(bndptr != NULL);
446 
447  rename = iwspacemalloc(ctrl, nvtxs);
448 
449  snvtxs[0] = snvtxs[1] = snvtxs[2] = snedges[0] = snedges[1] = snedges[2] = 0;
450  for (i=0; i<nvtxs; i++) {
451  k = where[i];
452  rename[i] = snvtxs[k]++;
453  snedges[k] += xadj[i+1]-xadj[i];
454  }
455 
456  lgraph = SetupSplitGraph(graph, snvtxs[0], snedges[0]);
457  sxadj[0] = lgraph->xadj;
458  svwgt[0] = lgraph->vwgt;
459  sadjncy[0] = lgraph->adjncy;
460  sadjwgt[0] = lgraph->adjwgt;
461  slabel[0] = lgraph->label;
462 
463  rgraph = SetupSplitGraph(graph, snvtxs[1], snedges[1]);
464  sxadj[1] = rgraph->xadj;
465  svwgt[1] = rgraph->vwgt;
466  sadjncy[1] = rgraph->adjncy;
467  sadjwgt[1] = rgraph->adjwgt;
468  slabel[1] = rgraph->label;
469 
470  /* Go and use bndptr to also mark the boundary nodes in the two partitions */
471  for (ii=0; ii<graph->nbnd; ii++) {
472  i = bndind[ii];
473  for (j=xadj[i]; j<xadj[i+1]; j++)
474  bndptr[adjncy[j]] = 1;
475  }
476 
477  snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
478  sxadj[0][0] = sxadj[1][0] = 0;
479  for (i=0; i<nvtxs; i++) {
480  if ((mypart = where[i]) == 2)
481  continue;
482 
483  istart = xadj[i];
484  iend = xadj[i+1];
485  if (bndptr[i] == -1) { /* This is an interior vertex */
486  auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
487  for(j=istart; j<iend; j++)
488  auxadjncy[j] = adjncy[j];
489  snedges[mypart] += iend-istart;
490  }
491  else {
492  auxadjncy = sadjncy[mypart];
493  l = snedges[mypart];
494  for (j=istart; j<iend; j++) {
495  k = adjncy[j];
496  if (where[k] == mypart)
497  auxadjncy[l++] = k;
498  }
499  snedges[mypart] = l;
500  }
501 
502  svwgt[mypart][snvtxs[mypart]] = vwgt[i];
503  slabel[mypart][snvtxs[mypart]] = label[i];
504  sxadj[mypart][++snvtxs[mypart]] = snedges[mypart];
505  }
506 
507  for (mypart=0; mypart<2; mypart++) {
508  iend = snedges[mypart];
509  iset(iend, 1, sadjwgt[mypart]);
510 
511  auxadjncy = sadjncy[mypart];
512  for (i=0; i<iend; i++)
513  auxadjncy[i] = rename[auxadjncy[i]];
514  }
515 
516  lgraph->nvtxs = snvtxs[0];
517  lgraph->nedges = snedges[0];
518  rgraph->nvtxs = snvtxs[1];
519  rgraph->nedges = snedges[1];
520 
521  SetupGraph_tvwgt(lgraph);
522  SetupGraph_tvwgt(rgraph);
523 
525 
526  *r_lgraph = lgraph;
527  *r_rgraph = rgraph;
528 
529  WCOREPOP;
530 }
531 
532 
533 /*************************************************************************/
551 /*************************************************************************/
553  idx_t *cptr, idx_t *cind)
554 {
555  idx_t i, ii, iii, j, k, l, istart, iend, mypart, nvtxs, snvtxs, snedges;
556  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *label, *where, *bndptr, *bndind;
557  idx_t *sxadj, *svwgt, *sadjncy, *sadjwgt, *slabel;
558  idx_t *rename;
559  idx_t *auxadjncy;
560  graph_t **sgraphs;
561 
562  WCOREPUSH;
563 
565 
566  nvtxs = graph->nvtxs;
567  xadj = graph->xadj;
568  vwgt = graph->vwgt;
569  adjncy = graph->adjncy;
570  adjwgt = graph->adjwgt;
571  label = graph->label;
572  where = graph->where;
573  bndptr = graph->bndptr;
574  bndind = graph->bndind;
575  ASSERT(bndptr != NULL);
576 
577  /* Go and use bndptr to also mark the boundary nodes in the two partitions */
578  for (ii=0; ii<graph->nbnd; ii++) {
579  i = bndind[ii];
580  for (j=xadj[i]; j<xadj[i+1]; j++)
581  bndptr[adjncy[j]] = 1;
582  }
583 
584  rename = iwspacemalloc(ctrl, nvtxs);
585 
586  sgraphs = (graph_t **)gk_malloc(sizeof(graph_t *)*ncmps, "SplitGraphOrderCC: sgraphs");
587 
588  /* Go and split the graph a component at a time */
589  for (iii=0; iii<ncmps; iii++) {
590  irandArrayPermute(cptr[iii+1]-cptr[iii], cind+cptr[iii], cptr[iii+1]-cptr[iii], 0);
591  snvtxs = snedges = 0;
592  for (j=cptr[iii]; j<cptr[iii+1]; j++) {
593  i = cind[j];
594  rename[i] = snvtxs++;
595  snedges += xadj[i+1]-xadj[i];
596  }
597 
598  sgraphs[iii] = SetupSplitGraph(graph, snvtxs, snedges);
599 
600  sxadj = sgraphs[iii]->xadj;
601  svwgt = sgraphs[iii]->vwgt;
602  sadjncy = sgraphs[iii]->adjncy;
603  sadjwgt = sgraphs[iii]->adjwgt;
604  slabel = sgraphs[iii]->label;
605 
606  snvtxs = snedges = sxadj[0] = 0;
607  for (ii=cptr[iii]; ii<cptr[iii+1]; ii++) {
608  i = cind[ii];
609 
610  istart = xadj[i];
611  iend = xadj[i+1];
612  if (bndptr[i] == -1) { /* This is an interior vertex */
613  auxadjncy = sadjncy + snedges - istart;
614  for(j=istart; j<iend; j++)
615  auxadjncy[j] = adjncy[j];
616  snedges += iend-istart;
617  }
618  else {
619  l = snedges;
620  for (j=istart; j<iend; j++) {
621  k = adjncy[j];
622  if (where[k] != 2)
623  sadjncy[l++] = k;
624  }
625  snedges = l;
626  }
627 
628  svwgt[snvtxs] = vwgt[i];
629  slabel[snvtxs] = label[i];
630  sxadj[++snvtxs] = snedges;
631  }
632 
633  iset(snedges, 1, sadjwgt);
634  for (i=0; i<snedges; i++)
635  sadjncy[i] = rename[sadjncy[i]];
636 
637  sgraphs[iii]->nvtxs = snvtxs;
638  sgraphs[iii]->nedges = snedges;
639 
640  SetupGraph_tvwgt(sgraphs[iii]);
641  }
642 
644 
645  WCOREPOP;
646 
647  return sgraphs;
648 }
649 
650 
651 /*************************************************************************/
654 /*************************************************************************/
655 void MMDOrder(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
656 {
657  idx_t i, j, k, nvtxs, nofsub, firstvtx;
658  idx_t *xadj, *adjncy, *label;
659  idx_t *perm, *iperm, *head, *qsize, *list, *marker;
660 
661  WCOREPUSH;
662 
663  nvtxs = graph->nvtxs;
664  xadj = graph->xadj;
665  adjncy = graph->adjncy;
666 
667  /* Relabel the vertices so that it starts from 1 */
668  k = xadj[nvtxs];
669  for (i=0; i<k; i++)
670  adjncy[i]++;
671  for (i=0; i<nvtxs+1; i++)
672  xadj[i]++;
673 
674  perm = iwspacemalloc(ctrl, nvtxs+5);
675  iperm = iwspacemalloc(ctrl, nvtxs+5);
676  head = iwspacemalloc(ctrl, nvtxs+5);
677  qsize = iwspacemalloc(ctrl, nvtxs+5);
678  list = iwspacemalloc(ctrl, nvtxs+5);
679  marker = iwspacemalloc(ctrl, nvtxs+5);
680 
681  genmmd(nvtxs, xadj, adjncy, iperm, perm, 1, head, qsize, list, marker, IDX_MAX, &nofsub);
682 
683  label = graph->label;
684  firstvtx = lastvtx-nvtxs;
685  for (i=0; i<nvtxs; i++)
686  order[label[i]] = firstvtx+iperm[i]-1;
687 
688  /* Relabel the vertices so that it starts from 0 */
689  for (i=0; i<nvtxs+1; i++)
690  xadj[i]--;
691  k = xadj[nvtxs];
692  for (i=0; i<k; i++)
693  adjncy[i]--;
694 
695  WCOREPOP;
696 }
697 
698 
699 
700 
701 
idx_t idx_t idx_t idx_t * vwgt
idx_t * bndind
int gk_siguntrap()
Definition: error.c:116
#define SetupSplitGraph
Definition: rename.h:94
double TotalTmr
#define Compute2WayNodePartitionParams
Definition: rename.h:229
#define iwspacemalloc
Definition: rename.h:256
graph_t ** SplitGraphOrderCC(ctrl_t *ctrl, graph_t *graph, idx_t ncmps, idx_t *cptr, idx_t *cind)
Definition: ometis.c:552
#define genmmd
Definition: rename.h:176
#define gk_startcputimer(tmr)
Definition: gk_macros.h:33
#define SetupGraph
Definition: rename.h:90
graph_t * CoarsenGraphNlevels(ctrl_t *ctrl, graph_t *graph, idx_t nlevels)
Definition: coarsen.c:85
#define irandArrayPermute
Definition: gklib_rename.h:62
idx_t * xadj
#define imalloc
Definition: gklib_rename.h:42
void MlevelNestedDissection(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
Definition: ometis.c:183
#define gk_stopcputimer(tmr)
Definition: gk_macros.h:34
idx_t * pwgts
idx_t * adjwgt
#define FreeGraph
Definition: rename.h:98
#define metis_rcode
Definition: rename.h:247
idx_t * bndptr
void MlevelNodeBisectionL1(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
Definition: ometis.c:395
idx_t idx_t * xadj
idx_t * where
idx_t compress
double SplitTmr
#define WCOREPUSH
idx_t nvtxs
idx_t idx_t idx_t idx_t idx_t idx_t * iperm
mdbglvl_et dbglvl
#define CoarsenGraph
Definition: rename.h:35
NonlinearFactorGraph graph
void MlevelNodeBisectionMultiple(ctrl_t *ctrl, graph_t *graph)
Definition: ometis.c:300
#define Change2FNumberingOrder
Definition: rename.h:84
real_t cfactor
int METIS_NodeND(idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *options, idx_t *perm, idx_t *iperm)
Definition: ometis.c:43
#define PRIDX
idx_t nedges
#define PruneGraph
Definition: rename.h:50
#define ASSERT(expression)
Definition: ccolamd.c:872
#define CheckGraph
Definition: rename.h:30
idx_t ccorder
#define MMDSWITCH
Definition: libmetis/defs.h:52
#define AllocateWorkSpace
Definition: rename.h:250
static const Line3 l(Rot3(), 1, 1)
idx_t nseps
#define gk_max(a, b)
Definition: gk_macros.h:16
int32_t idx_t
#define InitTimers
Definition: rename.h:238
#define Change2CNumbering
Definition: rename.h:81
real_t pfactor
#define Refine2WayNode
Definition: rename.h:227
idx_t idx_t idx_t idx_t idx_t * perm
void MMDOrder(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
Definition: ometis.c:655
#define InitSeparator
Definition: rename.h:102
void gk_malloc_cleanup(int showstats)
Definition: memory.c:118
idx_t idx_t idx_t idx_t idx_t * numflag
#define NULL
Definition: ccolamd.c:609
#define SetupCtrl
Definition: rename.h:194
idx_t mincut
Definition: pytypes.h:1301
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
#define FindSepInducedComponents
Definition: rename.h:56
#define IDX_MAX
#define FreeCtrl
Definition: rename.h:198
#define iset
Definition: gklib_rename.h:67
#define icopy
Definition: gklib_rename.h:28
void MlevelNestedDissectionCC(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
Definition: ometis.c:236
void * gk_malloc(size_t nbytes, char *msg)
Definition: memory.c:140
void gk_free(void **ptr1,...)
Definition: memory.c:202
idx_t idx_t idx_t idx_t * where
idx_t * adjncy
EIGEN_DEVICE_FUNC SegmentReturnType head(Index n)
This is the const version of head(Index).
Definition: BlockMethods.h:919
idx_t * tvwgt
#define gk_sigcatch()
Definition: gk_macros.h:52
idx_t idx_t idx_t * adjncy
#define PrintTimers
Definition: rename.h:239
#define FreeRData
Definition: rename.h:97
idx_t CoarsenTo
#define SetupGraph_tvwgt
Definition: rename.h:92
void MlevelNodeBisectionL2(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
Definition: ometis.c:345
#define WCOREPOP
#define LARGENIPARTS
Definition: libmetis/defs.h:45
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
void SplitGraphOrder(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, graph_t **r_rgraph)
Definition: ometis.c:422
#define CompressGraph
Definition: rename.h:49
int gk_malloc_init()
Definition: memory.c:99
std::ptrdiff_t j
int gk_sigtrap()
Definition: error.c:98
idx_t numflag
idx_t * label
#define LTERM
Definition: gk_defs.h:14
idx_t * vwgt


gtsam
Author(s):
autogenerated on Sat May 8 2021 02:43:05