contig.c
Go to the documentation of this file.
1 
11 #include "metislib.h"
12 
13 
14 /*************************************************************************/
31 /*************************************************************************/
33  idx_t *cptr, idx_t *cind)
34 {
35  idx_t i, ii, j, jj, k, me=0, nvtxs, first, last, nleft, ncmps;
36  idx_t *xadj, *adjncy;
37  idx_t *touched, *perm, *todo;
38  idx_t mustfree_ccsr=0, mustfree_where=0;
39 
40  nvtxs = graph->nvtxs;
41  xadj = graph->xadj;
42  adjncy = graph->adjncy;
43 
44  /* Deal with NULL supplied cptr/cind vectors */
45  if (cptr == NULL) {
46  cptr = imalloc(nvtxs+1, "FindPartitionInducedComponents: cptr");
47  cind = imalloc(nvtxs, "FindPartitionInducedComponents: cind");
48  mustfree_ccsr = 1;
49  }
50 
51  /* Deal with NULL supplied where vector */
52  if (where == NULL) {
53  where = ismalloc(nvtxs, 0, "FindPartitionInducedComponents: where");
54  mustfree_where = 1;
55  }
56 
57  /* Allocate memory required for the BFS traversal */
58  perm = iincset(nvtxs, 0, imalloc(nvtxs, "FindPartitionInducedComponents: perm"));
59  todo = iincset(nvtxs, 0, imalloc(nvtxs, "FindPartitionInducedComponents: todo"));
60  touched = ismalloc(nvtxs, 0, "FindPartitionInducedComponents: touched");
61 
62 
63  /* Find the connected componends induced by the partition */
64  ncmps = -1;
65  first = last = 0;
66  nleft = nvtxs;
67  while (nleft > 0) {
68  if (first == last) { /* Find another starting vertex */
69  cptr[++ncmps] = first;
70  ASSERT(touched[todo[0]] == 0);
71  i = todo[0];
72  cind[last++] = i;
73  touched[i] = 1;
74  me = where[i];
75  }
76 
77  i = cind[first++];
78  k = perm[i];
79  j = todo[k] = todo[--nleft];
80  perm[j] = k;
81 
82  for (j=xadj[i]; j<xadj[i+1]; j++) {
83  k = adjncy[j];
84  if (where[k] == me && !touched[k]) {
85  cind[last++] = k;
86  touched[k] = 1;
87  }
88  }
89  }
90  cptr[++ncmps] = first;
91 
92  if (mustfree_ccsr)
93  gk_free((void **)&cptr, &cind, LTERM);
94  if (mustfree_where)
95  gk_free((void **)&where, LTERM);
96 
97  gk_free((void **)&perm, &todo, &touched, LTERM);
98 
99  return ncmps;
100 }
101 
102 
103 /*************************************************************************/
114 /*************************************************************************/
115 void ComputeBFSOrdering(ctrl_t *ctrl, graph_t *graph, idx_t *bfsperm)
116 {
117  idx_t i, j, k, nvtxs, first, last;
118  idx_t *xadj, *adjncy, *perm;
119 
120  WCOREPUSH;
121 
122  nvtxs = graph->nvtxs;
123  xadj = graph->xadj;
124  adjncy = graph->adjncy;
125 
126  /* Allocate memory required for the BFS traversal */
127  perm = iincset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
128 
129  iincset(nvtxs, 0, bfsperm); /* this array will also store the vertices
130  still to be processed */
131 
132  /* Find the connected componends induced by the partition */
133  first = last = 0;
134  while (first < nvtxs) {
135  if (first == last) { /* Find another starting vertex */
136  k = bfsperm[last];
137  ASSERT(perm[k] != -1);
138  perm[k] = -1; /* mark node as being visited */
139  last++;
140  }
141 
142  i = bfsperm[first++];
143  for (j=xadj[i]; j<xadj[i+1]; j++) {
144  k = adjncy[j];
145  /* if a node has been already been visited, its perm[] will be -1 */
146  if (perm[k] != -1) {
147  /* perm[k] is the location within bfsperm of where k resides;
148  put in that location bfsperm[last] that we are about to
149  overwrite and update perm[bfsperm[last]] to reflect that. */
150  bfsperm[perm[k]] = bfsperm[last];
151  perm[bfsperm[last]] = perm[k];
152 
153  bfsperm[last++] = k; /* put node at the end of the "queue" */
154  perm[k] = -1; /* mark node as being visited */
155  }
156  }
157  }
158 
159  WCOREPOP;
160 }
161 
162 
163 /*************************************************************************/
166 /**************************************************************************/
168 {
169  idx_t ncmps;
170 
171  ncmps = FindPartitionInducedComponents(graph, NULL, NULL, NULL);
172 
173  if (ncmps != 1 && report)
174  printf("The graph is not connected. It has %"PRIDX" connected components.\n", ncmps);
175 
176  return (ncmps == 1);
177 }
178 
179 
180 /*************************************************************************/
183 /*************************************************************************/
185 {
186  idx_t i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
187  idx_t *xadj, *adjncy, *where, *touched, *queue;
188  idx_t *cptr;
189 
190  nvtxs = graph->nvtxs;
191  xadj = graph->xadj;
192  adjncy = graph->adjncy;
193  where = graph->where;
194 
195  touched = ismalloc(nvtxs, 0, "IsConnected: touched");
196  queue = imalloc(nvtxs, "IsConnected: queue");
197  cptr = imalloc(nvtxs+1, "IsConnected: cptr");
198 
199  nleft = 0;
200  for (i=0; i<nvtxs; i++) {
201  if (where[i] == pid)
202  nleft++;
203  }
204 
205  for (i=0; i<nvtxs; i++) {
206  if (where[i] == pid)
207  break;
208  }
209 
210  touched[i] = 1;
211  queue[0] = i;
212  first = 0; last = 1;
213 
214  cptr[0] = 0; /* This actually points to queue */
215  ncmps = 0;
216  while (first != nleft) {
217  if (first == last) { /* Find another starting vertex */
218  cptr[++ncmps] = first;
219  for (i=0; i<nvtxs; i++) {
220  if (where[i] == pid && !touched[i])
221  break;
222  }
223  queue[last++] = i;
224  touched[i] = 1;
225  }
226 
227  i = queue[first++];
228  for (j=xadj[i]; j<xadj[i+1]; j++) {
229  k = adjncy[j];
230  if (where[k] == pid && !touched[k]) {
231  queue[last++] = k;
232  touched[k] = 1;
233  }
234  }
235  }
236  cptr[++ncmps] = first;
237 
238  if (ncmps > 1 && report) {
239  printf("The graph has %"PRIDX" connected components in partition %"PRIDX":\t", ncmps, pid);
240  for (i=0; i<ncmps; i++) {
241  wgt = 0;
242  for (j=cptr[i]; j<cptr[i+1]; j++)
243  wgt += graph->vwgt[queue[j]];
244  printf("[%5"PRIDX" %5"PRIDX"] ", cptr[i+1]-cptr[i], wgt);
245  /*
246  if (cptr[i+1]-cptr[i] == 1)
247  printf("[%"PRIDX" %"PRIDX"] ", queue[cptr[i]], xadj[queue[cptr[i]]+1]-xadj[queue[cptr[i]]]);
248  */
249  }
250  printf("\n");
251  }
252 
253  gk_free((void **)&touched, &queue, &cptr, LTERM);
254 
255  return (ncmps == 1 ? 1 : 0);
256 }
257 
258 
259 /*************************************************************************/
266 /**************************************************************************/
268  idx_t *cind)
269 {
270  idx_t i, j, k, nvtxs, first, last, nleft, ncmps, wgt;
271  idx_t *xadj, *adjncy, *where, *touched, *queue;
272 
273  nvtxs = graph->nvtxs;
274  xadj = graph->xadj;
275  adjncy = graph->adjncy;
276  where = graph->where;
277 
278  touched = ismalloc(nvtxs, 0, "IsConnected: queue");
279 
280  for (i=0; i<graph->nbnd; i++)
281  touched[graph->bndind[i]] = 1;
282 
283  queue = cind;
284 
285  nleft = 0;
286  for (i=0; i<nvtxs; i++) {
287  if (where[i] != 2)
288  nleft++;
289  }
290 
291  for (i=0; i<nvtxs; i++) {
292  if (where[i] != 2)
293  break;
294  }
295 
296  touched[i] = 1;
297  queue[0] = i;
298  first = 0;
299  last = 1;
300  cptr[0] = 0; /* This actually points to queue */
301  ncmps = 0;
302 
303  while (first != nleft) {
304  if (first == last) { /* Find another starting vertex */
305  cptr[++ncmps] = first;
306  for (i=0; i<nvtxs; i++) {
307  if (!touched[i])
308  break;
309  }
310  queue[last++] = i;
311  touched[i] = 1;
312  }
313 
314  i = queue[first++];
315  for (j=xadj[i]; j<xadj[i+1]; j++) {
316  k = adjncy[j];
317  if (!touched[k]) {
318  queue[last++] = k;
319  touched[k] = 1;
320  }
321  }
322  }
323  cptr[++ncmps] = first;
324 
325  gk_free((void **)&touched, LTERM);
326 
327  return ncmps;
328 }
329 
330 
331 /*************************************************************************/
335 /*************************************************************************/
337 {
338  idx_t i, ii, j, jj, k, me, nparts, nvtxs, ncon, ncmps, other,
339  ncand, target;
340  idx_t *xadj, *adjncy, *vwgt, *adjwgt, *where, *pwgts;
341  idx_t *cptr, *cind, *cpvec, *pcptr, *pcind, *cwhere;
342  idx_t cid, bestcid, *cwgt, *bestcwgt;
343  idx_t ntodo, oldntodo, *todo;
344  rkv_t *cand;
345  real_t *tpwgts;
346  idx_t *vmarker=NULL, *pmarker=NULL, *modind=NULL; /* volume specific work arrays */
347 
348  WCOREPUSH;
349 
350  nvtxs = graph->nvtxs;
351  ncon = graph->ncon;
352  xadj = graph->xadj;
353  adjncy = graph->adjncy;
354  vwgt = graph->vwgt;
355  adjwgt = (ctrl->objtype == METIS_OBJTYPE_VOL ? NULL : graph->adjwgt);
356 
357  where = graph->where;
358  pwgts = graph->pwgts;
359 
360  nparts = ctrl->nparts;
361  tpwgts = ctrl->tpwgts;
362 
363  cptr = iwspacemalloc(ctrl, nvtxs+1);
364  cind = iwspacemalloc(ctrl, nvtxs);
365 
366  ncmps = FindPartitionInducedComponents(graph, where, cptr, cind);
367 
369  printf("I found %"PRIDX" components, for this %"PRIDX"-way partition\n",
370  ncmps, nparts));
371 
372  /* There are more components than partitions */
373  if (ncmps > nparts) {
374  cwgt = iwspacemalloc(ctrl, ncon);
375  bestcwgt = iwspacemalloc(ctrl, ncon);
376  cpvec = iwspacemalloc(ctrl, nparts);
377  pcptr = iset(nparts+1, 0, iwspacemalloc(ctrl, nparts+1));
378  pcind = iwspacemalloc(ctrl, ncmps);
379  cwhere = iset(nvtxs, -1, iwspacemalloc(ctrl, nvtxs));
380  todo = iwspacemalloc(ctrl, ncmps);
381  cand = (rkv_t *)wspacemalloc(ctrl, nparts*sizeof(rkv_t));
382 
383  if (ctrl->objtype == METIS_OBJTYPE_VOL) {
384  /* Vol-refinement specific working arrays */
385  modind = iwspacemalloc(ctrl, nvtxs);
386  vmarker = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
387  pmarker = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
388  }
389 
390 
391  /* Get a CSR representation of the components-2-partitions mapping */
392  for (i=0; i<ncmps; i++)
393  pcptr[where[cind[cptr[i]]]]++;
394  MAKECSR(i, nparts, pcptr);
395  for (i=0; i<ncmps; i++)
396  pcind[pcptr[where[cind[cptr[i]]]]++] = i;
397  SHIFTCSR(i, nparts, pcptr);
398 
399  /* Assign the heaviest component of each partition to its original partition */
400  for (ntodo=0, i=0; i<nparts; i++) {
401  if (pcptr[i+1]-pcptr[i] == 1)
402  bestcid = pcind[pcptr[i]];
403  else {
404  for (bestcid=-1, j=pcptr[i]; j<pcptr[i+1]; j++) {
405  cid = pcind[j];
406  iset(ncon, 0, cwgt);
407  for (ii=cptr[cid]; ii<cptr[cid+1]; ii++)
408  iaxpy(ncon, 1, vwgt+cind[ii]*ncon, 1, cwgt, 1);
409  if (bestcid == -1 || isum(ncon, bestcwgt, 1) < isum(ncon, cwgt, 1)) {
410  bestcid = cid;
411  icopy(ncon, cwgt, bestcwgt);
412  }
413  }
414  /* Keep track of those that need to be dealt with */
415  for (j=pcptr[i]; j<pcptr[i+1]; j++) {
416  if (pcind[j] != bestcid)
417  todo[ntodo++] = pcind[j];
418  }
419  }
420 
421  for (j=cptr[bestcid]; j<cptr[bestcid+1]; j++) {
422  ASSERT(where[cind[j]] == i);
423  cwhere[cind[j]] = i;
424  }
425  }
426 
427 
428  while (ntodo > 0) {
429  oldntodo = ntodo;
430  for (i=0; i<ntodo; i++) {
431  cid = todo[i];
432  me = where[cind[cptr[cid]]]; /* Get the domain of this component */
433 
434  /* Determine the weight of the block to be moved */
435  iset(ncon, 0, cwgt);
436  for (j=cptr[cid]; j<cptr[cid+1]; j++)
437  iaxpy(ncon, 1, vwgt+cind[j]*ncon, 1, cwgt, 1);
438 
440  printf("Trying to move %"PRIDX" [%"PRIDX"] from %"PRIDX"\n",
441  cid, isum(ncon, cwgt, 1), me));
442 
443  /* Determine the connectivity */
444  iset(nparts, 0, cpvec);
445  for (j=cptr[cid]; j<cptr[cid+1]; j++) {
446  ii = cind[j];
447  for (jj=xadj[ii]; jj<xadj[ii+1]; jj++)
448  if (cwhere[adjncy[jj]] != -1)
449  cpvec[cwhere[adjncy[jj]]] += (adjwgt ? adjwgt[jj] : 1);
450  }
451 
452  /* Put the neighbors into a cand[] array for sorting */
453  for (ncand=0, j=0; j<nparts; j++) {
454  if (cpvec[j] > 0) {
455  cand[ncand].key = cpvec[j];
456  cand[ncand++].val = j;
457  }
458  }
459  if (ncand == 0)
460  continue;
461 
462  rkvsortd(ncand, cand);
463 
464  /* Limit the moves to only the top candidates, which are defined as
465  those with connectivity at least 50% of the best.
466  This applies only when ncon=1, as for multi-constraint, balancing
467  will be hard. */
468  if (ncon == 1) {
469  for (j=1; j<ncand; j++) {
470  if (cand[j].key < .5*cand[0].key)
471  break;
472  }
473  ncand = j;
474  }
475 
476  /* Now among those, select the one with the best balance */
477  target = cand[0].val;
478  for (j=1; j<ncand; j++) {
479  if (BetterBalanceKWay(ncon, cwgt, ctrl->ubfactors,
480  1, pwgts+target*ncon, ctrl->pijbm+target*ncon,
481  1, pwgts+cand[j].val*ncon, ctrl->pijbm+cand[j].val*ncon))
482  target = cand[j].val;
483  }
484 
486  printf("\tMoving it to %"PRIDX" [%"PRIDX"] [%"PRIDX"]\n", target, cpvec[target], ncand));
487 
488  /* Note that as a result of a previous movement, a connected component may
489  now will like to stay to its original partition */
490  if (target != me) {
491  switch (ctrl->objtype) {
492  case METIS_OBJTYPE_CUT:
493  MoveGroupContigForCut(ctrl, graph, target, cid, cptr, cind);
494  break;
495 
496  case METIS_OBJTYPE_VOL:
497  MoveGroupContigForVol(ctrl, graph, target, cid, cptr, cind,
498  vmarker, pmarker, modind);
499  break;
500 
501  default:
502  gk_errexit(SIGERR, "Unknown objtype %d\n", ctrl->objtype);
503  }
504  }
505 
506  /* Update the cwhere vector */
507  for (j=cptr[cid]; j<cptr[cid+1]; j++)
508  cwhere[cind[j]] = target;
509 
510  todo[i] = todo[--ntodo];
511  }
512  if (oldntodo == ntodo) {
513  IFSET(ctrl->dbglvl, METIS_DBG_CONTIGINFO, printf("Stopped at ntodo: %"PRIDX"\n", ntodo));
514  break;
515  }
516  }
517 
518  for (i=0; i<nvtxs; i++)
519  ASSERT(where[i] == cwhere[i]);
520 
521  }
522 
523  WCOREPOP;
524 }
525 
526 
527 /*************************************************************************/
530 /*************************************************************************/
532  idx_t *ptr, idx_t *ind)
533 {
534  idx_t i, ii, iii, j, jj, k, l, nvtxs, nbnd, from, me;
535  idx_t *xadj, *adjncy, *adjwgt, *where, *bndptr, *bndind;
536  ckrinfo_t *myrinfo;
537  cnbr_t *mynbrs;
538 
539  nvtxs = graph->nvtxs;
540  xadj = graph->xadj;
541  adjncy = graph->adjncy;
542  adjwgt = graph->adjwgt;
543 
544  where = graph->where;
545  bndptr = graph->bndptr;
546  bndind = graph->bndind;
547 
548  nbnd = graph->nbnd;
549 
550  for (iii=ptr[gid]; iii<ptr[gid+1]; iii++) {
551  i = ind[iii];
552  from = where[i];
553 
554  myrinfo = graph->ckrinfo+i;
555  if (myrinfo->inbr == -1) {
556  myrinfo->inbr = cnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
557  myrinfo->nnbrs = 0;
558  }
559  mynbrs = ctrl->cnbrpool + myrinfo->inbr;
560 
561  /* find the location of 'to' in myrinfo or create it if it is not there */
562  for (k=0; k<myrinfo->nnbrs; k++) {
563  if (mynbrs[k].pid == to)
564  break;
565  }
566  if (k == myrinfo->nnbrs) {
567  mynbrs[k].pid = to;
568  mynbrs[k].ed = 0;
569  myrinfo->nnbrs++;
570  }
571 
572  graph->mincut -= mynbrs[k].ed-myrinfo->id;
573 
574  /* Update ID/ED and BND related information for the moved vertex */
575  iaxpy(graph->ncon, 1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+to*graph->ncon, 1);
576  iaxpy(graph->ncon, -1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+from*graph->ncon, 1);
577  UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where, nbnd,
578  bndptr, bndind, BNDTYPE_REFINE);
579 
580  /* Update the degrees of adjacent vertices */
581  for (j=xadj[i]; j<xadj[i+1]; j++) {
582  ii = adjncy[j];
583  me = where[ii];
584  myrinfo = graph->ckrinfo+ii;
585 
586  UpdateAdjacentVertexInfoAndBND(ctrl, ii, xadj[ii+1]-xadj[ii], me,
587  from, to, myrinfo, adjwgt[j], nbnd, bndptr, bndind, BNDTYPE_REFINE);
588  }
589 
590  ASSERT(CheckRInfo(ctrl, graph->ckrinfo+i));
591  }
592 
593  graph->nbnd = nbnd;
594 }
595 
596 
597 /*************************************************************************/
600 /*************************************************************************/
602  idx_t *ptr, idx_t *ind, idx_t *vmarker, idx_t *pmarker,
603  idx_t *modind)
604 {
605  idx_t i, ii, iii, j, jj, k, l, nvtxs, from, me, other, xgain;
606  idx_t *xadj, *vsize, *adjncy, *where;
607  vkrinfo_t *myrinfo, *orinfo;
608  vnbr_t *mynbrs, *onbrs;
609 
610  nvtxs = graph->nvtxs;
611  xadj = graph->xadj;
612  vsize = graph->vsize;
613  adjncy = graph->adjncy;
614  where = graph->where;
615 
616  for (iii=ptr[gid]; iii<ptr[gid+1]; iii++) {
617  i = ind[iii];
618  from = where[i];
619 
620  myrinfo = graph->vkrinfo+i;
621  if (myrinfo->inbr == -1) {
622  myrinfo->inbr = vnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
623  myrinfo->nnbrs = 0;
624  }
625  mynbrs = ctrl->vnbrpool + myrinfo->inbr;
626 
627  xgain = (myrinfo->nid == 0 && myrinfo->ned > 0 ? vsize[i] : 0);
628 
629  /* find the location of 'to' in myrinfo or create it if it is not there */
630  for (k=0; k<myrinfo->nnbrs; k++) {
631  if (mynbrs[k].pid == to)
632  break;
633  }
634  if (k == myrinfo->nnbrs) {
635  if (myrinfo->nid > 0)
636  xgain -= vsize[i];
637 
638  /* determine the volume gain resulting from that move */
639  for (j=xadj[i]; j<xadj[i+1]; j++) {
640  ii = adjncy[j];
641  other = where[ii];
642  orinfo = graph->vkrinfo+ii;
643  onbrs = ctrl->vnbrpool + orinfo->inbr;
644  ASSERT(other != to)
645 
646  if (from == other) {
647  /* Same subdomain vertex: Decrease the gain if 'to' is a new neighbor. */
648  for (l=0; l<orinfo->nnbrs; l++) {
649  if (onbrs[l].pid == to)
650  break;
651  }
652  if (l == orinfo->nnbrs)
653  xgain -= vsize[ii];
654  }
655  else {
656  /* Remote vertex: increase if 'to' is a new subdomain */
657  for (l=0; l<orinfo->nnbrs; l++) {
658  if (onbrs[l].pid == to)
659  break;
660  }
661  if (l == orinfo->nnbrs)
662  xgain -= vsize[ii];
663 
664  /* Remote vertex: decrease if i is the only connection to 'from' */
665  for (l=0; l<orinfo->nnbrs; l++) {
666  if (onbrs[l].pid == from && onbrs[l].ned == 1) {
667  xgain += vsize[ii];
668  break;
669  }
670  }
671  }
672  }
673  graph->minvol -= xgain;
674  graph->mincut -= -myrinfo->nid;
675  }
676  else {
677  graph->minvol -= (xgain + mynbrs[k].gv);
678  graph->mincut -= mynbrs[k].ned-myrinfo->nid;
679  }
680 
681 
682  /* Update where and pwgts */
683  where[i] = to;
684  iaxpy(graph->ncon, 1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+to*graph->ncon, 1);
685  iaxpy(graph->ncon, -1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+from*graph->ncon, 1);
686 
687  /* Update the id/ed/gains/bnd of potentially affected nodes */
688  KWayVolUpdate(ctrl, graph, i, from, to, NULL, NULL, NULL, NULL,
689  NULL, BNDTYPE_REFINE, vmarker, pmarker, modind);
690 
691  /*CheckKWayVolPartitionParams(ctrl, graph);*/
692  }
693 
694  ASSERT(ComputeCut(graph, where) == graph->mincut);
695  ASSERTP(ComputeVolume(graph, where) == graph->minvol,
696  ("%"PRIDX" %"PRIDX"\n", ComputeVolume(graph, where), graph->minvol));
697 
698 }
699 
const gtsam::Symbol key('X', 0)
idx_t idx_t idx_t idx_t * vwgt
idx_t ned
idx_t * bndind
idx_t FindSepInducedComponents(ctrl_t *ctrl, graph_t *graph, idx_t *cptr, idx_t *cind)
Definition: contig.c:267
real_t * tpwgts
#define iwspacemalloc
Definition: rename.h:256
idx_t * xadj
vnbr_t * vnbrpool
#define imalloc
Definition: gklib_rename.h:42
for(size_t i=1;i< poses.size();++i)
#define vnbrpoolGetNext
Definition: rename.h:262
idx_t * pwgts
idx_t * adjwgt
#define ismalloc
Definition: gklib_rename.h:68
#define MAKECSR(i, n, a)
Definition: gk_macros.h:73
idx_t * bndptr
#define ASSERTP(expr, msg)
Definition: gk_macros.h:131
idx_t idx_t * xadj
idx_t minvol
idx_t * where
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
EIGEN_CONSTEXPR Index first(const T &x) EIGEN_NOEXCEPT
NonlinearFactorGraph graph
idx_t pid
static const symbolic::SymbolExpr< internal::symbolic_last_tag > last
idx_t idx_t idx_t idx_t idx_t * vsize
#define PRIDX
#define ASSERT(expression)
Definition: ccolamd.c:872
static const Line3 l(Rot3(), 1, 1)
void MoveGroupContigForVol(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid, idx_t *ptr, idx_t *ind, idx_t *vmarker, idx_t *pmarker, idx_t *modind)
Definition: contig.c:601
#define SIGERR
Definition: gk_defs.h:38
std::vector< int > ind
idx_t IsConnected(graph_t *graph, idx_t report)
Definition: contig.c:167
int32_t idx_t
cnbr_t * cnbrpool
#define BNDTYPE_REFINE
Definition: libmetis/defs.h:30
idx_t nparts
real_t * pijbm
idx_t idx_t idx_t idx_t idx_t * perm
idx_t ncon
#define iaxpy
Definition: gklib_rename.h:27
#define iincset
Definition: gklib_rename.h:30
#define rkvsortd
Definition: gklib_rename.h:91
void EliminateComponents(ctrl_t *ctrl, graph_t *graph)
Definition: contig.c:336
float real_t
idx_t * ncon
#define NULL
Definition: ccolamd.c:609
#define ComputeVolume
Definition: rename.h:63
idx_t IsConnectedSubdomain(ctrl_t *ctrl, graph_t *graph, idx_t pid, idx_t report)
Definition: contig.c:184
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
#define CheckRInfo
Definition: rename.h:68
idx_t mincut
#define SHIFTCSR(i, n, a)
Definition: gk_macros.h:80
#define KWayVolUpdate
Definition: rename.h:120
idx_t gv
#define isum
Definition: gklib_rename.h:72
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
idx_t FindPartitionInducedComponents(graph_t *graph, idx_t *where, idx_t *cptr, idx_t *cind)
Definition: contig.c:32
real_t * ubfactors
#define iset
Definition: gklib_rename.h:67
#define icopy
Definition: gklib_rename.h:28
void gk_free(void **ptr1,...)
Definition: memory.c:202
idx_t idx_t idx_t idx_t * where
idx_t * adjncy
#define cnbrpoolGetNext
Definition: rename.h:260
idx_t idx_t idx_t * adjncy
#define UpdateAdjacentVertexInfoAndBND(ctrl, vid, adjlen, me, from, to, myrinfo, ewgt, nbnd, bndptr, bndind, bndtype)
#define UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where, nbnd, bndptr, bndind, bndtype)
void MoveGroupContigForCut(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t gid, idx_t *ptr, idx_t *ind)
Definition: contig.c:531
#define WCOREPOP
idx_t ed
#define BetterBalanceKWay
Definition: rename.h:142
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
#define ComputeCut
Definition: rename.h:62
void ComputeBFSOrdering(ctrl_t *ctrl, graph_t *graph, idx_t *bfsperm)
Definition: contig.c:115
std::ptrdiff_t j
mobjtype_et objtype
vkrinfo_t * vkrinfo
ckrinfo_t * ckrinfo
#define wspacemalloc
Definition: rename.h:253
#define LTERM
Definition: gk_defs.h:14
idx_t * vwgt


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