2
* Copyright 1997, Regents of the University of Minnesota
6
* This file contains the top level routines for the multilevel recursive
7
* bisection algorithm PMETIS.
12
* $Id: ometis.c 10513 2011-07-07 22:06:03Z karypis $
19
/*************************************************************************/
20
/*! This function is the entry point for the multilevel nested dissection
21
ordering code. At each bisection, a node-separator is computed using
22
a node-based refinement approach.
24
\param nvtxs is the number of vertices in the graph.
25
\param xadj is of length nvtxs+1 marking the start of the adjancy
26
list of each vertex in adjncy.
27
\param adjncy stores the adjacency lists of the vertices. The adjnacy
28
list of a vertex should not contain the vertex itself.
29
\param vwgt is an array of size nvtxs storing the weight of each
30
vertex. If vwgt is NULL, then the vertices are considered
32
\param numflag is either 0 or 1 indicating that the numbering of
33
the vertices starts from 0 or 1, respectively.
34
\param options is an array of size METIS_NOPTIONS used to pass
35
various options impacting the of the algorithm. A NULL
36
value indicates use of default options.
37
\param perm is an array of size nvtxs such that if A and A' are
38
the original and permuted matrices, then A'[i] = A[perm[i]].
39
\param iperm is an array of size nvtxs such that if A and A' are
40
the original and permuted matrices, then A[i] = A'[iperm[i]].
42
/*************************************************************************/
43
int METIS_NodeND(idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
44
idx_t *options, idx_t *perm, idx_t *iperm)
46
int sigrval=0, renumber=0;
47
idx_t i, ii, j, l, nnvtxs=0;
50
idx_t *cptr, *cind, *piperm;
53
/* set up malloc cleaning code and signal catchers */
54
if (!gk_malloc_init())
55
return METIS_ERROR_MEMORY;
59
if ((sigrval = gk_sigcatch()) != 0)
63
/* set up the run time parameters */
64
ctrl = SetupCtrl(METIS_OP_OMETIS, options, 1, 3, NULL, NULL);
67
return METIS_ERROR_INPUT;
70
/* if required, change the numbering to 0 */
71
if (ctrl->numflag == 1) {
72
Change2CNumbering(*nvtxs, xadj, adjncy);
76
IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));
77
IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->TotalTmr));
79
/* prune the dense columns */
80
if (ctrl->pfactor > 0.0) {
81
piperm = imalloc(*nvtxs, "OMETIS: piperm");
83
graph = PruneGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, piperm, ctrl->pfactor);
85
/* if there was no prunning, cleanup the pfactor */
86
gk_free((void **)&piperm, LTERM);
90
nnvtxs = graph->nvtxs;
91
ctrl->compress = 0; /* disable compression if prunning took place */
95
/* compress the graph; note that compression only happens if not prunning
98
cptr = imalloc(*nvtxs+1, "OMETIS: cptr");
99
cind = imalloc(*nvtxs, "OMETIS: cind");
101
graph = CompressGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, cptr, cind);
103
/* if there was no compression, cleanup the compress flag */
104
gk_free((void **)&cptr, &cind, LTERM);
108
nnvtxs = graph->nvtxs;
109
ctrl->cfactor = 1.0*(*nvtxs)/nnvtxs;
110
if (ctrl->cfactor > 1.5 && ctrl->nseps == 1)
112
//ctrl->nseps = (idx_t)(ctrl->cfactor*ctrl->nseps);
116
/* if no prunning and no compression, setup the graph in the normal way. */
117
if (ctrl->pfactor == 0.0 && ctrl->compress == 0)
118
graph = SetupGraph(ctrl, *nvtxs, 1, xadj, adjncy, vwgt, NULL, NULL);
120
ASSERT(CheckGraph(graph, ctrl->numflag, 1));
122
/* allocate workspace memory */
123
AllocateWorkSpace(ctrl, graph);
125
/* do the nested dissection ordering */
127
MlevelNestedDissectionCC(ctrl, graph, iperm, graph->nvtxs);
129
MlevelNestedDissection(ctrl, graph, iperm, graph->nvtxs);
132
if (ctrl->pfactor > 0.0) { /* Order any prunned vertices */
133
icopy(nnvtxs, iperm, perm); /* Use perm as an auxiliary array */
134
for (i=0; i<nnvtxs; i++)
135
iperm[piperm[i]] = perm[i];
136
for (i=nnvtxs; i<*nvtxs; i++)
137
iperm[piperm[i]] = i;
139
gk_free((void **)&piperm, LTERM);
141
else if (ctrl->compress) { /* Uncompress the ordering */
142
/* construct perm from iperm */
143
for (i=0; i<nnvtxs; i++)
145
for (l=ii=0; ii<nnvtxs; ii++) {
147
for (j=cptr[i]; j<cptr[i+1]; j++)
148
iperm[cind[j]] = l++;
151
gk_free((void **)&cptr, &cind, LTERM);
154
for (i=0; i<*nvtxs; i++)
157
IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->TotalTmr));
158
IFSET(ctrl->dbglvl, METIS_DBG_TIME, PrintTimers(ctrl));
164
/* if required, change the numbering back to 1 */
166
Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);
169
gk_malloc_cleanup(0);
171
return metis_rcode(sigrval);
175
/*************************************************************************/
176
/*! This is the driver for the recursive tri-section of a graph into the
177
left, separator, and right partitions. The graphs correspond to the
178
left and right parts are further tri-sected in a recursive fashion.
179
The nodes in the separator are ordered at the end of the left & right
182
/*************************************************************************/
183
void MlevelNestedDissection(ctrl_t *ctrl, graph_t *graph, idx_t *order,
186
idx_t i, j, nvtxs, nbnd;
187
idx_t *label, *bndind;
188
graph_t *lgraph, *rgraph;
190
nvtxs = graph->nvtxs;
192
MlevelNodeBisectionMultiple(ctrl, graph);
194
IFSET(ctrl->dbglvl, METIS_DBG_SEPINFO,
195
printf("Nvtxs: %6"PRIDX", [%6"PRIDX" %6"PRIDX" %6"PRIDX"]\n",
196
graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
199
/* Order the nodes in the separator */
201
bndind = graph->bndind;
202
label = graph->label;
203
for (i=0; i<nbnd; i++)
204
order[label[bndind[i]]] = --lastvtx;
206
SplitGraphOrder(ctrl, graph, &lgraph, &rgraph);
208
/* Free the memory of the top level graph */
211
/* Recurse on lgraph first, as its lastvtx depends on rgraph->nvtxs, which
212
will not be defined upon return from MlevelNestedDissection. */
213
if (lgraph->nvtxs > MMDSWITCH && lgraph->nedges > 0)
214
MlevelNestedDissection(ctrl, lgraph, order, lastvtx-rgraph->nvtxs);
216
MMDOrder(ctrl, lgraph, order, lastvtx-rgraph->nvtxs);
219
if (rgraph->nvtxs > MMDSWITCH && rgraph->nedges > 0)
220
MlevelNestedDissection(ctrl, rgraph, order, lastvtx);
222
MMDOrder(ctrl, rgraph, order, lastvtx);
228
/*************************************************************************/
229
/*! This routine is similar to its non 'CC' counterpart. The difference is
230
that after each tri-section, the connected components of the original
231
graph that result after removing the separator vertises are ordered
232
independently (i.e., this may lead to more than just the left and
233
the right subgraphs).
235
/*************************************************************************/
236
void MlevelNestedDissectionCC(ctrl_t *ctrl, graph_t *graph, idx_t *order,
239
idx_t i, j, nvtxs, nbnd, ncmps, rnvtxs, snvtxs;
240
idx_t *label, *bndind;
244
nvtxs = graph->nvtxs;
246
MlevelNodeBisectionMultiple(ctrl, graph);
248
IFSET(ctrl->dbglvl, METIS_DBG_SEPINFO,
249
printf("Nvtxs: %6"PRIDX", [%6"PRIDX" %6"PRIDX" %6"PRIDX"]\n",
250
graph->nvtxs, graph->pwgts[0], graph->pwgts[1], graph->pwgts[2]));
252
/* Order the nodes in the separator */
254
bndind = graph->bndind;
255
label = graph->label;
256
for (i=0; i<nbnd; i++)
257
order[label[bndind[i]]] = --lastvtx;
260
cptr = iwspacemalloc(ctrl, nvtxs+1);
261
cind = iwspacemalloc(ctrl, nvtxs);
262
ncmps = FindSepInducedComponents(ctrl, graph, cptr, cind);
264
if (ctrl->dbglvl&METIS_DBG_INFO) {
266
printf(" Bisection resulted in %"PRIDX" connected components\n", ncmps);
269
sgraphs = SplitGraphOrderCC(ctrl, graph, ncmps, cptr, cind);
273
/* Free the memory of the top level graph */
276
/* Go and process the subgraphs */
277
for (rnvtxs=i=0; i<ncmps; i++) {
278
/* Save the number of vertices in sgraphs[i] because sgraphs[i] is freed
279
inside MlevelNestedDissectionCC, and as such it will be undefined. */
280
snvtxs = sgraphs[i]->nvtxs;
282
if (sgraphs[i]->nvtxs > MMDSWITCH && sgraphs[i]->nedges > 0) {
283
MlevelNestedDissectionCC(ctrl, sgraphs[i], order, lastvtx-rnvtxs);
286
MMDOrder(ctrl, sgraphs[i], order, lastvtx-rnvtxs);
287
FreeGraph(&sgraphs[i]);
292
gk_free((void **)&sgraphs, LTERM);
296
/*************************************************************************/
297
/*! This function performs multilevel node bisection (i.e., tri-section).
298
It performs multiple bisections and selects the best. */
299
/*************************************************************************/
300
void MlevelNodeBisectionMultiple(ctrl_t *ctrl, graph_t *graph)
305
/* if the graph is small, just find a single vertex separator */
306
if (ctrl->nseps == 1 || graph->nvtxs < (ctrl->compress ? 1000 : 2000)) {
307
MlevelNodeBisectionL2(ctrl, graph, LARGENIPARTS);
313
bestwhere = iwspacemalloc(ctrl, graph->nvtxs);
315
mincut = graph->tvwgt[0];
316
for (i=0; i<ctrl->nseps; i++) {
317
MlevelNodeBisectionL2(ctrl, graph, LARGENIPARTS);
319
if (i == 0 || graph->mincut < mincut) {
320
mincut = graph->mincut;
321
if (i < ctrl->nseps-1)
322
icopy(graph->nvtxs, graph->where, bestwhere);
328
if (i < ctrl->nseps-1)
332
if (mincut != graph->mincut) {
333
icopy(graph->nvtxs, bestwhere, graph->where);
334
Compute2WayNodePartitionParams(ctrl, graph);
341
/*************************************************************************/
342
/*! This function performs multilevel node bisection (i.e., tri-section).
343
It performs multiple bisections and selects the best. */
344
/*************************************************************************/
345
void MlevelNodeBisectionL2(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
347
idx_t i, mincut, nruns=5;
351
/* if the graph is small, just find a single vertex separator */
352
if (graph->nvtxs < 5000) {
353
MlevelNodeBisectionL1(ctrl, graph, niparts);
359
ctrl->CoarsenTo = gk_max(100, graph->nvtxs/30);
361
cgraph = CoarsenGraphNlevels(ctrl, graph, 4);
363
bestwhere = iwspacemalloc(ctrl, cgraph->nvtxs);
365
mincut = graph->tvwgt[0];
366
for (i=0; i<nruns; i++) {
367
MlevelNodeBisectionL1(ctrl, cgraph, 0.7*niparts);
369
if (i == 0 || cgraph->mincut < mincut) {
370
mincut = cgraph->mincut;
372
icopy(cgraph->nvtxs, cgraph->where, bestwhere);
382
if (mincut != cgraph->mincut)
383
icopy(cgraph->nvtxs, bestwhere, cgraph->where);
387
Refine2WayNode(ctrl, graph, cgraph);
392
/*************************************************************************/
393
/*! The top-level routine of the actual multilevel node bisection */
394
/*************************************************************************/
395
void MlevelNodeBisectionL1(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
399
ctrl->CoarsenTo = graph->nvtxs/8;
400
if (ctrl->CoarsenTo > 100)
401
ctrl->CoarsenTo = 100;
402
else if (ctrl->CoarsenTo < 40)
403
ctrl->CoarsenTo = 40;
405
cgraph = CoarsenGraph(ctrl, graph);
407
niparts = gk_max(1, (cgraph->nvtxs <= ctrl->CoarsenTo ? niparts/2: niparts));
408
/*niparts = (cgraph->nvtxs <= ctrl->CoarsenTo ? SMALLNIPARTS : LARGENIPARTS);*/
409
InitSeparator(ctrl, cgraph, niparts);
411
Refine2WayNode(ctrl, graph, cgraph);
415
/*************************************************************************/
416
/*! This function takes a graph and a tri-section (left, right, separator)
417
and splits it into two graphs.
419
This function relies on the fact that adjwgt is all equal to 1.
421
/*************************************************************************/
422
void SplitGraphOrder(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph,
425
idx_t i, ii, j, k, l, istart, iend, mypart, nvtxs, snvtxs[3], snedges[3];
426
idx_t *xadj, *vwgt, *adjncy, *adjwgt, *label, *where, *bndptr, *bndind;
427
idx_t *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *slabel[2];
430
graph_t *lgraph, *rgraph;
434
IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->SplitTmr));
436
nvtxs = graph->nvtxs;
439
adjncy = graph->adjncy;
440
adjwgt = graph->adjwgt;
441
label = graph->label;
442
where = graph->where;
443
bndptr = graph->bndptr;
444
bndind = graph->bndind;
445
ASSERT(bndptr != NULL);
447
rename = iwspacemalloc(ctrl, nvtxs);
449
snvtxs[0] = snvtxs[1] = snvtxs[2] = snedges[0] = snedges[1] = snedges[2] = 0;
450
for (i=0; i<nvtxs; i++) {
452
rename[i] = snvtxs[k]++;
453
snedges[k] += xadj[i+1]-xadj[i];
456
lgraph = SetupSplitGraph(graph, snvtxs[0], snedges[0]);
457
sxadj[0] = lgraph->xadj;
458
svwgt[0] = lgraph->vwgt;
459
sadjncy[0] = lgraph->adjncy;
460
sadjwgt[0] = lgraph->adjwgt;
461
slabel[0] = lgraph->label;
463
rgraph = SetupSplitGraph(graph, snvtxs[1], snedges[1]);
464
sxadj[1] = rgraph->xadj;
465
svwgt[1] = rgraph->vwgt;
466
sadjncy[1] = rgraph->adjncy;
467
sadjwgt[1] = rgraph->adjwgt;
468
slabel[1] = rgraph->label;
470
/* Go and use bndptr to also mark the boundary nodes in the two partitions */
471
for (ii=0; ii<graph->nbnd; ii++) {
473
for (j=xadj[i]; j<xadj[i+1]; j++)
474
bndptr[adjncy[j]] = 1;
477
snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
478
sxadj[0][0] = sxadj[1][0] = 0;
479
for (i=0; i<nvtxs; i++) {
480
if ((mypart = where[i]) == 2)
485
if (bndptr[i] == -1) { /* This is an interior vertex */
486
auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
487
for(j=istart; j<iend; j++)
488
auxadjncy[j] = adjncy[j];
489
snedges[mypart] += iend-istart;
492
auxadjncy = sadjncy[mypart];
494
for (j=istart; j<iend; j++) {
496
if (where[k] == mypart)
502
svwgt[mypart][snvtxs[mypart]] = vwgt[i];
503
slabel[mypart][snvtxs[mypart]] = label[i];
504
sxadj[mypart][++snvtxs[mypart]] = snedges[mypart];
507
for (mypart=0; mypart<2; mypart++) {
508
iend = snedges[mypart];
509
iset(iend, 1, sadjwgt[mypart]);
511
auxadjncy = sadjncy[mypart];
512
for (i=0; i<iend; i++)
513
auxadjncy[i] = rename[auxadjncy[i]];
516
lgraph->nvtxs = snvtxs[0];
517
lgraph->nedges = snedges[0];
518
rgraph->nvtxs = snvtxs[1];
519
rgraph->nedges = snedges[1];
521
SetupGraph_tvwgt(lgraph);
522
SetupGraph_tvwgt(rgraph);
524
IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->SplitTmr));
533
/*************************************************************************/
534
/*! This function takes a graph and generates a set of graphs, each of
535
which is a connected component in the original graph.
537
This function relies on the fact that adjwgt is all equal to 1.
539
\param ctrl stores run state info.
540
\param graph is the graph to be split.
541
\param ncmps is the number of connected components.
542
\param cptr is an array of size ncmps+1 that marks the start and end
543
locations of the vertices in cind that make up the respective
544
components (i.e., cptr, cind is in CSR format).
545
\param cind is an array of size equal to the number of vertices in
546
the original graph and stores the vertices that belong to each
549
\returns an array of subgraphs corresponding to the extracted subgraphs.
551
/*************************************************************************/
552
graph_t **SplitGraphOrderCC(ctrl_t *ctrl, graph_t *graph, idx_t ncmps,
553
idx_t *cptr, idx_t *cind)
555
idx_t i, ii, iii, j, k, l, istart, iend, mypart, nvtxs, snvtxs, snedges;
556
idx_t *xadj, *vwgt, *adjncy, *adjwgt, *label, *where, *bndptr, *bndind;
557
idx_t *sxadj, *svwgt, *sadjncy, *sadjwgt, *slabel;
564
IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->SplitTmr));
566
nvtxs = graph->nvtxs;
569
adjncy = graph->adjncy;
570
adjwgt = graph->adjwgt;
571
label = graph->label;
572
where = graph->where;
573
bndptr = graph->bndptr;
574
bndind = graph->bndind;
575
ASSERT(bndptr != NULL);
577
/* Go and use bndptr to also mark the boundary nodes in the two partitions */
578
for (ii=0; ii<graph->nbnd; ii++) {
580
for (j=xadj[i]; j<xadj[i+1]; j++)
581
bndptr[adjncy[j]] = 1;
584
rename = iwspacemalloc(ctrl, nvtxs);
586
sgraphs = (graph_t **)gk_malloc(sizeof(graph_t *)*ncmps, "SplitGraphOrderCC: sgraphs");
588
/* Go and split the graph a component at a time */
589
for (iii=0; iii<ncmps; iii++) {
590
irandArrayPermute(cptr[iii+1]-cptr[iii], cind+cptr[iii], cptr[iii+1]-cptr[iii], 0);
591
snvtxs = snedges = 0;
592
for (j=cptr[iii]; j<cptr[iii+1]; j++) {
594
rename[i] = snvtxs++;
595
snedges += xadj[i+1]-xadj[i];
598
sgraphs[iii] = SetupSplitGraph(graph, snvtxs, snedges);
600
sxadj = sgraphs[iii]->xadj;
601
svwgt = sgraphs[iii]->vwgt;
602
sadjncy = sgraphs[iii]->adjncy;
603
sadjwgt = sgraphs[iii]->adjwgt;
604
slabel = sgraphs[iii]->label;
606
snvtxs = snedges = sxadj[0] = 0;
607
for (ii=cptr[iii]; ii<cptr[iii+1]; ii++) {
612
if (bndptr[i] == -1) { /* This is an interior vertex */
613
auxadjncy = sadjncy + snedges - istart;
614
for(j=istart; j<iend; j++)
615
auxadjncy[j] = adjncy[j];
616
snedges += iend-istart;
620
for (j=istart; j<iend; j++) {
628
svwgt[snvtxs] = vwgt[i];
629
slabel[snvtxs] = label[i];
630
sxadj[++snvtxs] = snedges;
633
iset(snedges, 1, sadjwgt);
634
for (i=0; i<snedges; i++)
635
sadjncy[i] = rename[sadjncy[i]];
637
sgraphs[iii]->nvtxs = snvtxs;
638
sgraphs[iii]->nedges = snedges;
640
SetupGraph_tvwgt(sgraphs[iii]);
643
IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->SplitTmr));
651
/*************************************************************************/
652
/*! This function uses MMD to order the graph. The vertices are numbered
653
from lastvtx downwards. */
654
/*************************************************************************/
655
void MMDOrder(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
657
idx_t i, j, k, nvtxs, nofsub, firstvtx;
658
idx_t *xadj, *adjncy, *label;
659
idx_t *perm, *iperm, *head, *qsize, *list, *marker;
663
nvtxs = graph->nvtxs;
665
adjncy = graph->adjncy;
667
/* Relabel the vertices so that it starts from 1 */
671
for (i=0; i<nvtxs+1; i++)
674
perm = iwspacemalloc(ctrl, nvtxs+5);
675
iperm = iwspacemalloc(ctrl, nvtxs+5);
676
head = iwspacemalloc(ctrl, nvtxs+5);
677
qsize = iwspacemalloc(ctrl, nvtxs+5);
678
list = iwspacemalloc(ctrl, nvtxs+5);
679
marker = iwspacemalloc(ctrl, nvtxs+5);
681
genmmd(nvtxs, xadj, adjncy, iperm, perm, 1, head, qsize, list, marker, IDX_MAX, &nofsub);
683
label = graph->label;
684
firstvtx = lastvtx-nvtxs;
685
for (i=0; i<nvtxs; i++)
686
order[label[i]] = firstvtx+iperm[i]-1;
688
/* Relabel the vertices so that it starts from 0 */
689
for (i=0; i<nvtxs+1; i++)
added
removed
elmergrid/src/metis-5.1.0/libmetis/ometis.c
