minconn.c
Go to the documentation of this file.
1 
11 #include "metislib.h"
12 
13 
14 /*************************************************************************/
17 /*************************************************************************/
19 {
20  idx_t i, ii, j, pid, other, nparts, nvtxs, nnbrs;
21  idx_t *xadj, *adjncy, *adjwgt, *where;
22  idx_t *pptr, *pind;
23  idx_t nads=0, *vadids, *vadwgts;
24 
25  WCOREPUSH;
26 
27  nvtxs = graph->nvtxs;
28  xadj = graph->xadj;
29  adjncy = graph->adjncy;
30  adjwgt = graph->adjwgt;
31  where = graph->where;
32 
33  nparts = ctrl->nparts;
34 
35  vadids = ctrl->pvec1;
36  vadwgts = iset(nparts, 0, ctrl->pvec2);
37 
38  pptr = iwspacemalloc(ctrl, nparts+1);
39  pind = iwspacemalloc(ctrl, nvtxs);
40  iarray2csr(nvtxs, nparts, where, pptr, pind);
41 
42  for (pid=0; pid<nparts; pid++) {
43  switch (ctrl->objtype) {
44  case METIS_OBJTYPE_CUT:
45  {
46  ckrinfo_t *rinfo;
47  cnbr_t *nbrs;
48 
49  rinfo = graph->ckrinfo;
50  for (nads=0, ii=pptr[pid]; ii<pptr[pid+1]; ii++) {
51  i = pind[ii];
52  ASSERT(pid == where[i]);
53 
54  if (rinfo[i].ed > 0) {
55  nnbrs = rinfo[i].nnbrs;
56  nbrs = ctrl->cnbrpool + rinfo[i].inbr;
57 
58  for (j=0; j<nnbrs; j++) {
59  other = nbrs[j].pid;
60  if (vadwgts[other] == 0)
61  vadids[nads++] = other;
62  vadwgts[other] += nbrs[j].ed;
63  }
64  }
65  }
66  }
67  break;
68 
69  case METIS_OBJTYPE_VOL:
70  {
71  vkrinfo_t *rinfo;
72  vnbr_t *nbrs;
73 
74  rinfo = graph->vkrinfo;
75  for (nads=0, ii=pptr[pid]; ii<pptr[pid+1]; ii++) {
76  i = pind[ii];
77  ASSERT(pid == where[i]);
78 
79  if (rinfo[i].ned > 0) {
80  nnbrs = rinfo[i].nnbrs;
81  nbrs = ctrl->vnbrpool + rinfo[i].inbr;
82 
83  for (j=0; j<nnbrs; j++) {
84  other = nbrs[j].pid;
85  if (vadwgts[other] == 0)
86  vadids[nads++] = other;
87  vadwgts[other] += nbrs[j].ned;
88  }
89  }
90  }
91  }
92  break;
93 
94  default:
95  gk_errexit(SIGERR, "Unknown objtype: %d\n", ctrl->objtype);
96  }
97 
98  /* See if you have enough memory to store the adjacent info for that subdomain */
99  if (ctrl->maxnads[pid] < nads) {
100  ctrl->maxnads[pid] = 2*nads;
101  ctrl->adids[pid] = irealloc(ctrl->adids[pid], ctrl->maxnads[pid],
102  "ComputeSubDomainGraph: adids[pid]");
103  ctrl->adwgts[pid] = irealloc(ctrl->adwgts[pid], ctrl->maxnads[pid],
104  "ComputeSubDomainGraph: adids[pid]");
105  }
106 
107  ctrl->nads[pid] = nads;
108  for (j=0; j<nads; j++) {
109  ctrl->adids[pid][j] = vadids[j];
110  ctrl->adwgts[pid][j] = vadwgts[vadids[j]];
111 
112  vadwgts[vadids[j]] = 0;
113  }
114  }
115 
116  WCOREPOP;
117 }
118 
119 
120 /*************************************************************************/
133 /*************************************************************************/
135  idx_t *r_maxndoms)
136 {
137  idx_t i, j, nads;
138 
139  if (ewgt == 0)
140  return;
141 
142  for (i=0; i<2; i++) {
143  nads = ctrl->nads[u];
144  /* Find the edge */
145  for (j=0; j<nads; j++) {
146  if (ctrl->adids[u][j] == v) {
147  ctrl->adwgts[u][j] += ewgt;
148  break;
149  }
150  }
151 
152  if (j == nads) {
153  /* Deal with the case in which the edge was not found */
154  ASSERT(ewgt > 0);
155  if (ctrl->maxnads[u] == nads) {
156  ctrl->maxnads[u] = 2*(nads+1);
157  ctrl->adids[u] = irealloc(ctrl->adids[u], ctrl->maxnads[u],
158  "IncreaseEdgeSubDomainGraph: adids[pid]");
159  ctrl->adwgts[u] = irealloc(ctrl->adwgts[u], ctrl->maxnads[u],
160  "IncreaseEdgeSubDomainGraph: adids[pid]");
161  }
162  ctrl->adids[u][nads] = v;
163  ctrl->adwgts[u][nads] = ewgt;
164  nads++;
165  if (r_maxndoms != NULL && nads > *r_maxndoms) {
166  printf("You just increased the maxndoms: %"PRIDX" %"PRIDX"\n",
167  nads, *r_maxndoms);
168  *r_maxndoms = nads;
169  }
170  }
171  else {
172  /* See if the updated edge becomes 0 */
173  ASSERT(ctrl->adwgts[u][j] >= 0);
174  if (ctrl->adwgts[u][j] == 0) {
175  ctrl->adids[u][j] = ctrl->adids[u][nads-1];
176  ctrl->adwgts[u][j] = ctrl->adwgts[u][nads-1];
177  nads--;
178  if (r_maxndoms != NULL && nads+1 == *r_maxndoms)
179  *r_maxndoms = ctrl->nads[iargmax(ctrl->nparts, ctrl->nads)];
180  }
181  }
182  ctrl->nads[u] = nads;
183 
184  SWAP(u, v, j);
185  }
186 }
187 
188 
189 /*************************************************************************/
191 /*************************************************************************/
193 {
194  idx_t i, ii, j, k, ncon, nparts, scheme, pid_from, pid_to, me, other, nvtxs,
195  total, max, avg, totalout, nind=0, ncand=0, ncand2, target, target2,
196  nadd, bestnadd=0;
197  idx_t min, move, *cpwgt;
198  idx_t *xadj, *adjncy, *vwgt, *adjwgt, *pwgts, *where, *maxpwgt,
199  *mypmat, *otherpmat, *kpmat, *ind;
200  idx_t *nads, **adids, **adwgts;
201  ikv_t *cand, *cand2;
202  ipq_t queue;
203  real_t *tpwgts, badfactor=1.4;
204  idx_t *pptr, *pind;
205  idx_t *vmarker=NULL, *pmarker=NULL, *modind=NULL; /* volume specific work arrays */
206 
207  WCOREPUSH;
208 
209  nvtxs = graph->nvtxs;
210  ncon = graph->ncon;
211  xadj = graph->xadj;
212  adjncy = graph->adjncy;
213  vwgt = graph->vwgt;
214  adjwgt = (ctrl->objtype == METIS_OBJTYPE_VOL ? NULL : graph->adjwgt);
215 
216  where = graph->where;
217  pwgts = graph->pwgts; /* We assume that this is properly initialized */
218 
219  nparts = ctrl->nparts;
220  tpwgts = ctrl->tpwgts;
221 
222  cpwgt = iwspacemalloc(ctrl, ncon);
223  maxpwgt = iwspacemalloc(ctrl, nparts*ncon);
224  ind = iwspacemalloc(ctrl, nvtxs);
225  otherpmat = iset(nparts, 0, iwspacemalloc(ctrl, nparts));
226 
227  cand = ikvwspacemalloc(ctrl, nparts);
228  cand2 = ikvwspacemalloc(ctrl, nparts);
229 
230  pptr = iwspacemalloc(ctrl, nparts+1);
231  pind = iwspacemalloc(ctrl, nvtxs);
232  iarray2csr(nvtxs, nparts, where, pptr, pind);
233 
234  if (ctrl->objtype == METIS_OBJTYPE_VOL) {
235  /* Vol-refinement specific working arrays */
236  modind = iwspacemalloc(ctrl, nvtxs);
237  vmarker = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
238  pmarker = iset(nparts, -1, iwspacemalloc(ctrl, nparts));
239  }
240 
241 
242  /* Compute the pmat matrix and ndoms */
243  ComputeSubDomainGraph(ctrl, graph);
244 
245  nads = ctrl->nads;
246  adids = ctrl->adids;
247  adwgts = ctrl->adwgts;
248 
249  mypmat = iset(nparts, 0, ctrl->pvec1);
250  kpmat = iset(nparts, 0, ctrl->pvec2);
251 
252  /* Compute the maximum allowed weight for each domain */
253  for (i=0; i<nparts; i++) {
254  for (j=0; j<ncon; j++)
255  maxpwgt[i*ncon+j] =
256  (ncon == 1 ? 1.25 : 1.025)*tpwgts[i]*graph->tvwgt[j]*ctrl->ubfactors[j];
257  }
258 
259  ipqInit(&queue, nparts);
260 
261  /* Get into the loop eliminating subdomain connections */
262  while (1) {
263  total = isum(nparts, nads, 1);
264  avg = total/nparts;
265  max = nads[iargmax(nparts, nads)];
266 
268  printf("Adjacent Subdomain Stats: Total: %3"PRIDX", "
269  "Max: %3"PRIDX"[%zu], Avg: %3"PRIDX"\n",
270  total, max, iargmax(nparts, nads), avg));
271 
272  if (max < badfactor*avg)
273  break;
274 
275  /* Add the subdomains that you will try to reduce their connectivity */
276  ipqReset(&queue);
277  for (i=0; i<nparts; i++) {
278  if (nads[i] >= avg + (max-avg)/2)
279  ipqInsert(&queue, i, nads[i]);
280  }
281 
282  move = 0;
283  while ((me = ipqGetTop(&queue)) != -1) {
284  totalout = isum(nads[me], adwgts[me], 1);
285 
286  for (ncand2=0, i=0; i<nads[me]; i++) {
287  mypmat[adids[me][i]] = adwgts[me][i];
288 
289  /* keep track of the weakly connected adjacent subdomains */
290  if (2*nads[me]*adwgts[me][i] < totalout) {
291  cand2[ncand2].val = adids[me][i];
292  cand2[ncand2++].key = adwgts[me][i];
293  }
294  }
295 
297  printf("Me: %"PRIDX", Degree: %4"PRIDX", TotalOut: %"PRIDX",\n",
298  me, nads[me], totalout));
299 
300  /* Sort the connections according to their cut */
301  ikvsorti(ncand2, cand2);
302 
303  /* Two schemes are used for eliminating subdomain edges.
304  The first, tries to eliminate subdomain edges by moving remote groups
305  of vertices to subdomains that 'me' is already connected to.
306  The second, tries to eliminate subdomain edges by moving entire sets of
307  my vertices that connect to the 'other' subdomain to a subdomain that
308  I'm already connected to.
309  These two schemes are applied in sequence. */
310  target = target2 = -1;
311  for (scheme=0; scheme<2; scheme++) {
312  for (min=0; min<ncand2; min++) {
313  other = cand2[min].val;
314 
315  /* pid_from is the subdomain from where the vertices will be removed.
316  pid_to is the adjacent subdomain to pid_from that defines the
317  (me, other) subdomain edge that needs to be removed */
318  if (scheme == 0) {
319  pid_from = other;
320  pid_to = me;
321  }
322  else {
323  pid_from = me;
324  pid_to = other;
325  }
326 
327  /* Go and find the vertices in 'other' that are connected in 'me' */
328  for (nind=0, ii=pptr[pid_from]; ii<pptr[pid_from+1]; ii++) {
329  i = pind[ii];
330  ASSERT(where[i] == pid_from);
331  for (j=xadj[i]; j<xadj[i+1]; j++) {
332  if (where[adjncy[j]] == pid_to) {
333  ind[nind++] = i;
334  break;
335  }
336  }
337  }
338 
339  /* Go and construct the otherpmat to see where these nind vertices are
340  connected to */
341  iset(ncon, 0, cpwgt);
342  for (ncand=0, ii=0; ii<nind; ii++) {
343  i = ind[ii];
344  iaxpy(ncon, 1, vwgt+i*ncon, 1, cpwgt, 1);
345 
346  for (j=xadj[i]; j<xadj[i+1]; j++) {
347  if ((k = where[adjncy[j]]) == pid_from)
348  continue;
349  if (otherpmat[k] == 0)
350  cand[ncand++].val = k;
351  otherpmat[k] += (adjwgt ? adjwgt[j] : 1);
352  }
353  }
354 
355  for (i=0; i<ncand; i++) {
356  cand[i].key = otherpmat[cand[i].val];
357  ASSERT(cand[i].key > 0);
358  }
359 
360  ikvsortd(ncand, cand);
361 
363  printf("\tMinOut: %4"PRIDX", to: %3"PRIDX", TtlWgt: %5"PRIDX"[#:%"PRIDX"]\n",
364  mypmat[other], other, isum(ncon, cpwgt, 1), nind));
365 
366  /* Go through and select the first domain that is common with 'me', and does
367  not increase the nads[target] higher than nads[me], subject to the maxpwgt
368  constraint. Traversal is done from the mostly connected to the least. */
369  for (i=0; i<ncand; i++) {
370  k = cand[i].val;
371 
372  if (mypmat[k] > 0) {
373  /* Check if balance will go off */
374  if (!ivecaxpylez(ncon, 1, cpwgt, pwgts+k*ncon, maxpwgt+k*ncon))
375  continue;
376 
377  /* get a dense vector out of k's connectivity */
378  for (j=0; j<nads[k]; j++)
379  kpmat[adids[k][j]] = adwgts[k][j];
380 
381  /* Check if the move to domain k will increase the nads of another
382  subdomain j that the set of vertices being moved are connected
383  to but domain k is not connected to. */
384  for (j=0; j<nparts; j++) {
385  if (otherpmat[j] > 0 && kpmat[j] == 0 && nads[j]+1 >= nads[me])
386  break;
387  }
388 
389  /* There were no bad second level effects. See if you can find a
390  subdomain to move to. */
391  if (j == nparts) {
392  for (nadd=0, j=0; j<nparts; j++) {
393  if (otherpmat[j] > 0 && kpmat[j] == 0)
394  nadd++;
395  }
396 
398  printf("\t\tto=%"PRIDX", nadd=%"PRIDX", %"PRIDX"\n", k, nadd, nads[k]));
399 
400  if (nads[k]+nadd < nads[me]) {
401  if (target2 == -1 || nads[target2]+bestnadd > nads[k]+nadd ||
402  (nads[target2]+bestnadd == nads[k]+nadd && bestnadd > nadd)) {
403  target2 = k;
404  bestnadd = nadd;
405  }
406  }
407 
408  if (nadd == 0)
409  target = k;
410  }
411 
412  /* reset kpmat for the next iteration */
413  for (j=0; j<nads[k]; j++)
414  kpmat[adids[k][j]] = 0;
415  }
416 
417  if (target != -1)
418  break;
419  }
420 
421  /* reset the otherpmat for the next iteration */
422  for (i=0; i<ncand; i++)
423  otherpmat[cand[i].val] = 0;
424 
425  if (target == -1 && target2 != -1)
426  target = target2;
427 
428  if (target != -1) {
430  printf("\t\tScheme: %"PRIDX". Moving to %"PRIDX"\n", scheme, target));
431  move = 1;
432  break;
433  }
434  }
435 
436  if (target != -1)
437  break; /* A move was found. No need to try the other scheme */
438  }
439 
440  /* reset the mypmat for next iteration */
441  for (i=0; i<nads[me]; i++)
442  mypmat[adids[me][i]] = 0;
443 
444  /* Note that once a target is found the above loops exit right away. So the
445  following variables are valid */
446  if (target != -1) {
447  switch (ctrl->objtype) {
448  case METIS_OBJTYPE_CUT:
449  MoveGroupMinConnForCut(ctrl, graph, target, nind, ind);
450  break;
451  case METIS_OBJTYPE_VOL:
452  MoveGroupMinConnForVol(ctrl, graph, target, nind, ind, vmarker,
453  pmarker, modind);
454  break;
455  default:
456  gk_errexit(SIGERR, "Unknown objtype of %d\n", ctrl->objtype);
457  }
458 
459  /* Update the csr representation of the partitioning vector */
460  iarray2csr(nvtxs, nparts, where, pptr, pind);
461  }
462  }
463 
464  if (move == 0)
465  break;
466  }
467 
468  ipqFree(&queue);
469 
470  WCOREPOP;
471 }
472 
473 
474 /*************************************************************************/
476 /*************************************************************************/
478  idx_t *ind)
479 {
480  idx_t i, ii, j, jj, k, l, nvtxs, nbnd, from, me;
481  idx_t *xadj, *adjncy, *adjwgt, *where, *bndptr, *bndind;
482  ckrinfo_t *myrinfo;
483  cnbr_t *mynbrs;
484 
485  nvtxs = graph->nvtxs;
486  xadj = graph->xadj;
487  adjncy = graph->adjncy;
488  adjwgt = graph->adjwgt;
489 
490  where = graph->where;
491  bndptr = graph->bndptr;
492  bndind = graph->bndind;
493 
494  nbnd = graph->nbnd;
495 
496  while (--nind>=0) {
497  i = ind[nind];
498  from = where[i];
499 
500  myrinfo = graph->ckrinfo+i;
501  if (myrinfo->inbr == -1) {
502  myrinfo->inbr = cnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
503  myrinfo->nnbrs = 0;
504  }
505  mynbrs = ctrl->cnbrpool + myrinfo->inbr;
506 
507  /* find the location of 'to' in myrinfo or create it if it is not there */
508  for (k=0; k<myrinfo->nnbrs; k++) {
509  if (mynbrs[k].pid == to)
510  break;
511  }
512  if (k == myrinfo->nnbrs) {
513  ASSERT(k < xadj[i+1]-xadj[i]);
514  mynbrs[k].pid = to;
515  mynbrs[k].ed = 0;
516  myrinfo->nnbrs++;
517  }
518 
519  /* Update pwgts */
520  iaxpy(graph->ncon, 1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+to*graph->ncon, 1);
521  iaxpy(graph->ncon, -1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+from*graph->ncon, 1);
522 
523  /* Update mincut */
524  graph->mincut -= mynbrs[k].ed-myrinfo->id;
525 
526  /* Update subdomain connectivity graph to reflect the move of 'i' */
527  UpdateEdgeSubDomainGraph(ctrl, from, to, myrinfo->id-mynbrs[k].ed, NULL);
528 
529  /* Update ID/ED and BND related information for the moved vertex */
530  UpdateMovedVertexInfoAndBND(i, from, k, to, myrinfo, mynbrs, where, nbnd,
531  bndptr, bndind, BNDTYPE_REFINE);
532 
533  /* Update the degrees of adjacent vertices */
534  for (j=xadj[i]; j<xadj[i+1]; j++) {
535  ii = adjncy[j];
536  me = where[ii];
537  myrinfo = graph->ckrinfo+ii;
538 
539  UpdateAdjacentVertexInfoAndBND(ctrl, ii, xadj[ii+1]-xadj[ii], me,
540  from, to, myrinfo, adjwgt[j], nbnd, bndptr, bndind, BNDTYPE_REFINE);
541 
542  /* Update subdomain graph to reflect the move of 'i' for domains other
543  than 'from' and 'to' */
544  if (me != from && me != to) {
545  UpdateEdgeSubDomainGraph(ctrl, from, me, -adjwgt[j], NULL);
546  UpdateEdgeSubDomainGraph(ctrl, to, me, adjwgt[j], NULL);
547  }
548  }
549  }
550 
551  ASSERT(ComputeCut(graph, where) == graph->mincut);
552 
553  graph->nbnd = nbnd;
554 
555 }
556 
557 
558 /*************************************************************************/
560 /*************************************************************************/
562  idx_t *ind, idx_t *vmarker, idx_t *pmarker, idx_t *modind)
563 {
564  idx_t i, ii, j, jj, k, l, nvtxs, from, me, other, xgain, ewgt;
565  idx_t *xadj, *vsize, *adjncy, *where;
566  vkrinfo_t *myrinfo, *orinfo;
567  vnbr_t *mynbrs, *onbrs;
568 
569  nvtxs = graph->nvtxs;
570  xadj = graph->xadj;
571  vsize = graph->vsize;
572  adjncy = graph->adjncy;
573  where = graph->where;
574 
575  while (--nind>=0) {
576  i = ind[nind];
577  from = where[i];
578 
579  myrinfo = graph->vkrinfo+i;
580  if (myrinfo->inbr == -1) {
581  myrinfo->inbr = vnbrpoolGetNext(ctrl, xadj[i+1]-xadj[i]+1);
582  myrinfo->nnbrs = 0;
583  }
584  mynbrs = ctrl->vnbrpool + myrinfo->inbr;
585 
586  xgain = (myrinfo->nid == 0 && myrinfo->ned > 0 ? vsize[i] : 0);
587 
588  //printf("Moving %"PRIDX" from %"PRIDX" to %"PRIDX" [vsize: %"PRIDX"] [xgain: %"PRIDX"]\n",
589  // i, from, to, vsize[i], xgain);
590 
591  /* find the location of 'to' in myrinfo or create it if it is not there */
592  for (k=0; k<myrinfo->nnbrs; k++) {
593  if (mynbrs[k].pid == to)
594  break;
595  }
596 
597  if (k == myrinfo->nnbrs) {
598  //printf("Missing neighbor\n");
599 
600  if (myrinfo->nid > 0)
601  xgain -= vsize[i];
602 
603  /* determine the volume gain resulting from that move */
604  for (j=xadj[i]; j<xadj[i+1]; j++) {
605  ii = adjncy[j];
606  other = where[ii];
607  orinfo = graph->vkrinfo+ii;
608  onbrs = ctrl->vnbrpool + orinfo->inbr;
609  ASSERT(other != to)
610 
611  //printf(" %8d %8d %3d\n", (int)ii, (int)vsize[ii], (int)other);
612 
613  if (from == other) {
614  /* Same subdomain vertex: Decrease the gain if 'to' is a new neighbor. */
615  for (l=0; l<orinfo->nnbrs; l++) {
616  if (onbrs[l].pid == to)
617  break;
618  }
619  if (l == orinfo->nnbrs)
620  xgain -= vsize[ii];
621  }
622  else {
623  /* Remote vertex: increase if 'to' is a new subdomain */
624  for (l=0; l<orinfo->nnbrs; l++) {
625  if (onbrs[l].pid == to)
626  break;
627  }
628  if (l == orinfo->nnbrs)
629  xgain -= vsize[ii];
630 
631  /* Remote vertex: decrease if i is the only connection to 'from' */
632  for (l=0; l<orinfo->nnbrs; l++) {
633  if (onbrs[l].pid == from && onbrs[l].ned == 1) {
634  xgain += vsize[ii];
635  break;
636  }
637  }
638  }
639  }
640  graph->minvol -= xgain;
641  graph->mincut -= -myrinfo->nid;
642  ewgt = myrinfo->nid;
643  }
644  else {
645  graph->minvol -= (xgain + mynbrs[k].gv);
646  graph->mincut -= mynbrs[k].ned-myrinfo->nid;
647  ewgt = myrinfo->nid-mynbrs[k].ned;
648  }
649 
650  /* Update where and pwgts */
651  where[i] = to;
652  iaxpy(graph->ncon, 1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+to*graph->ncon, 1);
653  iaxpy(graph->ncon, -1, graph->vwgt+i*graph->ncon, 1, graph->pwgts+from*graph->ncon, 1);
654 
655  /* Update subdomain connectivity graph to reflect the move of 'i' */
656  UpdateEdgeSubDomainGraph(ctrl, from, to, ewgt, NULL);
657 
658  /* Update the subdomain connectivity of the adjacent vertices */
659  for (j=xadj[i]; j<xadj[i+1]; j++) {
660  me = where[adjncy[j]];
661  if (me != from && me != to) {
662  UpdateEdgeSubDomainGraph(ctrl, from, me, -1, NULL);
663  UpdateEdgeSubDomainGraph(ctrl, to, me, 1, NULL);
664  }
665  }
666 
667  /* Update the id/ed/gains/bnd of potentially affected nodes */
668  KWayVolUpdate(ctrl, graph, i, from, to, NULL, NULL, NULL, NULL,
669  NULL, BNDTYPE_REFINE, vmarker, pmarker, modind);
670 
671  /*CheckKWayVolPartitionParams(ctrl, graph);*/
672  }
673  ASSERT(ComputeCut(graph, where) == graph->mincut);
674  ASSERTP(ComputeVolume(graph, where) == graph->minvol,
675  ("%"PRIDX" %"PRIDX"\n", ComputeVolume(graph, where), graph->minvol));
676 
677 }
678 
679 
680 /*************************************************************************/
682 /*************************************************************************/
684 {
685  idx_t i, j, k, me, nvtxs, total, max;
686  idx_t *xadj, *adjncy, *adjwgt, *pmat;
687 
688  nvtxs = graph->nvtxs;
689  xadj = graph->xadj;
690  adjncy = graph->adjncy;
691  adjwgt = graph->adjwgt;
692 
693  pmat = ismalloc(nparts*nparts, 0, "ComputeSubDomainGraph: pmat");
694 
695  for (i=0; i<nvtxs; i++) {
696  me = where[i];
697  for (j=xadj[i]; j<xadj[i+1]; j++) {
698  k = adjncy[j];
699  if (where[k] != me)
700  pmat[me*nparts+where[k]] += adjwgt[j];
701  }
702  }
703 
704  /* printf("Subdomain Info\n"); */
705  total = max = 0;
706  for (i=0; i<nparts; i++) {
707  for (k=0, j=0; j<nparts; j++) {
708  if (pmat[i*nparts+j] > 0)
709  k++;
710  }
711  total += k;
712 
713  if (k > max)
714  max = k;
715 /*
716  printf("%2"PRIDX" -> %2"PRIDX" ", i, k);
717  for (j=0; j<nparts; j++) {
718  if (pmat[i*nparts+j] > 0)
719  printf("[%2"PRIDX" %4"PRIDX"] ", j, pmat[i*nparts+j]);
720  }
721  printf("\n");
722 */
723  }
724  printf("Total adjacent subdomains: %"PRIDX", Max: %"PRIDX"\n", total, max);
725 
726  gk_free((void **)&pmat, LTERM);
727 }
728 
729 
const gtsam::Symbol key('X', 0)
idx_t idx_t idx_t idx_t * vwgt
idx_t ned
idx_t * bndind
void ComputeSubDomainGraph(ctrl_t *ctrl, graph_t *graph)
Definition: minconn.c:18
idx_t * maxnads
#define max(a, b)
Definition: datatypes.h:20
real_t * tpwgts
#define iwspacemalloc
Definition: rename.h:256
#define ikvsortd
Definition: gklib_rename.h:39
#define iarray2csr
Definition: gklib_rename.h:26
idx_t * xadj
vnbr_t * vnbrpool
#define ikvwspacemalloc
Definition: rename.h:258
#define vnbrpoolGetNext
Definition: rename.h:262
idx_t * pwgts
idx_t * adjwgt
#define min(a, b)
Definition: datatypes.h:19
#define ismalloc
Definition: gklib_rename.h:68
idx_t * bndptr
#define ASSERTP(expr, msg)
Definition: gk_macros.h:131
void MoveGroupMinConnForVol(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t nind, idx_t *ind, idx_t *vmarker, idx_t *pmarker, idx_t *modind)
Definition: minconn.c:561
idx_t idx_t * xadj
idx_t minvol
idx_t * where
idx_t pid
idx_t idx_t idx_t idx_t idx_t idx_t idx_t * nparts
#define WCOREPUSH
#define ikvsorti
Definition: gklib_rename.h:40
idx_t nvtxs
#define iargmax
Definition: gklib_rename.h:23
#define ipqFree
Definition: gklib_rename.h:50
idx_t * vsize
void gk_errexit(int signum, char *f_str,...)
Definition: error.c:77
mdbglvl_et dbglvl
#define ivecaxpylez
Definition: rename.h:138
NonlinearFactorGraph graph
void PrintSubDomainGraph(graph_t *graph, idx_t nparts, idx_t *where)
Definition: minconn.c:683
idx_t pid
idx_t idx_t idx_t idx_t idx_t * vsize
#define PRIDX
idx_t * pvec2
#define ipqInsert
Definition: gklib_rename.h:53
#define ASSERT(expression)
Definition: ccolamd.c:872
detail::enable_if_t<!detail::move_never< T >::value, T > move(object &&obj)
Definition: cast.h:1080
static const Line3 l(Rot3(), 1, 1)
void UpdateEdgeSubDomainGraph(ctrl_t *ctrl, idx_t u, idx_t v, idx_t ewgt, idx_t *r_maxndoms)
Definition: minconn.c:134
#define SIGERR
Definition: gk_defs.h:38
std::vector< int > ind
int32_t idx_t
cnbr_t * cnbrpool
#define BNDTYPE_REFINE
Definition: libmetis/defs.h:30
idx_t nparts
Array< int, Dynamic, 1 > v
void EliminateSubDomainEdges(ctrl_t *ctrl, graph_t *graph)
Definition: minconn.c:192
idx_t ncon
#define iaxpy
Definition: gklib_rename.h:27
idx_t * nads
float real_t
idx_t * ncon
#define NULL
Definition: ccolamd.c:609
#define ComputeVolume
Definition: rename.h:63
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t * tpwgts
idx_t mincut
#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
#define ipqInit
Definition: gklib_rename.h:52
idx_t * pvec1
real_t * ubfactors
#define iset
Definition: gklib_rename.h:67
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 * tvwgt
idx_t idx_t idx_t * adjncy
#define ipqReset
Definition: gklib_rename.h:55
void MoveGroupMinConnForCut(ctrl_t *ctrl, graph_t *graph, idx_t to, idx_t nind, idx_t *ind)
Definition: minconn.c:477
idx_t ** adids
#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)
#define WCOREPOP
idx_t ed
#define ipqGetTop
Definition: gklib_rename.h:51
idx_t ** adwgts
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
#define ComputeCut
Definition: rename.h:62
#define irealloc
Definition: gklib_rename.h:65
#define SWAP
std::ptrdiff_t j
mobjtype_et objtype
vkrinfo_t * vkrinfo
ckrinfo_t * ckrinfo
#define LTERM
Definition: gk_defs.h:14
idx_t * vwgt


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