initpart.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * initpart.c
5  *
6  * This file contains code that performs the initial partition of the
7  * coarsest graph
8  *
9  * Started 7/23/97
10  * George
11  *
12  */
13 
14 #include "metislib.h"
15 
16 /*************************************************************************/
18 /*************************************************************************/
19 void Init2WayPartition(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
20  idx_t niparts)
21 {
22  mdbglvl_et dbglvl;
23 
24  ASSERT(graph->tvwgt[0] >= 0);
25 
26  dbglvl = ctrl->dbglvl;
27  IFSET(ctrl->dbglvl, METIS_DBG_REFINE, ctrl->dbglvl -= METIS_DBG_REFINE);
28  IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, ctrl->dbglvl -= METIS_DBG_MOVEINFO);
29 
30  IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->InitPartTmr));
31 
32  switch (ctrl->iptype) {
33  case METIS_IPTYPE_RANDOM:
34  if (graph->ncon == 1)
35  RandomBisection(ctrl, graph, ntpwgts, niparts);
36  else
37  McRandomBisection(ctrl, graph, ntpwgts, niparts);
38  break;
39 
40  case METIS_IPTYPE_GROW:
41  if (graph->nedges == 0)
42  if (graph->ncon == 1)
43  RandomBisection(ctrl, graph, ntpwgts, niparts);
44  else
45  McRandomBisection(ctrl, graph, ntpwgts, niparts);
46  else
47  if (graph->ncon == 1)
48  GrowBisection(ctrl, graph, ntpwgts, niparts);
49  else
50  McGrowBisection(ctrl, graph, ntpwgts, niparts);
51  break;
52 
53  default:
54  gk_errexit(SIGERR, "Unknown initial partition type: %d\n", ctrl->iptype);
55  }
56 
57  IFSET(ctrl->dbglvl, METIS_DBG_IPART, printf("Initial Cut: %"PRIDX"\n", graph->mincut));
58  IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->InitPartTmr));
59  ctrl->dbglvl = dbglvl;
60 
61 }
62 
63 
64 /*************************************************************************/
66 /*************************************************************************/
67 void InitSeparator(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
68 {
69  real_t ntpwgts[2] = {0.5, 0.5};
70  mdbglvl_et dbglvl;
71 
72  dbglvl = ctrl->dbglvl;
73  IFSET(ctrl->dbglvl, METIS_DBG_REFINE, ctrl->dbglvl -= METIS_DBG_REFINE);
74  IFSET(ctrl->dbglvl, METIS_DBG_MOVEINFO, ctrl->dbglvl -= METIS_DBG_MOVEINFO);
75 
76  IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->InitPartTmr));
77 
78  /* this is required for the cut-based part of the refinement */
79  Setup2WayBalMultipliers(ctrl, graph, ntpwgts);
80 
81  switch (ctrl->iptype) {
82  case METIS_IPTYPE_EDGE:
83  if (graph->nedges == 0)
84  RandomBisection(ctrl, graph, ntpwgts, niparts);
85  else
86  GrowBisection(ctrl, graph, ntpwgts, niparts);
87 
88  Compute2WayPartitionParams(ctrl, graph);
89  ConstructSeparator(ctrl, graph);
90  break;
91 
92  case METIS_IPTYPE_NODE:
93  GrowBisectionNode(ctrl, graph, ntpwgts, niparts);
94  break;
95 
96  default:
97  gk_errexit(SIGERR, "Unkown iptype of %"PRIDX"\n", ctrl->iptype);
98  }
99 
100  IFSET(ctrl->dbglvl, METIS_DBG_IPART, printf("Initial Sep: %"PRIDX"\n", graph->mincut));
101  IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->InitPartTmr));
102 
103  ctrl->dbglvl = dbglvl;
104 
105 }
106 
107 
108 /*************************************************************************/
113 /*************************************************************************/
114 void RandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
115  idx_t niparts)
116 {
117  idx_t i, ii, j, k, nvtxs, pwgts[2], zeromaxpwgt, from, me,
118  bestcut=0, icut, mincut, inbfs;
119  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where;
120  idx_t *perm, *bestwhere;
121 
122  WCOREPUSH;
123 
124  nvtxs = graph->nvtxs;
125  xadj = graph->xadj;
126  vwgt = graph->vwgt;
127  adjncy = graph->adjncy;
128  adjwgt = graph->adjwgt;
129 
130  Allocate2WayPartitionMemory(ctrl, graph);
131  where = graph->where;
132 
133  bestwhere = iwspacemalloc(ctrl, nvtxs);
134  perm = iwspacemalloc(ctrl, nvtxs);
135 
136  zeromaxpwgt = ctrl->ubfactors[0]*graph->tvwgt[0]*ntpwgts[0];
137 
138  for (inbfs=0; inbfs<niparts; inbfs++) {
139  iset(nvtxs, 1, where);
140 
141  if (inbfs > 0) {
142  irandArrayPermute(nvtxs, perm, nvtxs/2, 1);
143  pwgts[1] = graph->tvwgt[0];
144  pwgts[0] = 0;
145 
146  for (ii=0; ii<nvtxs; ii++) {
147  i = perm[ii];
148  if (pwgts[0]+vwgt[i] < zeromaxpwgt) {
149  where[i] = 0;
150  pwgts[0] += vwgt[i];
151  pwgts[1] -= vwgt[i];
152  if (pwgts[0] > zeromaxpwgt)
153  break;
154  }
155  }
156  }
157 
158  /* Do some partition refinement */
159  Compute2WayPartitionParams(ctrl, graph);
160  /* printf("IPART: %3"PRIDX" [%5"PRIDX" %5"PRIDX"] [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->nvtxs, pwgts[0], pwgts[1], graph->pwgts[0], graph->pwgts[1], graph->mincut); */
161 
162  Balance2Way(ctrl, graph, ntpwgts);
163  /* printf("BPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0], graph->pwgts[1], graph->mincut); */
164 
165  FM_2WayRefine(ctrl, graph, ntpwgts, 4);
166  /* printf("RPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0], graph->pwgts[1], graph->mincut); */
167 
168  if (inbfs==0 || bestcut > graph->mincut) {
169  bestcut = graph->mincut;
170  icopy(nvtxs, where, bestwhere);
171  if (bestcut == 0)
172  break;
173  }
174  }
175 
176  graph->mincut = bestcut;
177  icopy(nvtxs, bestwhere, where);
178 
179  WCOREPOP;
180 }
181 
182 
183 /*************************************************************************/
188 /*************************************************************************/
189 void GrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
190  idx_t niparts)
191 {
192  idx_t i, j, k, nvtxs, drain, nleft, first, last,
193  pwgts[2], oneminpwgt, onemaxpwgt,
194  from, me, bestcut=0, icut, mincut, inbfs;
195  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where;
196  idx_t *queue, *touched, *gain, *bestwhere;
197 
198  WCOREPUSH;
199 
200  nvtxs = graph->nvtxs;
201  xadj = graph->xadj;
202  vwgt = graph->vwgt;
203  adjncy = graph->adjncy;
204  adjwgt = graph->adjwgt;
205 
206  Allocate2WayPartitionMemory(ctrl, graph);
207  where = graph->where;
208 
209  bestwhere = iwspacemalloc(ctrl, nvtxs);
210  queue = iwspacemalloc(ctrl, nvtxs);
211  touched = iwspacemalloc(ctrl, nvtxs);
212 
213  onemaxpwgt = ctrl->ubfactors[0]*graph->tvwgt[0]*ntpwgts[1];
214  oneminpwgt = (1.0/ctrl->ubfactors[0])*graph->tvwgt[0]*ntpwgts[1];
215 
216  for (inbfs=0; inbfs<niparts; inbfs++) {
217  iset(nvtxs, 1, where);
218 
219  iset(nvtxs, 0, touched);
220 
221  pwgts[1] = graph->tvwgt[0];
222  pwgts[0] = 0;
223 
224 
225  queue[0] = irandInRange(nvtxs);
226  touched[queue[0]] = 1;
227  first = 0;
228  last = 1;
229  nleft = nvtxs-1;
230  drain = 0;
231 
232  /* Start the BFS from queue to get a partition */
233  for (;;) {
234  if (first == last) { /* Empty. Disconnected graph! */
235  if (nleft == 0 || drain)
236  break;
237 
238  k = irandInRange(nleft);
239  for (i=0; i<nvtxs; i++) {
240  if (touched[i] == 0) {
241  if (k == 0)
242  break;
243  else
244  k--;
245  }
246  }
247 
248  queue[0] = i;
249  touched[i] = 1;
250  first = 0;
251  last = 1;
252  nleft--;
253  }
254 
255  i = queue[first++];
256  if (pwgts[0] > 0 && pwgts[1]-vwgt[i] < oneminpwgt) {
257  drain = 1;
258  continue;
259  }
260 
261  where[i] = 0;
262  INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
263  if (pwgts[1] <= onemaxpwgt)
264  break;
265 
266  drain = 0;
267  for (j=xadj[i]; j<xadj[i+1]; j++) {
268  k = adjncy[j];
269  if (touched[k] == 0) {
270  queue[last++] = k;
271  touched[k] = 1;
272  nleft--;
273  }
274  }
275  }
276 
277  /* Check to see if we hit any bad limiting cases */
278  if (pwgts[1] == 0)
279  where[irandInRange(nvtxs)] = 1;
280  if (pwgts[0] == 0)
281  where[irandInRange(nvtxs)] = 0;
282 
283  /*************************************************************
284  * Do some partition refinement
285  **************************************************************/
286  Compute2WayPartitionParams(ctrl, graph);
287  /*
288  printf("IPART: %3"PRIDX" [%5"PRIDX" %5"PRIDX"] [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n",
289  graph->nvtxs, pwgts[0], pwgts[1], graph->pwgts[0], graph->pwgts[1], graph->mincut);
290  */
291 
292  Balance2Way(ctrl, graph, ntpwgts);
293  /*
294  printf("BPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0],
295  graph->pwgts[1], graph->mincut);
296  */
297 
298  FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
299  /*
300  printf("RPART: [%5"PRIDX" %5"PRIDX"] %5"PRIDX"\n", graph->pwgts[0],
301  graph->pwgts[1], graph->mincut);
302  */
303 
304  if (inbfs == 0 || bestcut > graph->mincut) {
305  bestcut = graph->mincut;
306  icopy(nvtxs, where, bestwhere);
307  if (bestcut == 0)
308  break;
309  }
310  }
311 
312  graph->mincut = bestcut;
313  icopy(nvtxs, bestwhere, where);
314 
315  WCOREPOP;
316 }
317 
318 
319 /*************************************************************************/
324 /**************************************************************************/
325 void McRandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
326  idx_t niparts)
327 {
328  idx_t i, ii, j, k, nvtxs, ncon, from, bestcut=0, mincut, inbfs, qnum;
329  idx_t *bestwhere, *where, *perm, *counts;
330  idx_t *vwgt;
331 
332  WCOREPUSH;
333 
334  nvtxs = graph->nvtxs;
335  ncon = graph->ncon;
336  vwgt = graph->vwgt;
337 
338  Allocate2WayPartitionMemory(ctrl, graph);
339  where = graph->where;
340 
341  bestwhere = iwspacemalloc(ctrl, nvtxs);
342  perm = iwspacemalloc(ctrl, nvtxs);
343  counts = iwspacemalloc(ctrl, ncon);
344 
345  for (inbfs=0; inbfs<2*niparts; inbfs++) {
346  irandArrayPermute(nvtxs, perm, nvtxs/2, 1);
347  iset(ncon, 0, counts);
348 
349  /* partition by spliting the queues randomly */
350  for (ii=0; ii<nvtxs; ii++) {
351  i = perm[ii];
352  qnum = iargmax(ncon, vwgt+i*ncon);
353  where[i] = (counts[qnum]++)%2;
354  }
355 
356  Compute2WayPartitionParams(ctrl, graph);
357 
358  FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
359  Balance2Way(ctrl, graph, ntpwgts);
360  FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
361  Balance2Way(ctrl, graph, ntpwgts);
362  FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
363 
364  if (inbfs == 0 || bestcut >= graph->mincut) {
365  bestcut = graph->mincut;
366  icopy(nvtxs, where, bestwhere);
367  if (bestcut == 0)
368  break;
369  }
370  }
371 
372  graph->mincut = bestcut;
373  icopy(nvtxs, bestwhere, where);
374 
375  WCOREPOP;
376 }
377 
378 
379 /*************************************************************************/
384 /*************************************************************************/
385 void McGrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
386  idx_t niparts)
387 {
388  idx_t i, j, k, nvtxs, ncon, from, bestcut=0, mincut, inbfs;
389  idx_t *bestwhere, *where;
390 
391  WCOREPUSH;
392 
393  nvtxs = graph->nvtxs;
394 
395  Allocate2WayPartitionMemory(ctrl, graph);
396  where = graph->where;
397 
398  bestwhere = iwspacemalloc(ctrl, nvtxs);
399 
400  for (inbfs=0; inbfs<2*niparts; inbfs++) {
401  iset(nvtxs, 1, where);
402  where[irandInRange(nvtxs)] = 0;
403 
404  Compute2WayPartitionParams(ctrl, graph);
405 
406  Balance2Way(ctrl, graph, ntpwgts);
407  FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
408  Balance2Way(ctrl, graph, ntpwgts);
409  FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
410 
411  if (inbfs == 0 || bestcut >= graph->mincut) {
412  bestcut = graph->mincut;
413  icopy(nvtxs, where, bestwhere);
414  if (bestcut == 0)
415  break;
416  }
417  }
418 
419  graph->mincut = bestcut;
420  icopy(nvtxs, bestwhere, where);
421 
422  WCOREPOP;
423 }
424 
425 
426 /*************************************************************************/
427 /* This function takes a graph and produces a tri-section into left, right,
428  and separator using a region growing algorithm. The resulting separator
429  is refined using node FM.
430  The resulting partition is returned in graph->where.
431 */
432 /**************************************************************************/
433 void GrowBisectionNode(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
434  idx_t niparts)
435 {
436  idx_t i, j, k, nvtxs, drain, nleft, first, last, pwgts[2], oneminpwgt,
437  onemaxpwgt, from, me, bestcut=0, icut, mincut, inbfs;
438  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *where, *bndind;
439  idx_t *queue, *touched, *gain, *bestwhere;
440 
441  WCOREPUSH;
442 
443  nvtxs = graph->nvtxs;
444  xadj = graph->xadj;
445  vwgt = graph->vwgt;
446  adjncy = graph->adjncy;
447  adjwgt = graph->adjwgt;
448 
449  bestwhere = iwspacemalloc(ctrl, nvtxs);
450  queue = iwspacemalloc(ctrl, nvtxs);
451  touched = iwspacemalloc(ctrl, nvtxs);
452 
453  onemaxpwgt = ctrl->ubfactors[0]*graph->tvwgt[0]*0.5;
454  oneminpwgt = (1.0/ctrl->ubfactors[0])*graph->tvwgt[0]*0.5;
455 
456 
457  /* Allocate refinement memory. Allocate sufficient memory for both edge and node */
458  graph->pwgts = imalloc(3, "GrowBisectionNode: pwgts");
459  graph->where = imalloc(nvtxs, "GrowBisectionNode: where");
460  graph->bndptr = imalloc(nvtxs, "GrowBisectionNode: bndptr");
461  graph->bndind = imalloc(nvtxs, "GrowBisectionNode: bndind");
462  graph->id = imalloc(nvtxs, "GrowBisectionNode: id");
463  graph->ed = imalloc(nvtxs, "GrowBisectionNode: ed");
464  graph->nrinfo = (nrinfo_t *)gk_malloc(nvtxs*sizeof(nrinfo_t), "GrowBisectionNode: nrinfo");
465 
466  where = graph->where;
467  bndind = graph->bndind;
468 
469  for (inbfs=0; inbfs<niparts; inbfs++) {
470  iset(nvtxs, 1, where);
471  iset(nvtxs, 0, touched);
472 
473  pwgts[1] = graph->tvwgt[0];
474  pwgts[0] = 0;
475 
476  queue[0] = irandInRange(nvtxs);
477  touched[queue[0]] = 1;
478  first = 0; last = 1;
479  nleft = nvtxs-1;
480  drain = 0;
481 
482  /* Start the BFS from queue to get a partition */
483  for (;;) {
484  if (first == last) { /* Empty. Disconnected graph! */
485  if (nleft == 0 || drain)
486  break;
487 
488  k = irandInRange(nleft);
489  for (i=0; i<nvtxs; i++) { /* select the kth untouched vertex */
490  if (touched[i] == 0) {
491  if (k == 0)
492  break;
493  else
494  k--;
495  }
496  }
497 
498  queue[0] = i;
499  touched[i] = 1;
500  first = 0;
501  last = 1;
502  nleft--;
503  }
504 
505  i = queue[first++];
506  if (pwgts[1]-vwgt[i] < oneminpwgt) {
507  drain = 1;
508  continue;
509  }
510 
511  where[i] = 0;
512  INC_DEC(pwgts[0], pwgts[1], vwgt[i]);
513  if (pwgts[1] <= onemaxpwgt)
514  break;
515 
516  drain = 0;
517  for (j=xadj[i]; j<xadj[i+1]; j++) {
518  k = adjncy[j];
519  if (touched[k] == 0) {
520  queue[last++] = k;
521  touched[k] = 1;
522  nleft--;
523  }
524  }
525  }
526 
527  /*************************************************************
528  * Do some partition refinement
529  **************************************************************/
530  Compute2WayPartitionParams(ctrl, graph);
531  Balance2Way(ctrl, graph, ntpwgts);
532  FM_2WayRefine(ctrl, graph, ntpwgts, 4);
533 
534  /* Construct and refine the vertex separator */
535  for (i=0; i<graph->nbnd; i++) {
536  j = bndind[i];
537  if (xadj[j+1]-xadj[j] > 0) /* ignore islands */
538  where[j] = 2;
539  }
540 
541  Compute2WayNodePartitionParams(ctrl, graph);
542  FM_2WayNodeRefine2Sided(ctrl, graph, 1);
543  FM_2WayNodeRefine1Sided(ctrl, graph, 4);
544 
545  /*
546  printf("ISep: [%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"] %"PRIDX"\n",
547  inbfs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2], bestcut);
548  */
549 
550  if (inbfs == 0 || bestcut > graph->mincut) {
551  bestcut = graph->mincut;
552  icopy(nvtxs, where, bestwhere);
553  }
554  }
555 
556  graph->mincut = bestcut;
557  icopy(nvtxs, bestwhere, where);
558 
559  WCOREPOP;
560 }
561 
562 
563 /*************************************************************************/
564 /* This function takes a graph and produces a tri-section into left, right,
565  and separator using a region growing algorithm. The resulting separator
566  is refined using node FM.
567  The resulting partition is returned in graph->where.
568 */
569 /**************************************************************************/
570 void GrowBisectionNode2(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts,
571  idx_t niparts)
572 {
573  idx_t i, j, k, nvtxs, bestcut=0, mincut, inbfs;
574  idx_t *xadj, *where, *bndind, *bestwhere;
575 
576  WCOREPUSH;
577 
578  nvtxs = graph->nvtxs;
579  xadj = graph->xadj;
580 
581  /* Allocate refinement memory. Allocate sufficient memory for both edge and node */
582  graph->pwgts = imalloc(3, "GrowBisectionNode: pwgts");
583  graph->where = imalloc(nvtxs, "GrowBisectionNode: where");
584  graph->bndptr = imalloc(nvtxs, "GrowBisectionNode: bndptr");
585  graph->bndind = imalloc(nvtxs, "GrowBisectionNode: bndind");
586  graph->id = imalloc(nvtxs, "GrowBisectionNode: id");
587  graph->ed = imalloc(nvtxs, "GrowBisectionNode: ed");
588  graph->nrinfo = (nrinfo_t *)gk_malloc(nvtxs*sizeof(nrinfo_t), "GrowBisectionNode: nrinfo");
589 
590  bestwhere = iwspacemalloc(ctrl, nvtxs);
591 
592  where = graph->where;
593  bndind = graph->bndind;
594 
595  for (inbfs=0; inbfs<niparts; inbfs++) {
596  iset(nvtxs, 1, where);
597  if (inbfs > 0)
598  where[irandInRange(nvtxs)] = 0;
599 
600  Compute2WayPartitionParams(ctrl, graph);
601  General2WayBalance(ctrl, graph, ntpwgts);
602  FM_2WayRefine(ctrl, graph, ntpwgts, ctrl->niter);
603 
604  /* Construct and refine the vertex separator */
605  for (i=0; i<graph->nbnd; i++) {
606  j = bndind[i];
607  if (xadj[j+1]-xadj[j] > 0) /* ignore islands */
608  where[j] = 2;
609  }
610 
611  Compute2WayNodePartitionParams(ctrl, graph);
612  FM_2WayNodeRefine2Sided(ctrl, graph, 4);
613 
614  /*
615  printf("ISep: [%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"] %"PRIDX"\n",
616  inbfs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2], bestcut);
617  */
618 
619  if (inbfs == 0 || bestcut > graph->mincut) {
620  bestcut = graph->mincut;
621  icopy(nvtxs, where, bestwhere);
622  }
623  }
624 
625  graph->mincut = bestcut;
626  icopy(nvtxs, bestwhere, where);
627 
628  WCOREPOP;
629 }
630 
FM_2WayNodeRefine2Sided
#define FM_2WayNodeRefine2Sided
Definition: rename.h:222
ctrl_t
Definition: libmetis/struct.h:139
vwgt
idx_t idx_t idx_t idx_t * vwgt
Definition: include/metis.h:197
graph_t::bndind
idx_t * bndind
Definition: libmetis/struct.h:107
graph_t::nbnd
idx_t nbnd
Definition: libmetis/struct.h:106
Compute2WayNodePartitionParams
#define Compute2WayNodePartitionParams
Definition: rename.h:229
Balance2Way
#define Balance2Way
Definition: rename.h:21
iwspacemalloc
#define iwspacemalloc
Definition: rename.h:256
gk_startcputimer
#define gk_startcputimer(tmr)
Definition: gk_macros.h:33
irandArrayPermute
#define irandArrayPermute
Definition: gklib_rename.h:62
graph_t::xadj
idx_t * xadj
Definition: libmetis/struct.h:85
mdbglvl_et
mdbglvl_et
Definition: include/metis.h:339
imalloc
#define imalloc
Definition: gklib_rename.h:42
for
for(size_t i=1;i< poses.size();++i)
Definition: doc/Code/VisualISAMExample.cpp:7
gk_stopcputimer
#define gk_stopcputimer(tmr)
Definition: gk_macros.h:34
graph_t::pwgts
idx_t * pwgts
Definition: libmetis/struct.h:105
graph_t::adjwgt
idx_t * adjwgt
Definition: libmetis/struct.h:89
graph_t::bndptr
idx_t * bndptr
Definition: libmetis/struct.h:107
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
graph_t::where
idx_t * where
Definition: libmetis/struct.h:105
McRandomBisection
void McRandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
Definition: initpart.c:325
WCOREPUSH
#define WCOREPUSH
Definition: metis/libmetis/macros.h:38
graph_t::nvtxs
idx_t nvtxs
Definition: libmetis/struct.h:83
graph_t::id
idx_t * id
Definition: libmetis/struct.h:110
iargmax
#define iargmax
Definition: gklib_rename.h:23
Compute2WayPartitionParams
#define Compute2WayPartitionParams
Definition: rename.h:214
gk_errexit
void gk_errexit(int signum, char *f_str,...)
Definition: error.c:77
ctrl_t::dbglvl
mdbglvl_et dbglvl
Definition: libmetis/struct.h:142
Eigen::internal::first
EIGEN_CONSTEXPR Index first(const T &x) EIGEN_NOEXCEPT
Definition: IndexedViewHelper.h:81
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
GrowBisectionNode
void GrowBisectionNode(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
Definition: initpart.c:433
Init2WayPartition
void Init2WayPartition(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
Definition: initpart.c:19
ctrl_t::InitPartTmr
double InitPartTmr
Definition: libmetis/struct.h:176
graph_t::nrinfo
nrinfo_t * nrinfo
Definition: libmetis/struct.h:117
FM_2WayRefine
#define FM_2WayRefine
Definition: rename.h:74
Eigen::last
static const symbolic::SymbolExpr< internal::symbolic_last_tag > last
Definition: IndexedViewHelper.h:38
FM_2WayNodeRefine1Sided
#define FM_2WayNodeRefine1Sided
Definition: rename.h:223
graph_t::ed
idx_t * ed
Definition: libmetis/struct.h:110
nrinfo_t
Definition: libmetis/struct.h:74
irandInRange
#define irandInRange
Definition: gklib_rename.h:64
PRIDX
#define PRIDX
Definition: include/metis.h:107
graph_t::nedges
idx_t nedges
Definition: libmetis/struct.h:83
ctrl_t::niter
idx_t niter
Definition: libmetis/struct.h:158
ASSERT
#define ASSERT(expression)
Definition: ccolamd.c:872
GrowBisection
void GrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
Definition: initpart.c:189
SIGERR
#define SIGERR
Definition: gk_defs.h:38
ConstructSeparator
#define ConstructSeparator
Definition: rename.h:218
idx_t
int32_t idx_t
Definition: include/metis.h:101
General2WayBalance
#define General2WayBalance
Definition: rename.h:23
perm
idx_t idx_t idx_t idx_t idx_t * perm
Definition: include/metis.h:222
graph_t::ncon
idx_t ncon
Definition: libmetis/struct.h:84
real_t
float real_t
Definition: include/metis.h:132
ncon
idx_t * ncon
Definition: include/metis.h:197
graph_t::mincut
idx_t mincut
Definition: libmetis/struct.h:104
adjwgt
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
Definition: include/metis.h:197
INC_DEC
#define INC_DEC(a, b, val)
Definition: gk_macros.h:20
GrowBisectionNode2
void GrowBisectionNode2(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
Definition: initpart.c:570
RandomBisection
void RandomBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
Definition: initpart.c:114
ctrl_t::ubfactors
real_t * ubfactors
Definition: libmetis/struct.h:167
iset
#define iset
Definition: gklib_rename.h:67
icopy
#define icopy
Definition: gklib_rename.h:28
gk_malloc
void * gk_malloc(size_t nbytes, char *msg)
Definition: memory.c:140
where
idx_t idx_t idx_t idx_t * where
Definition: include/metis.h:239
graph_t::adjncy
idx_t * adjncy
Definition: libmetis/struct.h:88
McGrowBisection
void McGrowBisection(ctrl_t *ctrl, graph_t *graph, real_t *ntpwgts, idx_t niparts)
Definition: initpart.c:385
graph_t::tvwgt
idx_t * tvwgt
Definition: libmetis/struct.h:91
Setup2WayBalMultipliers
#define Setup2WayBalMultipliers
Definition: rename.h:196
adjncy
idx_t idx_t idx_t * adjncy
Definition: include/metis.h:197
InitSeparator
void InitSeparator(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
Definition: initpart.c:67
Allocate2WayPartitionMemory
#define Allocate2WayPartitionMemory
Definition: rename.h:213
graph_t
Definition: libmetis/struct.h:82
WCOREPOP
#define WCOREPOP
Definition: metis/libmetis/macros.h:39
IFSET
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
ctrl_t::iptype
miptype_et iptype
Definition: libmetis/struct.h:144
graph_t::vwgt
idx_t * vwgt
Definition: libmetis/struct.h:86

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