source: anuga_work/development/pymetis/metis-4.0/Lib/ometis.c @ 6842

Last change on this file since 6842 was 2051, checked in by jack, 19 years ago

Python interface to metis. Currently provides only the
METIS_PartMeshNodal function, since that is what is currently needed for partitioning.
Module name is metis.
File size: 22.0 KB
Line 
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**************************************************************************/
22void METIS_EdgeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options, 
23                  idxtype *perm, idxtype *iperm) 
24{
25  int i, j;
26  GraphType graph;
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**************************************************************************/
79void 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;
83  GraphType graph;
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**************************************************************************/
204void 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;
208  GraphType graph;
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**************************************************************************/
263void 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**************************************************************************/
323void 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**************************************************************************/
386void 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**************************************************************************/
468void 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**************************************************************************/
508void SplitGraphOrder(CtrlType *ctrl, GraphType *graph, GraphType *lgraph, GraphType *rgraph)
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**************************************************************************/
617void 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**************************************************************************/
663int 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
Note: See TracBrowser for help on using the repository browser.