coarsen.c
Go to the documentation of this file.
1 
12 #include "metislib.h"
13 
14 #define UNMATCHEDFOR2HOP 0.10 /* The fraction of unmatched vertices that triggers 2-hop */
15 
16 
17 /*************************************************************************/
21 /*************************************************************************/
23 {
24  idx_t i, eqewgts, level=0;
25 
27 
28  /* determine if the weights on the edges are all the same */
29  for (eqewgts=1, i=1; i<graph->nedges; i++) {
30  if (graph->adjwgt[0] != graph->adjwgt[i]) {
31  eqewgts = 0;
32  break;
33  }
34  }
35 
36  /* set the maximum allowed coarsest vertex weight */
37  for (i=0; i<graph->ncon; i++)
38  ctrl->maxvwgt[i] = 1.5*graph->tvwgt[i]/ctrl->CoarsenTo;
39 
40  do {
42 
43  /* allocate memory for cmap, if it has not already been done due to
44  multiple cuts */
45  if (graph->cmap == NULL)
46  graph->cmap = imalloc(graph->nvtxs, "CoarsenGraph: graph->cmap");
47 
48  /* determine which matching scheme you will use */
49  switch (ctrl->ctype) {
50  case METIS_CTYPE_RM:
51  Match_RM(ctrl, graph);
52  break;
53  case METIS_CTYPE_SHEM:
54  if (eqewgts || graph->nedges == 0)
55  Match_RM(ctrl, graph);
56  else
57  Match_SHEM(ctrl, graph);
58  break;
59  default:
60  gk_errexit(SIGERR, "Unknown ctype: %d\n", ctrl->ctype);
61  }
62 
63  graph = graph->coarser;
64  eqewgts = 0;
65  level++;
66 
67  ASSERT(CheckGraph(graph, 0, 1));
68 
69  } while (graph->nvtxs > ctrl->CoarsenTo &&
70  graph->nvtxs < COARSEN_FRACTION*graph->finer->nvtxs &&
71  graph->nedges > graph->nvtxs/2);
72 
73  IFSET(ctrl->dbglvl, METIS_DBG_COARSEN, PrintCGraphStats(ctrl, graph));
74  IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->CoarsenTmr));
75 
76  return graph;
77 }
78 
79 
80 /*************************************************************************/
84 /*************************************************************************/
86 {
87  idx_t i, eqewgts, level;
88 
90 
91  /* determine if the weights on the edges are all the same */
92  for (eqewgts=1, i=1; i<graph->nedges; i++) {
93  if (graph->adjwgt[0] != graph->adjwgt[i]) {
94  eqewgts = 0;
95  break;
96  }
97  }
98 
99  /* set the maximum allowed coarsest vertex weight */
100  for (i=0; i<graph->ncon; i++)
101  ctrl->maxvwgt[i] = 1.5*graph->tvwgt[i]/ctrl->CoarsenTo;
102 
103  for (level=0; level<nlevels; level++) {
105 
106  /* allocate memory for cmap, if it has not already been done due to
107  multiple cuts */
108  if (graph->cmap == NULL)
109  graph->cmap = imalloc(graph->nvtxs, "CoarsenGraph: graph->cmap");
110 
111  /* determine which matching scheme you will use */
112  switch (ctrl->ctype) {
113  case METIS_CTYPE_RM:
114  Match_RM(ctrl, graph);
115  break;
116  case METIS_CTYPE_SHEM:
117  if (eqewgts || graph->nedges == 0)
118  Match_RM(ctrl, graph);
119  else
120  Match_SHEM(ctrl, graph);
121  break;
122  default:
123  gk_errexit(SIGERR, "Unknown ctype: %d\n", ctrl->ctype);
124  }
125 
126  graph = graph->coarser;
127  eqewgts = 0;
128 
129  ASSERT(CheckGraph(graph, 0, 1));
130 
131  if (graph->nvtxs < ctrl->CoarsenTo ||
132  graph->nvtxs > COARSEN_FRACTION*graph->finer->nvtxs ||
133  graph->nedges < graph->nvtxs/2)
134  break;
135  }
136 
139 
140  return graph;
141 }
142 
143 
144 /*************************************************************************/
148 /**************************************************************************/
150 {
151  idx_t i, pi, ii, j, jj, jjinc, k, nvtxs, ncon, cnvtxs, maxidx, last_unmatched;
152  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *maxvwgt;
153  idx_t *match, *cmap, *perm;
154  size_t nunmatched=0;
155 
156  WCOREPUSH;
157 
159 
160  nvtxs = graph->nvtxs;
161  ncon = graph->ncon;
162  xadj = graph->xadj;
163  vwgt = graph->vwgt;
164  adjncy = graph->adjncy;
165  adjwgt = graph->adjwgt;
166  cmap = graph->cmap;
167 
168  maxvwgt = ctrl->maxvwgt;
169 
170  match = iset(nvtxs, UNMATCHED, iwspacemalloc(ctrl, nvtxs));
171  perm = iwspacemalloc(ctrl, nvtxs);
172 
173  irandArrayPermute(nvtxs, perm, nvtxs/8, 1);
174 
175  for (cnvtxs=0, last_unmatched=0, pi=0; pi<nvtxs; pi++) {
176  i = perm[pi];
177 
178  if (match[i] == UNMATCHED) { /* Unmatched */
179  maxidx = i;
180 
181  if ((ncon == 1 ? vwgt[i] < maxvwgt[0] : ivecle(ncon, vwgt+i*ncon, maxvwgt))) {
182  /* Deal with island vertices. Find a non-island and match it with.
183  The matching ignores ctrl->maxvwgt requirements */
184  if (xadj[i] == xadj[i+1]) {
185  last_unmatched = gk_max(pi, last_unmatched)+1;
186  for (; last_unmatched<nvtxs; last_unmatched++) {
187  j = perm[last_unmatched];
188  if (match[j] == UNMATCHED) {
189  maxidx = j;
190  break;
191  }
192  }
193  }
194  else {
195  /* Find a random matching, subject to maxvwgt constraints */
196  if (ncon == 1) {
197  /* single constraint version */
198  for (j=xadj[i]; j<xadj[i+1]; j++) {
199  k = adjncy[j];
200  if (match[k] == UNMATCHED && vwgt[i]+vwgt[k] <= maxvwgt[0]) {
201  maxidx = k;
202  break;
203  }
204  }
205 
206  /* If it did not match, record for a 2-hop matching. */
207  if (maxidx == i && 3*vwgt[i] < maxvwgt[0]) {
208  nunmatched++;
209  maxidx = UNMATCHED;
210  }
211  }
212  else {
213  /* multi-constraint version */
214  for (j=xadj[i]; j<xadj[i+1]; j++) {
215  k = adjncy[j];
216  if (match[k] == UNMATCHED &&
217  ivecaxpylez(ncon, 1, vwgt+i*ncon, vwgt+k*ncon, maxvwgt)) {
218  maxidx = k;
219  break;
220  }
221  }
222 
223  /* If it did not match, record for a 2-hop matching. */
224  if (maxidx == i && ivecaxpylez(ncon, 2, vwgt+i*ncon, vwgt+i*ncon, maxvwgt)) {
225  nunmatched++;
226  maxidx = UNMATCHED;
227  }
228  }
229  }
230  }
231 
232  if (maxidx != UNMATCHED) {
233  cmap[i] = cmap[maxidx] = cnvtxs++;
234  match[i] = maxidx;
235  match[maxidx] = i;
236  }
237  }
238  }
239 
240  //printf("nunmatched: %zu\n", nunmatched);
241 
242  /* see if a 2-hop matching is required/allowed */
243  if (!ctrl->no2hop && nunmatched > UNMATCHEDFOR2HOP*nvtxs)
244  cnvtxs = Match_2Hop(ctrl, graph, perm, match, cnvtxs, nunmatched);
245 
246 
247  /* match the final unmatched vertices with themselves and reorder the vertices
248  of the coarse graph for memory-friendly contraction */
249  for (cnvtxs=0, i=0; i<nvtxs; i++) {
250  if (match[i] == UNMATCHED) {
251  match[i] = i;
252  cmap[i] = cnvtxs++;
253  }
254  else {
255  if (i <= match[i])
256  cmap[i] = cmap[match[i]] = cnvtxs++;
257  }
258  }
259 
261 
262  CreateCoarseGraph(ctrl, graph, cnvtxs, match);
263 
264  WCOREPOP;
265 
266  return cnvtxs;
267 }
268 
269 
270 /**************************************************************************/
275 /**************************************************************************/
277 {
278  idx_t i, pi, ii, j, jj, jjinc, k, nvtxs, ncon, cnvtxs, maxidx, maxwgt,
279  last_unmatched, avgdegree;
280  idx_t *xadj, *vwgt, *adjncy, *adjwgt, *maxvwgt;
281  idx_t *match, *cmap, *degrees, *perm, *tperm;
282  size_t nunmatched=0;
283 
284  WCOREPUSH;
285 
287 
288  nvtxs = graph->nvtxs;
289  ncon = graph->ncon;
290  xadj = graph->xadj;
291  vwgt = graph->vwgt;
292  adjncy = graph->adjncy;
293  adjwgt = graph->adjwgt;
294  cmap = graph->cmap;
295 
296  maxvwgt = ctrl->maxvwgt;
297 
298  match = iset(nvtxs, UNMATCHED, iwspacemalloc(ctrl, nvtxs));
299  perm = iwspacemalloc(ctrl, nvtxs);
300  tperm = iwspacemalloc(ctrl, nvtxs);
301  degrees = iwspacemalloc(ctrl, nvtxs);
302 
303  irandArrayPermute(nvtxs, tperm, nvtxs/8, 1);
304 
305  avgdegree = 0.7*(xadj[nvtxs]/nvtxs);
306  for (i=0; i<nvtxs; i++)
307  degrees[i] = (xadj[i+1]-xadj[i] > avgdegree ? avgdegree : xadj[i+1]-xadj[i]);
308  BucketSortKeysInc(ctrl, nvtxs, avgdegree, degrees, tperm, perm);
309 
310  for (cnvtxs=0, last_unmatched=0, pi=0; pi<nvtxs; pi++) {
311  i = perm[pi];
312 
313  if (match[i] == UNMATCHED) { /* Unmatched */
314  maxidx = i;
315  maxwgt = -1;
316 
317  if ((ncon == 1 ? vwgt[i] < maxvwgt[0] : ivecle(ncon, vwgt+i*ncon, maxvwgt))) {
318  /* Deal with island vertices. Find a non-island and match it with.
319  The matching ignores ctrl->maxvwgt requirements */
320  if (xadj[i] == xadj[i+1]) {
321  last_unmatched = gk_max(pi, last_unmatched)+1;
322  for (; last_unmatched<nvtxs; last_unmatched++) {
323  j = perm[last_unmatched];
324  if (match[j] == UNMATCHED) {
325  maxidx = j;
326  break;
327  }
328  }
329  }
330  else {
331  /* Find a heavy-edge matching, subject to maxvwgt constraints */
332  if (ncon == 1) {
333  /* single constraint version */
334  for (j=xadj[i]; j<xadj[i+1]; j++) {
335  k = adjncy[j];
336  if (match[k] == UNMATCHED &&
337  maxwgt < adjwgt[j] && vwgt[i]+vwgt[k] <= maxvwgt[0]) {
338  maxidx = k;
339  maxwgt = adjwgt[j];
340  }
341  }
342 
343  /* If it did not match, record for a 2-hop matching. */
344  if (maxidx == i && 3*vwgt[i] < maxvwgt[0]) {
345  nunmatched++;
346  maxidx = UNMATCHED;
347  }
348  }
349  else {
350  /* multi-constraint version */
351  for (j=xadj[i]; j<xadj[i+1]; j++) {
352  k = adjncy[j];
353  if (match[k] == UNMATCHED &&
354  ivecaxpylez(ncon, 1, vwgt+i*ncon, vwgt+k*ncon, maxvwgt) &&
355  (maxwgt < adjwgt[j] ||
356  (maxwgt == adjwgt[j] &&
357  BetterVBalance(ncon, graph->invtvwgt, vwgt+i*ncon,
358  vwgt+maxidx*ncon, vwgt+k*ncon)))) {
359  maxidx = k;
360  maxwgt = adjwgt[j];
361  }
362  }
363 
364  /* If it did not match, record for a 2-hop matching. */
365  if (maxidx == i && ivecaxpylez(ncon, 2, vwgt+i*ncon, vwgt+i*ncon, maxvwgt)) {
366  nunmatched++;
367  maxidx = UNMATCHED;
368  }
369  }
370  }
371  }
372 
373  if (maxidx != UNMATCHED) {
374  cmap[i] = cmap[maxidx] = cnvtxs++;
375  match[i] = maxidx;
376  match[maxidx] = i;
377  }
378  }
379  }
380 
381  //printf("nunmatched: %zu\n", nunmatched);
382 
383  /* see if a 2-hop matching is required/allowed */
384  if (!ctrl->no2hop && nunmatched > UNMATCHEDFOR2HOP*nvtxs)
385  cnvtxs = Match_2Hop(ctrl, graph, perm, match, cnvtxs, nunmatched);
386 
387 
388  /* match the final unmatched vertices with themselves and reorder the vertices
389  of the coarse graph for memory-friendly contraction */
390  for (cnvtxs=0, i=0; i<nvtxs; i++) {
391  if (match[i] == UNMATCHED) {
392  match[i] = i;
393  cmap[i] = cnvtxs++;
394  }
395  else {
396  if (i <= match[i])
397  cmap[i] = cmap[match[i]] = cnvtxs++;
398  }
399  }
400 
402 
403  CreateCoarseGraph(ctrl, graph, cnvtxs, match);
404 
405  WCOREPOP;
406 
407  return cnvtxs;
408 }
409 
410 
411 /*************************************************************************/
414 /**************************************************************************/
416  idx_t cnvtxs, size_t nunmatched)
417 {
418 
419  cnvtxs = Match_2HopAny(ctrl, graph, perm, match, cnvtxs, &nunmatched, 2);
420  cnvtxs = Match_2HopAll(ctrl, graph, perm, match, cnvtxs, &nunmatched, 64);
421  if (nunmatched > 1.5*UNMATCHEDFOR2HOP*graph->nvtxs)
422  cnvtxs = Match_2HopAny(ctrl, graph, perm, match, cnvtxs, &nunmatched, 3);
423  if (nunmatched > 2.0*UNMATCHEDFOR2HOP*graph->nvtxs)
424  cnvtxs = Match_2HopAny(ctrl, graph, perm, match, cnvtxs, &nunmatched, graph->nvtxs);
425 
426  return cnvtxs;
427 }
428 
429 
430 /*************************************************************************/
436 /**************************************************************************/
438  idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree)
439 {
440  idx_t i, pi, ii, j, jj, k, nvtxs;
441  idx_t *xadj, *adjncy, *colptr, *rowind;
442  idx_t *cmap;
443  size_t nunmatched;
444 
446 
447  nvtxs = graph->nvtxs;
448  xadj = graph->xadj;
449  adjncy = graph->adjncy;
450  cmap = graph->cmap;
451 
452  nunmatched = *r_nunmatched;
453 
454  /*IFSET(ctrl->dbglvl, METIS_DBG_COARSEN, printf("IN: nunmatched: %zu\t", * nunmatched)); */
455 
456  /* create the inverted index */
457  WCOREPUSH;
458  colptr = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs+1));
459  for (i=0; i<nvtxs; i++) {
460  if (match[i] == UNMATCHED && xadj[i+1]-xadj[i] < maxdegree) {
461  for (j=xadj[i]; j<xadj[i+1]; j++)
462  colptr[adjncy[j]]++;
463  }
464  }
465  MAKECSR(i, nvtxs, colptr);
466 
467  rowind = iwspacemalloc(ctrl, colptr[nvtxs]);
468  for (pi=0; pi<nvtxs; pi++) {
469  i = perm[pi];
470  if (match[i] == UNMATCHED && xadj[i+1]-xadj[i] < maxdegree) {
471  for (j=xadj[i]; j<xadj[i+1]; j++)
472  rowind[colptr[adjncy[j]]++] = i;
473  }
474  }
475  SHIFTCSR(i, nvtxs, colptr);
476 
477  /* compute matchings by going down the inverted index */
478  for (pi=0; pi<nvtxs; pi++) {
479  i = perm[pi];
480  if (colptr[i+1]-colptr[i] < 2)
481  continue;
482 
483  for (jj=colptr[i+1], j=colptr[i]; j<jj; j++) {
484  if (match[rowind[j]] == UNMATCHED) {
485  for (jj--; jj>j; jj--) {
486  if (match[rowind[jj]] == UNMATCHED) {
487  cmap[rowind[j]] = cmap[rowind[jj]] = cnvtxs++;
488  match[rowind[j]] = rowind[jj];
489  match[rowind[jj]] = rowind[j];
490  nunmatched -= 2;
491  break;
492  }
493  }
494  }
495  }
496  }
497  WCOREPOP;
498 
499  /* IFSET(ctrl->dbglvl, METIS_DBG_COARSEN, printf("OUT: nunmatched: %zu\n", nunmatched)); */
500 
502 
503  *r_nunmatched = nunmatched;
504  return cnvtxs;
505 }
506 
507 
508 /*************************************************************************/
515 /**************************************************************************/
517  idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree)
518 {
519  idx_t i, pi, pk, ii, j, jj, k, nvtxs, mask, idegree;
520  idx_t *xadj, *adjncy;
521  idx_t *cmap, *mark;
522  ikv_t *keys;
523  size_t nunmatched, ncand;
524 
526 
527  nvtxs = graph->nvtxs;
528  xadj = graph->xadj;
529  adjncy = graph->adjncy;
530  cmap = graph->cmap;
531 
532  nunmatched = *r_nunmatched;
533  mask = IDX_MAX/maxdegree;
534 
535  /*IFSET(ctrl->dbglvl, METIS_DBG_COARSEN, printf("IN: nunmatched: %zu\t", nunmatched)); */
536 
537  WCOREPUSH;
538 
539  /* collapse vertices with identical adjancency lists */
540  keys = ikvwspacemalloc(ctrl, nunmatched);
541  for (ncand=0, pi=0; pi<nvtxs; pi++) {
542  i = perm[pi];
543  idegree = xadj[i+1]-xadj[i];
544  if (match[i] == UNMATCHED && idegree > 1 && idegree < maxdegree) {
545  for (k=0, j=xadj[i]; j<xadj[i+1]; j++)
546  k += adjncy[j]%mask;
547  keys[ncand].val = i;
548  keys[ncand].key = (k%mask)*maxdegree + idegree;
549  ncand++;
550  }
551  }
552  ikvsorti(ncand, keys);
553 
554  mark = iset(nvtxs, 0, iwspacemalloc(ctrl, nvtxs));
555  for (pi=0; pi<ncand; pi++) {
556  i = keys[pi].val;
557  if (match[i] != UNMATCHED)
558  continue;
559 
560  for (j=xadj[i]; j<xadj[i+1]; j++)
561  mark[adjncy[j]] = i;
562 
563  for (pk=pi+1; pk<ncand; pk++) {
564  k = keys[pk].val;
565  if (match[k] != UNMATCHED)
566  continue;
567 
568  if (keys[pi].key != keys[pk].key)
569  break;
570  if (xadj[i+1]-xadj[i] != xadj[k+1]-xadj[k])
571  break;
572 
573  for (jj=xadj[k]; jj<xadj[k+1]; jj++) {
574  if (mark[adjncy[jj]] != i)
575  break;
576  }
577  if (jj == xadj[k+1]) {
578  cmap[i] = cmap[k] = cnvtxs++;
579  match[i] = k;
580  match[k] = i;
581  nunmatched -= 2;
582  break;
583  }
584  }
585  }
586  WCOREPOP;
587 
588  /*IFSET(ctrl->dbglvl, METIS_DBG_COARSEN, printf("OUT: ncand: %zu, nunmatched: %zu\n", ncand, nunmatched)); */
589 
591 
592  *r_nunmatched = nunmatched;
593  return cnvtxs;
594 }
595 
596 
597 /*************************************************************************/
600 /*************************************************************************/
602 {
603  idx_t i;
604 
605  printf("%10"PRIDX" %10"PRIDX" %10"PRIDX" [%"PRIDX"] [",
606  graph->nvtxs, graph->nedges, isum(graph->nedges, graph->adjwgt, 1), ctrl->CoarsenTo);
607 
608  for (i=0; i<graph->ncon; i++)
609  printf(" %8"PRIDX":%8"PRIDX, ctrl->maxvwgt[i], graph->tvwgt[i]);
610  printf(" ]\n");
611 }
612 
613 
614 /*************************************************************************/
620 /*************************************************************************/
622  idx_t *match)
623 {
624  idx_t j, jj, k, kk, l, m, istart, iend, nvtxs, nedges, ncon, cnedges,
625  v, u, mask, dovsize;
626  idx_t *xadj, *vwgt, *vsize, *adjncy, *adjwgt;
627  idx_t *cmap, *htable;
628  idx_t *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt;
629  graph_t *cgraph;
630 
631  dovsize = (ctrl->objtype == METIS_OBJTYPE_VOL ? 1 : 0);
632 
633  /* Check if the mask-version of the code is a good choice */
634  mask = HTLENGTH;
635  if (cnvtxs < 2*mask || graph->nedges/graph->nvtxs > mask/20) {
636  CreateCoarseGraphNoMask(ctrl, graph, cnvtxs, match);
637  return;
638  }
639 
640  nvtxs = graph->nvtxs;
641  xadj = graph->xadj;
642  for (v=0; v<nvtxs; v++) {
643  if (xadj[v+1]-xadj[v] > (mask>>3)) {
644  CreateCoarseGraphNoMask(ctrl, graph, cnvtxs, match);
645  return;
646  }
647  }
648 
649 
650  WCOREPUSH;
651 
653 
654  ncon = graph->ncon;
655  vwgt = graph->vwgt;
656  vsize = graph->vsize;
657  adjncy = graph->adjncy;
658  adjwgt = graph->adjwgt;
659  cmap = graph->cmap;
660 
661  /* Initialize the coarser graph */
662  cgraph = SetupCoarseGraph(graph, cnvtxs, dovsize);
663  cxadj = cgraph->xadj;
664  cvwgt = cgraph->vwgt;
665  cvsize = cgraph->vsize;
666  cadjncy = cgraph->adjncy;
667  cadjwgt = cgraph->adjwgt;
668 
669  htable = iset(gk_min(cnvtxs+1, mask+1), -1, iwspacemalloc(ctrl, mask+1));
670 
671  cxadj[0] = cnvtxs = cnedges = 0;
672  for (v=0; v<nvtxs; v++) {
673  if ((u = match[v]) < v)
674  continue;
675 
676  ASSERT(cmap[v] == cnvtxs);
677  ASSERT(cmap[match[v]] == cnvtxs);
678 
679  if (ncon == 1)
680  cvwgt[cnvtxs] = vwgt[v];
681  else
682  icopy(ncon, vwgt+v*ncon, cvwgt+cnvtxs*ncon);
683 
684  if (dovsize)
685  cvsize[cnvtxs] = vsize[v];
686 
687  nedges = 0;
688 
689  istart = xadj[v];
690  iend = xadj[v+1];
691  for (j=istart; j<iend; j++) {
692  k = cmap[adjncy[j]];
693  kk = k&mask;
694  if ((m = htable[kk]) == -1) {
695  cadjncy[nedges] = k;
696  cadjwgt[nedges] = adjwgt[j];
697  htable[kk] = nedges++;
698  }
699  else if (cadjncy[m] == k) {
700  cadjwgt[m] += adjwgt[j];
701  }
702  else {
703  for (jj=0; jj<nedges; jj++) {
704  if (cadjncy[jj] == k) {
705  cadjwgt[jj] += adjwgt[j];
706  break;
707  }
708  }
709  if (jj == nedges) {
710  cadjncy[nedges] = k;
711  cadjwgt[nedges++] = adjwgt[j];
712  }
713  }
714  }
715 
716  if (v != u) {
717  if (ncon == 1)
718  cvwgt[cnvtxs] += vwgt[u];
719  else
720  iaxpy(ncon, 1, vwgt+u*ncon, 1, cvwgt+cnvtxs*ncon, 1);
721 
722  if (dovsize)
723  cvsize[cnvtxs] += vsize[u];
724 
725  istart = xadj[u];
726  iend = xadj[u+1];
727  for (j=istart; j<iend; j++) {
728  k = cmap[adjncy[j]];
729  kk = k&mask;
730  if ((m = htable[kk]) == -1) {
731  cadjncy[nedges] = k;
732  cadjwgt[nedges] = adjwgt[j];
733  htable[kk] = nedges++;
734  }
735  else if (cadjncy[m] == k) {
736  cadjwgt[m] += adjwgt[j];
737  }
738  else {
739  for (jj=0; jj<nedges; jj++) {
740  if (cadjncy[jj] == k) {
741  cadjwgt[jj] += adjwgt[j];
742  break;
743  }
744  }
745  if (jj == nedges) {
746  cadjncy[nedges] = k;
747  cadjwgt[nedges++] = adjwgt[j];
748  }
749  }
750  }
751 
752  /* Remove the contracted adjacency weight */
753  jj = htable[cnvtxs&mask];
754  if (jj >= 0 && cadjncy[jj] != cnvtxs) {
755  for (jj=0; jj<nedges; jj++) {
756  if (cadjncy[jj] == cnvtxs)
757  break;
758  }
759  }
760  /* This 2nd check is needed for non-adjacent matchings */
761  if (jj >= 0 && jj < nedges && cadjncy[jj] == cnvtxs) {
762  cadjncy[jj] = cadjncy[--nedges];
763  cadjwgt[jj] = cadjwgt[nedges];
764  }
765  }
766 
767  /* Zero out the htable */
768  for (j=0; j<nedges; j++)
769  htable[cadjncy[j]&mask] = -1;
770  htable[cnvtxs&mask] = -1;
771 
772  cnedges += nedges;
773  cxadj[++cnvtxs] = cnedges;
774  cadjncy += nedges;
775  cadjwgt += nedges;
776  }
777 
778  cgraph->nedges = cnedges;
779 
780  for (j=0; j<ncon; j++) {
781  cgraph->tvwgt[j] = isum(cgraph->nvtxs, cgraph->vwgt+j, ncon);
782  cgraph->invtvwgt[j] = 1.0/(cgraph->tvwgt[j] > 0 ? cgraph->tvwgt[j] : 1);
783  }
784 
785 
786  ReAdjustMemory(ctrl, graph, cgraph);
787 
789 
790  WCOREPOP;
791 }
792 
793 
794 /*************************************************************************/
799 /*************************************************************************/
801  idx_t *match)
802 {
803  idx_t j, k, m, istart, iend, nvtxs, nedges, ncon, cnedges, v, u, dovsize;
804  idx_t *xadj, *vwgt, *vsize, *adjncy, *adjwgt;
805  idx_t *cmap, *htable;
806  idx_t *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt;
807  graph_t *cgraph;
808 
809  WCOREPUSH;
810 
811  dovsize = (ctrl->objtype == METIS_OBJTYPE_VOL ? 1 : 0);
812 
814 
815  nvtxs = graph->nvtxs;
816  ncon = graph->ncon;
817  xadj = graph->xadj;
818  vwgt = graph->vwgt;
819  vsize = graph->vsize;
820  adjncy = graph->adjncy;
821  adjwgt = graph->adjwgt;
822  cmap = graph->cmap;
823 
824 
825  /* Initialize the coarser graph */
826  cgraph = SetupCoarseGraph(graph, cnvtxs, dovsize);
827  cxadj = cgraph->xadj;
828  cvwgt = cgraph->vwgt;
829  cvsize = cgraph->vsize;
830  cadjncy = cgraph->adjncy;
831  cadjwgt = cgraph->adjwgt;
832 
833  htable = iset(cnvtxs, -1, iwspacemalloc(ctrl, cnvtxs));
834 
835  cxadj[0] = cnvtxs = cnedges = 0;
836  for (v=0; v<nvtxs; v++) {
837  if ((u = match[v]) < v)
838  continue;
839 
840  ASSERT(cmap[v] == cnvtxs);
841  ASSERT(cmap[match[v]] == cnvtxs);
842 
843  if (ncon == 1)
844  cvwgt[cnvtxs] = vwgt[v];
845  else
846  icopy(ncon, vwgt+v*ncon, cvwgt+cnvtxs*ncon);
847 
848  if (dovsize)
849  cvsize[cnvtxs] = vsize[v];
850 
851  nedges = 0;
852 
853  istart = xadj[v];
854  iend = xadj[v+1];
855  for (j=istart; j<iend; j++) {
856  k = cmap[adjncy[j]];
857  if ((m = htable[k]) == -1) {
858  cadjncy[nedges] = k;
859  cadjwgt[nedges] = adjwgt[j];
860  htable[k] = nedges++;
861  }
862  else {
863  cadjwgt[m] += adjwgt[j];
864  }
865  }
866 
867  if (v != u) {
868  if (ncon == 1)
869  cvwgt[cnvtxs] += vwgt[u];
870  else
871  iaxpy(ncon, 1, vwgt+u*ncon, 1, cvwgt+cnvtxs*ncon, 1);
872 
873  if (dovsize)
874  cvsize[cnvtxs] += vsize[u];
875 
876  istart = xadj[u];
877  iend = xadj[u+1];
878  for (j=istart; j<iend; j++) {
879  k = cmap[adjncy[j]];
880  if ((m = htable[k]) == -1) {
881  cadjncy[nedges] = k;
882  cadjwgt[nedges] = adjwgt[j];
883  htable[k] = nedges++;
884  }
885  else {
886  cadjwgt[m] += adjwgt[j];
887  }
888  }
889 
890  /* Remove the contracted adjacency weight */
891  if ((j = htable[cnvtxs]) != -1) {
892  ASSERT(cadjncy[j] == cnvtxs);
893  cadjncy[j] = cadjncy[--nedges];
894  cadjwgt[j] = cadjwgt[nedges];
895  htable[cnvtxs] = -1;
896  }
897  }
898 
899  /* Zero out the htable */
900  for (j=0; j<nedges; j++)
901  htable[cadjncy[j]] = -1;
902 
903  cnedges += nedges;
904  cxadj[++cnvtxs] = cnedges;
905  cadjncy += nedges;
906  cadjwgt += nedges;
907  }
908 
909  cgraph->nedges = cnedges;
910 
911  for (j=0; j<ncon; j++) {
912  cgraph->tvwgt[j] = isum(cgraph->nvtxs, cgraph->vwgt+j, ncon);
913  cgraph->invtvwgt[j] = 1.0/(cgraph->tvwgt[j] > 0 ? cgraph->tvwgt[j] : 1);
914  }
915 
916  ReAdjustMemory(ctrl, graph, cgraph);
917 
919 
920  WCOREPOP;
921 }
922 
923 
924 /*************************************************************************/
931 /*************************************************************************/
933  idx_t *match, idx_t *perm)
934 {
935  idx_t i, j, jj, k, kk, l, m, istart, iend, nvtxs, nedges, ncon, cnedges,
936  v, u, mask, dovsize;
937  idx_t *xadj, *vwgt, *vsize, *adjncy, *adjwgt;
938  idx_t *cmap, *htable;
939  idx_t *cxadj, *cvwgt, *cvsize, *cadjncy, *cadjwgt;
940  graph_t *cgraph;
941 
942  WCOREPUSH;
943 
945 
946  dovsize = (ctrl->objtype == METIS_OBJTYPE_VOL ? 1 : 0);
947 
948  mask = HTLENGTH;
949 
950  nvtxs = graph->nvtxs;
951  ncon = graph->ncon;
952  xadj = graph->xadj;
953  vwgt = graph->vwgt;
954  vsize = graph->vsize;
955  adjncy = graph->adjncy;
956  adjwgt = graph->adjwgt;
957  cmap = graph->cmap;
958 
959  /* Initialize the coarser graph */
960  cgraph = SetupCoarseGraph(graph, cnvtxs, dovsize);
961  cxadj = cgraph->xadj;
962  cvwgt = cgraph->vwgt;
963  cvsize = cgraph->vsize;
964  cadjncy = cgraph->adjncy;
965  cadjwgt = cgraph->adjwgt;
966 
967  htable = iset(mask+1, -1, iwspacemalloc(ctrl, mask+1));
968 
969  cxadj[0] = cnvtxs = cnedges = 0;
970  for (i=0; i<nvtxs; i++) {
971  v = perm[i];
972  if (cmap[v] != cnvtxs)
973  continue;
974 
975  u = match[v];
976  if (ncon == 1)
977  cvwgt[cnvtxs] = vwgt[v];
978  else
979  icopy(ncon, vwgt+v*ncon, cvwgt+cnvtxs*ncon);
980 
981  if (dovsize)
982  cvsize[cnvtxs] = vsize[v];
983 
984  nedges = 0;
985 
986  istart = xadj[v];
987  iend = xadj[v+1];
988  for (j=istart; j<iend; j++) {
989  k = cmap[adjncy[j]];
990  kk = k&mask;
991  if ((m = htable[kk]) == -1) {
992  cadjncy[nedges] = k;
993  cadjwgt[nedges] = adjwgt[j];
994  htable[kk] = nedges++;
995  }
996  else if (cadjncy[m] == k) {
997  cadjwgt[m] += adjwgt[j];
998  }
999  else {
1000  for (jj=0; jj<nedges; jj++) {
1001  if (cadjncy[jj] == k) {
1002  cadjwgt[jj] += adjwgt[j];
1003  break;
1004  }
1005  }
1006  if (jj == nedges) {
1007  cadjncy[nedges] = k;
1008  cadjwgt[nedges++] = adjwgt[j];
1009  }
1010  }
1011  }
1012 
1013  if (v != u) {
1014  if (ncon == 1)
1015  cvwgt[cnvtxs] += vwgt[u];
1016  else
1017  iaxpy(ncon, 1, vwgt+u*ncon, 1, cvwgt+cnvtxs*ncon, 1);
1018 
1019  if (dovsize)
1020  cvsize[cnvtxs] += vsize[u];
1021 
1022  istart = xadj[u];
1023  iend = xadj[u+1];
1024  for (j=istart; j<iend; j++) {
1025  k = cmap[adjncy[j]];
1026  kk = k&mask;
1027  if ((m = htable[kk]) == -1) {
1028  cadjncy[nedges] = k;
1029  cadjwgt[nedges] = adjwgt[j];
1030  htable[kk] = nedges++;
1031  }
1032  else if (cadjncy[m] == k) {
1033  cadjwgt[m] += adjwgt[j];
1034  }
1035  else {
1036  for (jj=0; jj<nedges; jj++) {
1037  if (cadjncy[jj] == k) {
1038  cadjwgt[jj] += adjwgt[j];
1039  break;
1040  }
1041  }
1042  if (jj == nedges) {
1043  cadjncy[nedges] = k;
1044  cadjwgt[nedges++] = adjwgt[j];
1045  }
1046  }
1047  }
1048 
1049  /* Remove the contracted adjacency weight */
1050  jj = htable[cnvtxs&mask];
1051  if (jj >= 0 && cadjncy[jj] != cnvtxs) {
1052  for (jj=0; jj<nedges; jj++) {
1053  if (cadjncy[jj] == cnvtxs)
1054  break;
1055  }
1056  }
1057  if (jj >= 0 && cadjncy[jj] == cnvtxs) { /* This 2nd check is needed for non-adjacent matchings */
1058  cadjncy[jj] = cadjncy[--nedges];
1059  cadjwgt[jj] = cadjwgt[nedges];
1060  }
1061  }
1062 
1063  for (j=0; j<nedges; j++)
1064  htable[cadjncy[j]&mask] = -1; /* Zero out the htable */
1065  htable[cnvtxs&mask] = -1;
1066 
1067  cnedges += nedges;
1068  cxadj[++cnvtxs] = cnedges;
1069  cadjncy += nedges;
1070  cadjwgt += nedges;
1071  }
1072 
1073  cgraph->nedges = cnedges;
1074 
1075  for (i=0; i<ncon; i++) {
1076  cgraph->tvwgt[i] = isum(cgraph->nvtxs, cgraph->vwgt+i, ncon);
1077  cgraph->invtvwgt[i] = 1.0/(cgraph->tvwgt[i] > 0 ? cgraph->tvwgt[i] : 1);
1078  }
1079 
1080 
1081  ReAdjustMemory(ctrl, graph, cgraph);
1082 
1084 
1085  WCOREPOP;
1086 }
1087 
1088 
1089 /*************************************************************************/
1092 /*************************************************************************/
1094 {
1095  graph_t *cgraph;
1096 
1097  cgraph = CreateGraph();
1098 
1099  cgraph->nvtxs = cnvtxs;
1100  cgraph->ncon = graph->ncon;
1101 
1102  cgraph->finer = graph;
1103  graph->coarser = cgraph;
1104 
1105 
1106  /* Allocate memory for the coarser graph */
1107  cgraph->xadj = imalloc(cnvtxs+1, "SetupCoarseGraph: xadj");
1108  cgraph->adjncy = imalloc(graph->nedges, "SetupCoarseGraph: adjncy");
1109  cgraph->adjwgt = imalloc(graph->nedges, "SetupCoarseGraph: adjwgt");
1110  cgraph->vwgt = imalloc(cgraph->ncon*cnvtxs, "SetupCoarseGraph: vwgt");
1111  cgraph->tvwgt = imalloc(cgraph->ncon, "SetupCoarseGraph: tvwgt");
1112  cgraph->invtvwgt = rmalloc(cgraph->ncon, "SetupCoarseGraph: invtvwgt");
1113 
1114  if (dovsize)
1115  cgraph->vsize = imalloc(cnvtxs, "SetupCoarseGraph: vsize");
1116 
1117  return cgraph;
1118 }
1119 
1120 
1121 /*************************************************************************/
1125 /*************************************************************************/
1126 void ReAdjustMemory(ctrl_t *ctrl, graph_t *graph, graph_t *cgraph)
1127 {
1128  if (cgraph->nedges > 10000 && cgraph->nedges < 0.9*graph->nedges) {
1129  cgraph->adjncy = irealloc(cgraph->adjncy, cgraph->nedges, "ReAdjustMemory: adjncy");
1130  cgraph->adjwgt = irealloc(cgraph->adjwgt, cgraph->nedges, "ReAdjustMemory: adjwgt");
1131  }
1132 }
graph_t::tvwgt
idx_t * tvwgt
Definition: libmetis/struct.h:91
ctrl_t::ContractTmr
double ContractTmr
Definition: libmetis/struct.h:176
perm
idx_t idx_t idx_t idx_t idx_t * perm
Definition: include/metis.h:223
irealloc
#define irealloc
Definition: gklib_rename.h:65
Match_RM
idx_t Match_RM(ctrl_t *ctrl, graph_t *graph)
Definition: coarsen.c:149
adjwgt
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
Definition: include/metis.h:198
CreateGraph
#define CreateGraph
Definition: rename.h:95
graph_t::vwgt
idx_t * vwgt
Definition: libmetis/struct.h:86
keys
const KeyVector keys
Definition: testRegularImplicitSchurFactor.cpp:40
graph_t::invtvwgt
real_t * invtvwgt
Definition: libmetis/struct.h:92
vsize
idx_t idx_t idx_t idx_t idx_t * vsize
Definition: include/metis.h:198
CoarsenGraphNlevels
graph_t * CoarsenGraphNlevels(ctrl_t *ctrl, graph_t *graph, idx_t nlevels)
Definition: coarsen.c:85
CheckGraph
#define CheckGraph
Definition: rename.h:30
ctrl_t
Definition: libmetis/struct.h:139
graph_t::xadj
idx_t * xadj
Definition: libmetis/struct.h:85
adjncy
idx_t idx_t idx_t * adjncy
Definition: include/metis.h:198
gk_min
#define gk_min(a, b)
Definition: gk_macros.h:17
imalloc
#define imalloc
Definition: gklib_rename.h:42
graph_t::adjwgt
idx_t * adjwgt
Definition: libmetis/struct.h:89
CreateCoarseGraphNoMask
void CreateCoarseGraphNoMask(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, idx_t *match)
Definition: coarsen.c:800
graph_t::nedges
idx_t nedges
Definition: libmetis/struct.h:83
METIS_CTYPE_SHEM
@ METIS_CTYPE_SHEM
Definition: include/metis.h:316
IFSET
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
COARSEN_FRACTION
#define COARSEN_FRACTION
Definition: libmetis/defs.h:45
ikvwspacemalloc
#define ikvwspacemalloc
Definition: rename.h:258
ikvsorti
#define ikvsorti
Definition: gklib_rename.h:40
ivecaxpylez
#define ivecaxpylez
Definition: rename.h:138
BucketSortKeysInc
#define BucketSortKeysInc
Definition: rename.h:27
ctrl_t::MatchTmr
double MatchTmr
Definition: libmetis/struct.h:176
ncon
idx_t * ncon
Definition: include/metis.h:197
PrintCGraphStats
void PrintCGraphStats(ctrl_t *ctrl, graph_t *graph)
Definition: coarsen.c:601
gk_startcputimer
#define gk_startcputimer(tmr)
Definition: gk_macros.h:33
match
bool match(const T &xpr, std::string ref, std::string str_xpr="")
Definition: indexed_view.cpp:54
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
ctrl_t::Aux3Tmr
double Aux3Tmr
Definition: libmetis/struct.h:177
ivecle
#define ivecle
Definition: rename.h:136
ctrl_t::CoarsenTmr
double CoarsenTmr
Definition: libmetis/struct.h:176
iaxpy
#define iaxpy
Definition: gklib_rename.h:27
UNMATCHED
#define UNMATCHED
Definition: libmetis/defs.h:40
ReAdjustMemory
void ReAdjustMemory(ctrl_t *ctrl, graph_t *graph, graph_t *cgraph)
Definition: coarsen.c:1126
l
static const Line3 l(Rot3(), 1, 1)
METIS_DBG_COARSEN
@ METIS_DBG_COARSEN
Definition: include/metis.h:342
ctrl_t::objtype
mobjtype_et objtype
Definition: libmetis/struct.h:141
Match_2HopAny
idx_t Match_2HopAny(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree)
Definition: coarsen.c:437
ctrl_t::CoarsenTo
idx_t CoarsenTo
Definition: libmetis/struct.h:147
graph_t::vsize
idx_t * vsize
Definition: libmetis/struct.h:87
WCOREPUSH
#define WCOREPUSH
Definition: metis/libmetis/macros.h:38
SIGERR
#define SIGERR
Definition: gk_defs.h:38
graph_t::nvtxs
idx_t nvtxs
Definition: libmetis/struct.h:83
ctrl_t::maxvwgt
idx_t * maxvwgt
Definition: libmetis/struct.h:160
gtsam.examples.SFMExample_bal.level
level
Definition: SFMExample_bal.py:24
m
Matrix3f m
Definition: AngleAxis_mimic_euler.cpp:1
METIS_CTYPE_RM
@ METIS_CTYPE_RM
Definition: include/metis.h:315
vwgt
idx_t idx_t idx_t idx_t * vwgt
Definition: include/metis.h:198
Match_2HopAll
idx_t Match_2HopAll(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, idx_t cnvtxs, size_t *r_nunmatched, size_t maxdegree)
Definition: coarsen.c:516
CreateCoarseGraph
void CreateCoarseGraph(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, idx_t *match)
Definition: coarsen.c:621
key
const gtsam::Symbol key('X', 0)
ASSERT
#define ASSERT(expression)
Definition: ccolamd.c:872
graph_t::finer
struct graph_t * finer
Definition: libmetis/struct.h:119
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
Match_2Hop
idx_t Match_2Hop(ctrl_t *ctrl, graph_t *graph, idx_t *perm, idx_t *match, idx_t cnvtxs, size_t nunmatched)
Definition: coarsen.c:415
SHIFTCSR
#define SHIFTCSR(i, n, a)
Definition: gk_macros.h:80
graph_t::ncon
idx_t ncon
Definition: libmetis/struct.h:84
SetupCoarseGraph
graph_t * SetupCoarseGraph(graph_t *graph, idx_t cnvtxs, idx_t dovsize)
Definition: coarsen.c:1093
iset
#define iset
Definition: gklib_rename.h:67
isum
#define isum
Definition: gklib_rename.h:72
v
Array< int, Dynamic, 1 > v
Definition: Array_initializer_list_vector_cxx11.cpp:1
PRIDX
#define PRIDX
Definition: include/metis.h:107
METIS_OBJTYPE_VOL
@ METIS_OBJTYPE_VOL
Definition: include/metis.h:356
BetterVBalance
#define BetterVBalance
Definition: rename.h:140
graph_t::adjncy
idx_t * adjncy
Definition: libmetis/struct.h:88
Match_SHEM
idx_t Match_SHEM(ctrl_t *ctrl, graph_t *graph)
Definition: coarsen.c:276
ctrl_t::ctype
mctype_et ctype
Definition: libmetis/struct.h:143
MAKECSR
#define MAKECSR(i, n, a)
Definition: gk_macros.h:73
CreateCoarseGraphPerm
void CreateCoarseGraphPerm(ctrl_t *ctrl, graph_t *graph, idx_t cnvtxs, idx_t *match, idx_t *perm)
Definition: coarsen.c:932
ctrl_t::dbglvl
mdbglvl_et dbglvl
Definition: libmetis/struct.h:142
NULL
#define NULL
Definition: ccolamd.c:609
metislib.h
WCOREPOP
#define WCOREPOP
Definition: metis/libmetis/macros.h:39
ctrl_t::no2hop
idx_t no2hop
Definition: libmetis/struct.h:149
UNMATCHEDFOR2HOP
#define UNMATCHEDFOR2HOP
Definition: coarsen.c:14
icopy
#define icopy
Definition: gklib_rename.h:28
IDX_MAX
#define IDX_MAX
Definition: include/metis.h:103
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
rmalloc
#define rmalloc
Definition: gklib_rename.h:93
gk_max
#define gk_max(a, b)
Definition: gk_macros.h:16
iwspacemalloc
#define iwspacemalloc
Definition: rename.h:256
irandArrayPermute
#define irandArrayPermute
Definition: gklib_rename.h:62
CoarsenGraph
graph_t * CoarsenGraph(ctrl_t *ctrl, graph_t *graph)
Definition: coarsen.c:22
gk_stopcputimer
#define gk_stopcputimer(tmr)
Definition: gk_macros.h:34
HTLENGTH
#define HTLENGTH
Definition: libmetis/defs.h:23
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
gk_errexit
void gk_errexit(int signum, char *f_str,...)
Definition: error.c:76
for
for(size_t i=1;i< poses.size();++i)
Definition: doc/Code/VisualISAMExample.cpp:7
graph_t
Definition: libmetis/struct.h:82
idx_t
int32_t idx_t
Definition: include/metis.h:101
METIS_DBG_TIME
@ METIS_DBG_TIME
Definition: include/metis.h:341


gtsam
Author(s):
autogenerated on Sat Nov 16 2024 04:01:59