Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
ometis.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * ometis.c
5  *
6  * This file contains the top level routines for the multilevel recursive
7  * bisection algorithm PMETIS.
8  *
9  * Started 7/24/97
10  * George
11  *
12  * $Id: ometis.c,v 1.1 1998/11/27 17:59:27 karypis Exp $
13  *
14  */
15 
16 #include <metis.h>
17 
18 
19 /*************************************************************************
20 * This function is the entry point for OEMETIS
21 **************************************************************************/
22 void METIS_EdgeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options,
23  idxtype *perm, idxtype *iperm)
24 {
25  int i, j;
27  CtrlType ctrl;
28 
29  if (*numflag == 1)
30  Change2CNumbering(*nvtxs, xadj, adjncy);
31 
32  SetUpGraph(&graph, OP_OEMETIS, *nvtxs, 1, xadj, adjncy, NULL, NULL, 0);
33 
34  if (options[0] == 0) { /* Use the default parameters */
35  ctrl.CType = OEMETIS_CTYPE;
36  ctrl.IType = OEMETIS_ITYPE;
37  ctrl.RType = OEMETIS_RTYPE;
38  ctrl.dbglvl = OEMETIS_DBGLVL;
39  }
40  else {
41  ctrl.CType = options[OPTION_CTYPE];
42  ctrl.IType = options[OPTION_ITYPE];
43  ctrl.RType = options[OPTION_RTYPE];
44  ctrl.dbglvl = options[OPTION_DBGLVL];
45  }
46  ctrl.oflags = 0;
47  ctrl.pfactor = -1;
48  ctrl.nseps = 1;
49 
50  ctrl.optype = OP_OEMETIS;
51  ctrl.CoarsenTo = 20;
52  ctrl.maxvwgt = 1.5*(idxsum(*nvtxs, graph.vwgt)/ctrl.CoarsenTo);
53 
54  InitRandom(-1);
55 
56  AllocateWorkSpace(&ctrl, &graph, 2);
57 
58  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
59  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
60 
61  MlevelNestedDissection(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, *nvtxs);
62 
63  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
64  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
65 
66  for (i=0; i<*nvtxs; i++)
67  perm[iperm[i]] = i;
68 
69  FreeWorkSpace(&ctrl, &graph);
70 
71  if (*numflag == 1)
72  Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);
73 }
74 
75 
76 /*************************************************************************
77 * This function is the entry point for ONCMETIS
78 **************************************************************************/
79 void METIS_NodeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options,
80  idxtype *perm, idxtype *iperm)
81 {
82  int i, ii, j, l, wflag, nflag;
84  CtrlType ctrl;
85  idxtype *cptr, *cind, *piperm;
86 
87  if (*numflag == 1)
88  Change2CNumbering(*nvtxs, xadj, adjncy);
89 
90  if (options[0] == 0) { /* Use the default parameters */
91  ctrl.CType = ONMETIS_CTYPE;
92  ctrl.IType = ONMETIS_ITYPE;
93  ctrl.RType = ONMETIS_RTYPE;
94  ctrl.dbglvl = ONMETIS_DBGLVL;
95  ctrl.oflags = ONMETIS_OFLAGS;
96  ctrl.pfactor = ONMETIS_PFACTOR;
97  ctrl.nseps = ONMETIS_NSEPS;
98  }
99  else {
100  ctrl.CType = options[OPTION_CTYPE];
101  ctrl.IType = options[OPTION_ITYPE];
102  ctrl.RType = options[OPTION_RTYPE];
103  ctrl.dbglvl = options[OPTION_DBGLVL];
104  ctrl.oflags = options[OPTION_OFLAGS];
105  ctrl.pfactor = options[OPTION_PFACTOR];
106  ctrl.nseps = options[OPTION_NSEPS];
107  }
108  if (ctrl.nseps < 1)
109  ctrl.nseps = 1;
110 
111  ctrl.optype = OP_ONMETIS;
112  ctrl.CoarsenTo = 100;
113 
114  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
115  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
116 
117  InitRandom(-1);
118 
119  if (ctrl.pfactor > 0) {
120  /*============================================================
121  * Prune the dense columns
122  ==============================================================*/
123  piperm = idxmalloc(*nvtxs, "ONMETIS: piperm");
124 
125  PruneGraph(&ctrl, &graph, *nvtxs, xadj, adjncy, piperm, (float)(0.1*ctrl.pfactor));
126  }
127  else if (ctrl.oflags&OFLAG_COMPRESS) {
128  /*============================================================
129  * Compress the graph
130  ==============================================================*/
131  cptr = idxmalloc(*nvtxs+1, "ONMETIS: cptr");
132  cind = idxmalloc(*nvtxs, "ONMETIS: cind");
133 
134  CompressGraph(&ctrl, &graph, *nvtxs, xadj, adjncy, cptr, cind);
135 
136  if (graph.nvtxs >= COMPRESSION_FRACTION*(*nvtxs)) {
137  ctrl.oflags--; /* We actually performed no compression */
138  GKfree(&cptr, &cind, LTERM);
139  }
140  else if (2*graph.nvtxs < *nvtxs && ctrl.nseps == 1)
141  ctrl.nseps = 2;
142  }
143  else {
144  SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, NULL, NULL, 0);
145  }
146 
147 
148  /*=============================================================
149  * Do the nested dissection ordering
150  --=============================================================*/
151  ctrl.maxvwgt = 1.5*(idxsum(graph.nvtxs, graph.vwgt)/ctrl.CoarsenTo);
152  AllocateWorkSpace(&ctrl, &graph, 2);
153 
154  if (ctrl.oflags&OFLAG_CCMP)
155  MlevelNestedDissectionCC(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, graph.nvtxs);
156  else
157  MlevelNestedDissection(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, graph.nvtxs);
158 
159  FreeWorkSpace(&ctrl, &graph);
160 
161  if (ctrl.pfactor > 0) { /* Order any prunned vertices */
162  if (graph.nvtxs < *nvtxs) {
163  idxcopy(graph.nvtxs, iperm, perm); /* Use perm as an auxiliary array */
164  for (i=0; i<graph.nvtxs; i++)
165  iperm[piperm[i]] = perm[i];
166  for (i=graph.nvtxs; i<*nvtxs; i++)
167  iperm[piperm[i]] = i;
168  }
169 
170  GKfree(&piperm, LTERM);
171  }
172  else if (ctrl.oflags&OFLAG_COMPRESS) { /* Uncompress the ordering */
173  if (graph.nvtxs < COMPRESSION_FRACTION*(*nvtxs)) {
174  /* construct perm from iperm */
175  for (i=0; i<graph.nvtxs; i++)
176  perm[iperm[i]] = i;
177  for (l=ii=0; ii<graph.nvtxs; ii++) {
178  i = perm[ii];
179  for (j=cptr[i]; j<cptr[i+1]; j++)
180  iperm[cind[j]] = l++;
181  }
182  }
183 
184  GKfree(&cptr, &cind, LTERM);
185  }
186 
187 
188  for (i=0; i<*nvtxs; i++)
189  perm[iperm[i]] = i;
190 
191  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
192  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
193 
194  if (*numflag == 1)
195  Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);
196 
197 }
198 
199 
200 /*************************************************************************
201 * This function is the entry point for ONWMETIS. It requires weights on the
202 * vertices. It is for the case that the matrix has been pre-compressed.
203 **************************************************************************/
204 void METIS_NodeWND(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, int *numflag,
205  int *options, idxtype *perm, idxtype *iperm)
206 {
207  int i, j, tvwgt;
209  CtrlType ctrl;
210 
211  if (*numflag == 1)
212  Change2CNumbering(*nvtxs, xadj, adjncy);
213 
214  SetUpGraph(&graph, OP_ONMETIS, *nvtxs, 1, xadj, adjncy, vwgt, NULL, 2);
215 
216  if (options[0] == 0) { /* Use the default parameters */
217  ctrl.CType = ONMETIS_CTYPE;
218  ctrl.IType = ONMETIS_ITYPE;
219  ctrl.RType = ONMETIS_RTYPE;
220  ctrl.dbglvl = ONMETIS_DBGLVL;
221  }
222  else {
223  ctrl.CType = options[OPTION_CTYPE];
224  ctrl.IType = options[OPTION_ITYPE];
225  ctrl.RType = options[OPTION_RTYPE];
226  ctrl.dbglvl = options[OPTION_DBGLVL];
227  }
228 
229  ctrl.oflags = OFLAG_COMPRESS;
230  ctrl.pfactor = 0;
231  ctrl.nseps = 2;
232  ctrl.optype = OP_ONMETIS;
233  ctrl.CoarsenTo = 100;
234  ctrl.maxvwgt = 1.5*(idxsum(*nvtxs, graph.vwgt)/ctrl.CoarsenTo);
235 
236  InitRandom(-1);
237 
238  AllocateWorkSpace(&ctrl, &graph, 2);
239 
240  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
241  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
242 
243  MlevelNestedDissection(&ctrl, &graph, iperm, ORDER_UNBALANCE_FRACTION, *nvtxs);
244 
245  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
246  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
247 
248  for (i=0; i<*nvtxs; i++)
249  perm[iperm[i]] = i;
250 
251  FreeWorkSpace(&ctrl, &graph);
252 
253  if (*numflag == 1)
254  Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);
255 }
256 
257 
258 
259 
260 /*************************************************************************
261 * This function takes a graph and produces a bisection of it
262 **************************************************************************/
263 void MlevelNestedDissection(CtrlType *ctrl, GraphType *graph, idxtype *order, float ubfactor, int lastvtx)
264 {
265  int i, j, nvtxs, nbnd, tvwgt, tpwgts2[2];
266  idxtype *label, *bndind;
267  GraphType lgraph, rgraph;
268 
269  nvtxs = graph->nvtxs;
270 
271  /* Determine the weights of the partitions */
272  tvwgt = idxsum(nvtxs, graph->vwgt);
273  tpwgts2[0] = tvwgt/2;
274  tpwgts2[1] = tvwgt-tpwgts2[0];
275 
276  switch (ctrl->optype) {
277  case OP_OEMETIS:
278  MlevelEdgeBisection(ctrl, graph, tpwgts2, ubfactor);
279 
280  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SepTmr));
281  ConstructMinCoverSeparator(ctrl, graph, ubfactor);
282  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SepTmr));
283 
284  break;
285  case OP_ONMETIS:
286  MlevelNodeBisectionMultiple(ctrl, graph, tpwgts2, ubfactor);
287 
288  IFSET(ctrl->dbglvl, DBG_SEPINFO, printf("Nvtxs: %6d, [%6d %6d %6d]\n", graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
289 
290  break;
291  }
292 
293  /* Order the nodes in the separator */
294  nbnd = graph->nbnd;
295  bndind = graph->bndind;
296  label = graph->label;
297  for (i=0; i<nbnd; i++)
298  order[label[bndind[i]]] = --lastvtx;
299 
300  SplitGraphOrder(ctrl, graph, &lgraph, &rgraph);
301 
302  /* Free the memory of the top level graph */
303  GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
304 
305  if (rgraph.nvtxs > MMDSWITCH)
306  MlevelNestedDissection(ctrl, &rgraph, order, ubfactor, lastvtx);
307  else {
308  MMDOrder(ctrl, &rgraph, order, lastvtx);
309  GKfree(&rgraph.gdata, &rgraph.rdata, &rgraph.label, LTERM);
310  }
311  if (lgraph.nvtxs > MMDSWITCH)
312  MlevelNestedDissection(ctrl, &lgraph, order, ubfactor, lastvtx-rgraph.nvtxs);
313  else {
314  MMDOrder(ctrl, &lgraph, order, lastvtx-rgraph.nvtxs);
315  GKfree(&lgraph.gdata, &lgraph.rdata, &lgraph.label, LTERM);
316  }
317 }
318 
319 
320 /*************************************************************************
321 * This function takes a graph and produces a bisection of it
322 **************************************************************************/
323 void MlevelNestedDissectionCC(CtrlType *ctrl, GraphType *graph, idxtype *order, float ubfactor, int lastvtx)
324 {
325  int i, j, nvtxs, nbnd, tvwgt, tpwgts2[2], nsgraphs, ncmps, rnvtxs;
326  idxtype *label, *bndind;
327  idxtype *cptr, *cind;
328  GraphType *sgraphs;
329 
330  nvtxs = graph->nvtxs;
331 
332  /* Determine the weights of the partitions */
333  tvwgt = idxsum(nvtxs, graph->vwgt);
334  tpwgts2[0] = tvwgt/2;
335  tpwgts2[1] = tvwgt-tpwgts2[0];
336 
337  MlevelNodeBisectionMultiple(ctrl, graph, tpwgts2, ubfactor);
338  IFSET(ctrl->dbglvl, DBG_SEPINFO, printf("Nvtxs: %6d, [%6d %6d %6d]\n", graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
339 
340  /* Order the nodes in the separator */
341  nbnd = graph->nbnd;
342  bndind = graph->bndind;
343  label = graph->label;
344  for (i=0; i<nbnd; i++)
345  order[label[bndind[i]]] = --lastvtx;
346 
347  cptr = idxmalloc(nvtxs, "MlevelNestedDissectionCC: cptr");
348  cind = idxmalloc(nvtxs, "MlevelNestedDissectionCC: cind");
349  ncmps = FindComponents(ctrl, graph, cptr, cind);
350 
351 /*
352  if (ncmps > 2)
353  printf("[%5d] has %3d components\n", nvtxs, ncmps);
354 */
355 
356  sgraphs = (GraphType *)GKmalloc(ncmps*sizeof(GraphType), "MlevelNestedDissectionCC: sgraphs");
357 
358  nsgraphs = SplitGraphOrderCC(ctrl, graph, sgraphs, ncmps, cptr, cind);
359 
360  GKfree(&cptr, &cind, LTERM);
361 
362  /* Free the memory of the top level graph */
363  GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
364 
365  /* Go and process the subgraphs */
366  for (rnvtxs=i=0; i<nsgraphs; i++) {
367  if (sgraphs[i].adjwgt == NULL) {
368  MMDOrder(ctrl, sgraphs+i, order, lastvtx-rnvtxs);
369  GKfree(&sgraphs[i].gdata, &sgraphs[i].label, LTERM);
370  }
371  else {
372  MlevelNestedDissectionCC(ctrl, sgraphs+i, order, ubfactor, lastvtx-rnvtxs);
373  }
374  rnvtxs += sgraphs[i].nvtxs;
375  }
376 
377  free(sgraphs);
378 }
379 
380 
381 
382 /*************************************************************************
383 * This function performs multilevel bisection. It performs multiple
384 * bisections and selects the best.
385 **************************************************************************/
386 void MlevelNodeBisectionMultiple(CtrlType *ctrl, GraphType *graph, int *tpwgts, float ubfactor)
387 {
388  int i, nvtxs, cnvtxs, mincut, tmp;
389  GraphType *cgraph;
390  idxtype *bestwhere;
391 
392  if (ctrl->nseps == 1 || graph->nvtxs < (ctrl->oflags&OFLAG_COMPRESS ? 1000 : 2000)) {
393  MlevelNodeBisection(ctrl, graph, tpwgts, ubfactor);
394  return;
395  }
396 
397  nvtxs = graph->nvtxs;
398 
399  if (ctrl->oflags&OFLAG_COMPRESS) { /* Multiple separators at the original graph */
400  bestwhere = idxmalloc(nvtxs, "MlevelNodeBisection2: bestwhere");
401  mincut = nvtxs;
402 
403  for (i=ctrl->nseps; i>0; i--) {
404  MlevelNodeBisection(ctrl, graph, tpwgts, ubfactor);
405 
406  /* printf("%5d ", cgraph->mincut); */
407 
408  if (graph->mincut < mincut) {
409  mincut = graph->mincut;
410  idxcopy(nvtxs, graph->where, bestwhere);
411  }
412 
413  GKfree(&graph->rdata, LTERM);
414 
415  if (mincut == 0)
416  break;
417  }
418  /* printf("[%5d]\n", mincut); */
419 
420  Allocate2WayNodePartitionMemory(ctrl, graph);
421  idxcopy(nvtxs, bestwhere, graph->where);
422  free(bestwhere);
423 
424  Compute2WayNodePartitionParams(ctrl, graph);
425  }
426  else { /* Coarsen it a bit */
427  ctrl->CoarsenTo = nvtxs-1;
428 
429  cgraph = Coarsen2Way(ctrl, graph);
430 
431  cnvtxs = cgraph->nvtxs;
432 
433  bestwhere = idxmalloc(cnvtxs, "MlevelNodeBisection2: bestwhere");
434  mincut = nvtxs;
435 
436  for (i=ctrl->nseps; i>0; i--) {
437  ctrl->CType += 20; /* This is a hack. Look at coarsen.c */
438  MlevelNodeBisection(ctrl, cgraph, tpwgts, ubfactor);
439 
440  /* printf("%5d ", cgraph->mincut); */
441 
442  if (cgraph->mincut < mincut) {
443  mincut = cgraph->mincut;
444  idxcopy(cnvtxs, cgraph->where, bestwhere);
445  }
446 
447  GKfree(&cgraph->rdata, LTERM);
448 
449  if (mincut == 0)
450  break;
451  }
452  /* printf("[%5d]\n", mincut); */
453 
454  Allocate2WayNodePartitionMemory(ctrl, cgraph);
455  idxcopy(cnvtxs, bestwhere, cgraph->where);
456  free(bestwhere);
457 
458  Compute2WayNodePartitionParams(ctrl, cgraph);
459 
460  Refine2WayNode(ctrl, graph, cgraph, ubfactor);
461  }
462 
463 }
464 
465 /*************************************************************************
466 * This function performs multilevel bisection
467 **************************************************************************/
468 void MlevelNodeBisection(CtrlType *ctrl, GraphType *graph, int *tpwgts, float ubfactor)
469 {
470  GraphType *cgraph;
471 
472  ctrl->CoarsenTo = graph->nvtxs/8;
473  if (ctrl->CoarsenTo > 100)
474  ctrl->CoarsenTo = 100;
475  else if (ctrl->CoarsenTo < 40)
476  ctrl->CoarsenTo = 40;
477  ctrl->maxvwgt = 1.5*((tpwgts[0]+tpwgts[1])/ctrl->CoarsenTo);
478 
479  cgraph = Coarsen2Way(ctrl, graph);
480 
481  switch (ctrl->IType) {
482  case IPART_GGPKL:
483  Init2WayPartition(ctrl, cgraph, tpwgts, ubfactor);
484 
485  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SepTmr));
486 
487  Compute2WayPartitionParams(ctrl, cgraph);
488  ConstructSeparator(ctrl, cgraph, ubfactor);
489 
490  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SepTmr));
491  break;
492  case IPART_GGPKLNODE:
493  InitSeparator(ctrl, cgraph, ubfactor);
494  break;
495  }
496 
497  Refine2WayNode(ctrl, graph, cgraph, ubfactor);
498 
499 }
500 
501 
502 
503 
504 /*************************************************************************
505 * This function takes a graph and a bisection and splits it into two graphs.
506 * This function relies on the fact that adjwgt is all equal to 1.
507 **************************************************************************/
509 {
510  int i, ii, j, k, l, istart, iend, mypart, nvtxs, snvtxs[3], snedges[3];
511  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *adjwgtsum, *label, *where, *bndptr, *bndind;
512  idxtype *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *sadjwgtsum[2], *slabel[2];
513  idxtype *rename;
514  idxtype *auxadjncy, *auxadjwgt;
515 
516  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SplitTmr));
517 
518  nvtxs = graph->nvtxs;
519  xadj = graph->xadj;
520  vwgt = graph->vwgt;
521  adjncy = graph->adjncy;
522  adjwgt = graph->adjwgt;
523  adjwgtsum = graph->adjwgtsum;
524  label = graph->label;
525  where = graph->where;
526  bndptr = graph->bndptr;
527  bndind = graph->bndind;
528  ASSERT(bndptr != NULL);
529 
530  rename = idxwspacemalloc(ctrl, nvtxs);
531 
532  snvtxs[0] = snvtxs[1] = snvtxs[2] = snedges[0] = snedges[1] = snedges[2] = 0;
533  for (i=0; i<nvtxs; i++) {
534  k = where[i];
535  rename[i] = snvtxs[k]++;
536  snedges[k] += xadj[i+1]-xadj[i];
537  }
538 
539  SetUpSplitGraph(graph, lgraph, snvtxs[0], snedges[0]);
540  sxadj[0] = lgraph->xadj;
541  svwgt[0] = lgraph->vwgt;
542  sadjwgtsum[0] = lgraph->adjwgtsum;
543  sadjncy[0] = lgraph->adjncy;
544  sadjwgt[0] = lgraph->adjwgt;
545  slabel[0] = lgraph->label;
546 
547  SetUpSplitGraph(graph, rgraph, snvtxs[1], snedges[1]);
548  sxadj[1] = rgraph->xadj;
549  svwgt[1] = rgraph->vwgt;
550  sadjwgtsum[1] = rgraph->adjwgtsum;
551  sadjncy[1] = rgraph->adjncy;
552  sadjwgt[1] = rgraph->adjwgt;
553  slabel[1] = rgraph->label;
554 
555  /* Go and use bndptr to also mark the boundary nodes in the two partitions */
556  for (ii=0; ii<graph->nbnd; ii++) {
557  i = bndind[ii];
558  for (j=xadj[i]; j<xadj[i+1]; j++)
559  bndptr[adjncy[j]] = 1;
560  }
561 
562  snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
563  sxadj[0][0] = sxadj[1][0] = 0;
564  for (i=0; i<nvtxs; i++) {
565  if ((mypart = where[i]) == 2)
566  continue;
567 
568  istart = xadj[i];
569  iend = xadj[i+1];
570  if (bndptr[i] == -1) { /* This is an interior vertex */
571  auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
572  for(j=istart; j<iend; j++)
573  auxadjncy[j] = adjncy[j];
574  snedges[mypart] += iend-istart;
575  }
576  else {
577  auxadjncy = sadjncy[mypart];
578  l = snedges[mypart];
579  for (j=istart; j<iend; j++) {
580  k = adjncy[j];
581  if (where[k] == mypart)
582  auxadjncy[l++] = k;
583  }
584  snedges[mypart] = l;
585  }
586 
587  svwgt[mypart][snvtxs[mypart]] = vwgt[i];
588  sadjwgtsum[mypart][snvtxs[mypart]] = snedges[mypart]-sxadj[mypart][snvtxs[mypart]];
589  slabel[mypart][snvtxs[mypart]] = label[i];
590  sxadj[mypart][++snvtxs[mypart]] = snedges[mypart];
591  }
592 
593  for (mypart=0; mypart<2; mypart++) {
594  iend = snedges[mypart];
595  idxset(iend, 1, sadjwgt[mypart]);
596 
597  auxadjncy = sadjncy[mypart];
598  for (i=0; i<iend; i++)
599  auxadjncy[i] = rename[auxadjncy[i]];
600  }
601 
602  lgraph->nvtxs = snvtxs[0];
603  lgraph->nedges = snedges[0];
604  rgraph->nvtxs = snvtxs[1];
605  rgraph->nedges = snedges[1];
606 
607  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SplitTmr));
608 
609  idxwspacefree(ctrl, nvtxs);
610 
611 }
612 
613 /*************************************************************************
614 * This function uses MMD to order the graph. The vertices are numbered
615 * from lastvtx downwards
616 **************************************************************************/
617 void MMDOrder(CtrlType *ctrl, GraphType *graph, idxtype *order, int lastvtx)
618 {
619  int i, j, k, nvtxs, nofsub, firstvtx;
620  idxtype *xadj, *adjncy, *label;
621  idxtype *perm, *iperm, *head, *qsize, *list, *marker;
622 
623  nvtxs = graph->nvtxs;
624  xadj = graph->xadj;
625  adjncy = graph->adjncy;
626 
627  /* Relabel the vertices so that it starts from 1 */
628  k = xadj[nvtxs];
629  for (i=0; i<k; i++)
630  adjncy[i]++;
631  for (i=0; i<nvtxs+1; i++)
632  xadj[i]++;
633 
634  perm = idxmalloc(6*(nvtxs+5), "MMDOrder: perm");
635  iperm = perm + nvtxs + 5;
636  head = iperm + nvtxs + 5;
637  qsize = head + nvtxs + 5;
638  list = qsize + nvtxs + 5;
639  marker = list + nvtxs + 5;
640 
641  genmmd(nvtxs, xadj, adjncy, iperm, perm, 1, head, qsize, list, marker, MAXIDX, &nofsub);
642 
643  label = graph->label;
644  firstvtx = lastvtx-nvtxs;
645  for (i=0; i<nvtxs; i++)
646  order[label[i]] = firstvtx+iperm[i]-1;
647 
648  free(perm);
649 
650  /* Relabel the vertices so that it starts from 0 */
651  for (i=0; i<nvtxs+1; i++)
652  xadj[i]--;
653  k = xadj[nvtxs];
654  for (i=0; i<k; i++)
655  adjncy[i]--;
656 }
657 
658 
659 /*************************************************************************
660 * This function takes a graph and a bisection and splits it into two graphs.
661 * It relies on the fact that adjwgt is all set to 1.
662 **************************************************************************/
663 int SplitGraphOrderCC(CtrlType *ctrl, GraphType *graph, GraphType *sgraphs, int ncmps, idxtype *cptr, idxtype *cind)
664 {
665  int i, ii, iii, j, k, l, istart, iend, mypart, nvtxs, snvtxs, snedges;
666  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *adjwgtsum, *label, *where, *bndptr, *bndind;
667  idxtype *sxadj, *svwgt, *sadjncy, *sadjwgt, *sadjwgtsum, *slabel;
668  idxtype *rename;
669  idxtype *auxadjncy, *auxadjwgt;
670 
671  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SplitTmr));
672 
673  nvtxs = graph->nvtxs;
674  xadj = graph->xadj;
675  vwgt = graph->vwgt;
676  adjncy = graph->adjncy;
677  adjwgt = graph->adjwgt;
678  adjwgtsum = graph->adjwgtsum;
679  label = graph->label;
680  where = graph->where;
681  bndptr = graph->bndptr;
682  bndind = graph->bndind;
683  ASSERT(bndptr != NULL);
684 
685  /* Go and use bndptr to also mark the boundary nodes in the two partitions */
686  for (ii=0; ii<graph->nbnd; ii++) {
687  i = bndind[ii];
688  for (j=xadj[i]; j<xadj[i+1]; j++)
689  bndptr[adjncy[j]] = 1;
690  }
691 
692  rename = idxwspacemalloc(ctrl, nvtxs);
693 
694  /* Go and split the graph a component at a time */
695  for (iii=0; iii<ncmps; iii++) {
696  RandomPermute(cptr[iii+1]-cptr[iii], cind+cptr[iii], 0);
697  snvtxs = snedges = 0;
698  for (j=cptr[iii]; j<cptr[iii+1]; j++) {
699  i = cind[j];
700  rename[i] = snvtxs++;
701  snedges += xadj[i+1]-xadj[i];
702  }
703 
704  SetUpSplitGraph(graph, sgraphs+iii, snvtxs, snedges);
705  sxadj = sgraphs[iii].xadj;
706  svwgt = sgraphs[iii].vwgt;
707  sadjwgtsum = sgraphs[iii].adjwgtsum;
708  sadjncy = sgraphs[iii].adjncy;
709  sadjwgt = sgraphs[iii].adjwgt;
710  slabel = sgraphs[iii].label;
711 
712  snvtxs = snedges = sxadj[0] = 0;
713  for (ii=cptr[iii]; ii<cptr[iii+1]; ii++) {
714  i = cind[ii];
715 
716  istart = xadj[i];
717  iend = xadj[i+1];
718  if (bndptr[i] == -1) { /* This is an interior vertex */
719  auxadjncy = sadjncy + snedges - istart;
720  auxadjwgt = sadjwgt + snedges - istart;
721  for(j=istart; j<iend; j++)
722  auxadjncy[j] = adjncy[j];
723  snedges += iend-istart;
724  }
725  else {
726  l = snedges;
727  for (j=istart; j<iend; j++) {
728  k = adjncy[j];
729  if (where[k] != 2)
730  sadjncy[l++] = k;
731  }
732  snedges = l;
733  }
734 
735  svwgt[snvtxs] = vwgt[i];
736  sadjwgtsum[snvtxs] = snedges-sxadj[snvtxs];
737  slabel[snvtxs] = label[i];
738  sxadj[++snvtxs] = snedges;
739  }
740 
741  idxset(snedges, 1, sadjwgt);
742  for (i=0; i<snedges; i++)
743  sadjncy[i] = rename[sadjncy[i]];
744 
745  sgraphs[iii].nvtxs = snvtxs;
746  sgraphs[iii].nedges = snedges;
747  sgraphs[iii].ncon = 1;
748 
749  if (snvtxs < MMDSWITCH)
750  sgraphs[iii].adjwgt = NULL; /* A marker to call MMD on the driver */
751  }
752 
753  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SplitTmr));
754 
755  idxwspacefree(ctrl, nvtxs);
756 
757  return ncmps;
758 
759 }
760 
761 
762 
763 
764 
#define idxwspacefree
Definition: rename.h:165
#define OP_OEMETIS
Definition: defs.h:91
#define OEMETIS_RTYPE
Definition: defs.h:57
int pfactor
Definition: struct.h:223
#define Compute2WayNodePartitionParams
Definition: rename.h:351
timer TotalTmr
Definition: struct.h:230
#define ONMETIS_OFLAGS
Definition: defs.h:65
void METIS_NodeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options, idxtype *perm, idxtype *iperm)
Definition: ometis.c:79
#define genmmd
Definition: rename.h:253
#define SplitGraphOrder
Definition: rename.h:298
#define ONMETIS_NSEPS
Definition: defs.h:67
#define COMPRESSION_FRACTION
Definition: defs.h:145
#define ConstructMinCoverSeparator
Definition: rename.h:337
idxtype * pwgts
Definition: struct.h:176
idxtype * adjwgtsum
Definition: struct.h:168
int optype
Definition: struct.h:222
int nbnd
Definition: struct.h:177
#define ONMETIS_DBGLVL
Definition: defs.h:64
timer SepTmr
Definition: struct.h:230
void METIS_NodeWND(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, int *numflag, int *options, idxtype *perm, idxtype *iperm)
Definition: ometis.c:204
#define SetUpGraph
Definition: rename.h:72
#define OPTION_NSEPS
Definition: defs.h:36
#define ONMETIS_PFACTOR
Definition: defs.h:66
#define DBG_SEPINFO
Definition: defs.h:161
#define OPTION_CTYPE
Definition: defs.h:30
#define MAXIDX
Definition: struct.h:24
#define Coarsen2Way
Definition: rename.h:34
int IType
Definition: struct.h:218
int mincut
Definition: struct.h:175
idxtype * bndptr
Definition: struct.h:178
int oflags
Definition: struct.h:225
idxtype * rdata
Definition: struct.h:157
#define OPTION_OFLAGS
Definition: defs.h:34
#define MlevelNodeBisectionMultiple
Definition: rename.h:296
#define Compute2WayPartitionParams
Definition: rename.h:330
#define IPART_GGPKL
Definition: defs.h:108
#define idxwspacemalloc
Definition: rename.h:164
#define SetUpSplitGraph
Definition: rename.h:311
#define idxsum
Definition: rename.h:399
#define stoptimer(tmr)
Definition: macros.h:54
#define Change2FNumberingOrder
Definition: rename.h:65
HitTile_Vector graph
#define Allocate2WayNodePartitionMemory
Definition: rename.h:350
int CType
Definition: struct.h:217
idxtype * where
Definition: struct.h:176
#define LTERM
Definition: defs.h:18
#define PruneGraph
Definition: rename.h:39
int idxtype
Definition: struct.h:19
#define OEMETIS_ITYPE
Definition: defs.h:56
#define OFLAG_CCMP
Definition: defs.h:39
#define InitRandom
Definition: rename.h:412
#define AllocateWorkSpace
Definition: rename.h:161
#define OEMETIS_DBGLVL
Definition: defs.h:58
#define OPTION_PFACTOR
Definition: defs.h:35
#define ONMETIS_RTYPE
Definition: defs.h:63
#define MlevelNestedDissection
Definition: rename.h:294
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define SplitGraphOrderCC
Definition: rename.h:300
#define ConstructSeparator
Definition: rename.h:335
#define InitTimers
Definition: rename.h:373
#define Change2CNumbering
Definition: rename.h:62
idxtype * label
Definition: struct.h:170
#define MMDSWITCH
Definition: defs.h:149
#define Refine2WayNode
Definition: rename.h:349
#define OPTION_RTYPE
Definition: defs.h:32
#define InitSeparator
Definition: rename.h:85
#define OFLAG_COMPRESS
Definition: defs.h:38
#define ONMETIS_ITYPE
Definition: defs.h:62
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define idxcopy(n, a, b)
Definition: macros.h:44
#define IPART_GGPKLNODE
Definition: defs.h:109
#define OEMETIS_CTYPE
Definition: defs.h:55
int CoarsenTo
Definition: struct.h:215
void GKfree(void **ptr1,...)
Definition: util.c:121
int ncon
Definition: struct.h:194
void METIS_EdgeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options, idxtype *perm, idxtype *iperm)
Definition: ometis.c:22
#define GKmalloc
Definition: rename.h:387
#define OP_ONMETIS
Definition: defs.h:92
idxtype * bndind
Definition: struct.h:178
#define FindComponents
Definition: rename.h:80
#define ONMETIS_CTYPE
Definition: defs.h:61
#define PrintTimers
Definition: rename.h:374
timer SplitTmr
Definition: struct.h:230
#define FreeWorkSpace
Definition: rename.h:162
idxtype * vwgt
Definition: struct.h:163
#define DBG_TIME
Definition: defs.h:154
int RType
Definition: struct.h:219
int nedges
Definition: struct.h:161
#define idxmalloc
Definition: rename.h:383
int nseps
Definition: struct.h:224
idxtype * gdata
Definition: struct.h:157
#define MMDOrder
Definition: rename.h:299
int maxvwgt
Definition: struct.h:220
#define OPTION_ITYPE
Definition: defs.h:31
int nvtxs
Definition: struct.h:161
#define RandomPermute
Definition: rename.h:410
#define ASSERT(expr)
Definition: macros.h:130
#define CompressGraph
Definition: rename.h:38
#define MlevelNestedDissectionCC
Definition: rename.h:295
#define MlevelEdgeBisection
Definition: rename.h:309
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define MlevelNodeBisection
Definition: rename.h:297
#define ORDER_UNBALANCE_FRACTION
Definition: defs.h:147
#define OPTION_DBGLVL
Definition: defs.h:33
#define starttimer(tmr)
Definition: macros.h:53
#define Init2WayPartition
Definition: rename.h:84