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 10513 2011-07-07 22:06:03Z karypis $
13 *
14 */
15
16 #include "metislib.h"
17
18
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.
23
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
31 to have unit weight.
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]].
41 */
42 /*************************************************************************/
METIS_NodeND(idx_t * nvtxs,idx_t * xadj,idx_t * adjncy,idx_t * vwgt,idx_t * options,idx_t * perm,idx_t * iperm)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)
45 {
46 int sigrval=0, renumber=0;
47 idx_t i, ii, j, l, nnvtxs=0;
48 graph_t *graph=NULL;
49 ctrl_t *ctrl;
50 idx_t *cptr, *cind, *piperm;
51 int numflag = 0;
52
53 /* set up malloc cleaning code and signal catchers */
54 if (!gk_malloc_init())
55 return METIS_ERROR_MEMORY;
56
57 gk_sigtrap();
58
59 if ((sigrval = gk_sigcatch()) != 0)
60 goto SIGTHROW;
61
62
63 /* set up the run time parameters */
64 ctrl = SetupCtrl(METIS_OP_OMETIS, options, 1, 3, NULL, NULL);
65 if (!ctrl) {
66 gk_siguntrap();
67 return METIS_ERROR_INPUT;
68 }
69
70 /* if required, change the numbering to 0 */
71 if (ctrl->numflag == 1) {
72 Change2CNumbering(*nvtxs, xadj, adjncy);
73 renumber = 1;
74 }
75
76 IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));
77 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->TotalTmr));
78
79 /* prune the dense columns */
80 if (ctrl->pfactor > 0.0) {
81 piperm = imalloc(*nvtxs, "OMETIS: piperm");
82
83 graph = PruneGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, piperm, ctrl->pfactor);
84 if (graph == NULL) {
85 /* if there was no prunning, cleanup the pfactor */
86 gk_free((void **)&piperm, LTERM);
87 ctrl->pfactor = 0.0;
88 }
89 else {
90 nnvtxs = graph->nvtxs;
91 ctrl->compress = 0; /* disable compression if prunning took place */
92 }
93 }
94
95 /* compress the graph; note that compression only happens if not prunning
96 has taken place. */
97 if (ctrl->compress) {
98 cptr = imalloc(*nvtxs+1, "OMETIS: cptr");
99 cind = imalloc(*nvtxs, "OMETIS: cind");
100
101 graph = CompressGraph(ctrl, *nvtxs, xadj, adjncy, vwgt, cptr, cind);
102 if (graph == NULL) {
103 /* if there was no compression, cleanup the compress flag */
104 gk_free((void **)&cptr, &cind, LTERM);
105 ctrl->compress = 0;
106 }
107 else {
108 nnvtxs = graph->nvtxs;
109 ctrl->cfactor = 1.0*(*nvtxs)/nnvtxs;
110 if (ctrl->cfactor > 1.5 && ctrl->nseps == 1)
111 ctrl->nseps = 2;
112 //ctrl->nseps = (idx_t)(ctrl->cfactor*ctrl->nseps);
113 }
114 }
115
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);
119
120 ASSERT(CheckGraph(graph, ctrl->numflag, 1));
121
122 /* allocate workspace memory */
123 AllocateWorkSpace(ctrl, graph);
124
125 /* do the nested dissection ordering */
126 if (ctrl->ccorder)
127 MlevelNestedDissectionCC(ctrl, graph, iperm, graph->nvtxs);
128 else
129 MlevelNestedDissection(ctrl, graph, iperm, graph->nvtxs);
130
131
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;
138
139 gk_free((void **)&piperm, LTERM);
140 }
141 else if (ctrl->compress) { /* Uncompress the ordering */
142 /* construct perm from iperm */
143 for (i=0; i<nnvtxs; i++)
144 perm[iperm[i]] = i;
145 for (l=ii=0; ii<nnvtxs; ii++) {
146 i = perm[ii];
147 for (j=cptr[i]; j<cptr[i+1]; j++)
148 iperm[cind[j]] = l++;
149 }
150
151 gk_free((void **)&cptr, &cind, LTERM);
152 }
153
154 for (i=0; i<*nvtxs; i++)
155 perm[iperm[i]] = i;
156
157 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->TotalTmr));
158 IFSET(ctrl->dbglvl, METIS_DBG_TIME, PrintTimers(ctrl));
159
160 /* clean up */
161 FreeCtrl(&ctrl);
162
163 SIGTHROW:
164 /* if required, change the numbering back to 1 */
165 if (renumber)
166 Change2FNumberingOrder(*nvtxs, xadj, adjncy, perm, iperm);
167
168 gk_siguntrap();
169 gk_malloc_cleanup(0);
170
171 return metis_rcode(sigrval);
172 }
173
174
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
180 nodes.
181 */
182 /*************************************************************************/
MlevelNestedDissection(ctrl_t * ctrl,graph_t * graph,idx_t * order,idx_t lastvtx)183 void MlevelNestedDissection(ctrl_t *ctrl, graph_t *graph, idx_t *order,
184 idx_t lastvtx)
185 {
186 idx_t i, j, nvtxs, nbnd;
187 idx_t *label, *bndind;
188 graph_t *lgraph, *rgraph;
189
190 nvtxs = graph->nvtxs;
191
192 MlevelNodeBisectionMultiple(ctrl, graph);
193
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]));
197
198
199 /* Order the nodes in the separator */
200 nbnd = graph->nbnd;
201 bndind = graph->bndind;
202 label = graph->label;
203 for (i=0; i<nbnd; i++)
204 order[label[bndind[i]]] = --lastvtx;
205
206 SplitGraphOrder(ctrl, graph, &lgraph, &rgraph);
207
208 /* Free the memory of the top level graph */
209 FreeGraph(&graph);
210
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);
215 else {
216 MMDOrder(ctrl, lgraph, order, lastvtx-rgraph->nvtxs);
217 FreeGraph(&lgraph);
218 }
219 if (rgraph->nvtxs > MMDSWITCH && rgraph->nedges > 0)
220 MlevelNestedDissection(ctrl, rgraph, order, lastvtx);
221 else {
222 MMDOrder(ctrl, rgraph, order, lastvtx);
223 FreeGraph(&rgraph);
224 }
225 }
226
227
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).
234 */
235 /*************************************************************************/
MlevelNestedDissectionCC(ctrl_t * ctrl,graph_t * graph,idx_t * order,idx_t lastvtx)236 void MlevelNestedDissectionCC(ctrl_t *ctrl, graph_t *graph, idx_t *order,
237 idx_t lastvtx)
238 {
239 idx_t i, j, nvtxs, nbnd, ncmps, rnvtxs, snvtxs;
240 idx_t *label, *bndind;
241 idx_t *cptr, *cind;
242 graph_t **sgraphs;
243
244 nvtxs = graph->nvtxs;
245
246 MlevelNodeBisectionMultiple(ctrl, graph);
247
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]));
251
252 /* Order the nodes in the separator */
253 nbnd = graph->nbnd;
254 bndind = graph->bndind;
255 label = graph->label;
256 for (i=0; i<nbnd; i++)
257 order[label[bndind[i]]] = --lastvtx;
258
259 WCOREPUSH;
260 cptr = iwspacemalloc(ctrl, nvtxs+1);
261 cind = iwspacemalloc(ctrl, nvtxs);
262 ncmps = FindSepInducedComponents(ctrl, graph, cptr, cind);
263
264 if (ctrl->dbglvl&METIS_DBG_INFO) {
265 if (ncmps > 2)
266 printf(" Bisection resulted in %"PRIDX" connected components\n", ncmps);
267 }
268
269 sgraphs = SplitGraphOrderCC(ctrl, graph, ncmps, cptr, cind);
270
271 WCOREPOP;
272
273 /* Free the memory of the top level graph */
274 FreeGraph(&graph);
275
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;
281
282 if (sgraphs[i]->nvtxs > MMDSWITCH && sgraphs[i]->nedges > 0) {
283 MlevelNestedDissectionCC(ctrl, sgraphs[i], order, lastvtx-rnvtxs);
284 }
285 else {
286 MMDOrder(ctrl, sgraphs[i], order, lastvtx-rnvtxs);
287 FreeGraph(&sgraphs[i]);
288 }
289 rnvtxs += snvtxs;
290 }
291
292 gk_free((void **)&sgraphs, LTERM);
293 }
294
295
296 /*************************************************************************/
297 /*! This function performs multilevel node bisection (i.e., tri-section).
298 It performs multiple bisections and selects the best. */
299 /*************************************************************************/
MlevelNodeBisectionMultiple(ctrl_t * ctrl,graph_t * graph)300 void MlevelNodeBisectionMultiple(ctrl_t *ctrl, graph_t *graph)
301 {
302 idx_t i, mincut;
303 idx_t *bestwhere;
304
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);
308 return;
309 }
310
311 WCOREPUSH;
312
313 bestwhere = iwspacemalloc(ctrl, graph->nvtxs);
314
315 mincut = graph->tvwgt[0];
316 for (i=0; i<ctrl->nseps; i++) {
317 MlevelNodeBisectionL2(ctrl, graph, LARGENIPARTS);
318
319 if (i == 0 || graph->mincut < mincut) {
320 mincut = graph->mincut;
321 if (i < ctrl->nseps-1)
322 icopy(graph->nvtxs, graph->where, bestwhere);
323 }
324
325 if (mincut == 0)
326 break;
327
328 if (i < ctrl->nseps-1)
329 FreeRData(graph);
330 }
331
332 if (mincut != graph->mincut) {
333 icopy(graph->nvtxs, bestwhere, graph->where);
334 Compute2WayNodePartitionParams(ctrl, graph);
335 }
336
337 WCOREPOP;
338 }
339
340
341 /*************************************************************************/
342 /*! This function performs multilevel node bisection (i.e., tri-section).
343 It performs multiple bisections and selects the best. */
344 /*************************************************************************/
MlevelNodeBisectionL2(ctrl_t * ctrl,graph_t * graph,idx_t niparts)345 void MlevelNodeBisectionL2(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
346 {
347 idx_t i, mincut, nruns=5;
348 graph_t *cgraph;
349 idx_t *bestwhere;
350
351 /* if the graph is small, just find a single vertex separator */
352 if (graph->nvtxs < 5000) {
353 MlevelNodeBisectionL1(ctrl, graph, niparts);
354 return;
355 }
356
357 WCOREPUSH;
358
359 ctrl->CoarsenTo = gk_max(100, graph->nvtxs/30);
360
361 cgraph = CoarsenGraphNlevels(ctrl, graph, 4);
362
363 bestwhere = iwspacemalloc(ctrl, cgraph->nvtxs);
364
365 mincut = graph->tvwgt[0];
366 for (i=0; i<nruns; i++) {
367 MlevelNodeBisectionL1(ctrl, cgraph, 0.7*niparts);
368
369 if (i == 0 || cgraph->mincut < mincut) {
370 mincut = cgraph->mincut;
371 if (i < nruns-1)
372 icopy(cgraph->nvtxs, cgraph->where, bestwhere);
373 }
374
375 if (mincut == 0)
376 break;
377
378 if (i < nruns-1)
379 FreeRData(cgraph);
380 }
381
382 if (mincut != cgraph->mincut)
383 icopy(cgraph->nvtxs, bestwhere, cgraph->where);
384
385 WCOREPOP;
386
387 Refine2WayNode(ctrl, graph, cgraph);
388
389 }
390
391
392 /*************************************************************************/
393 /*! The top-level routine of the actual multilevel node bisection */
394 /*************************************************************************/
MlevelNodeBisectionL1(ctrl_t * ctrl,graph_t * graph,idx_t niparts)395 void MlevelNodeBisectionL1(ctrl_t *ctrl, graph_t *graph, idx_t niparts)
396 {
397 graph_t *cgraph;
398
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;
404
405 cgraph = CoarsenGraph(ctrl, graph);
406
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);
410
411 Refine2WayNode(ctrl, graph, cgraph);
412 }
413
414
415 /*************************************************************************/
416 /*! This function takes a graph and a tri-section (left, right, separator)
417 and splits it into two graphs.
418
419 This function relies on the fact that adjwgt is all equal to 1.
420 */
421 /*************************************************************************/
SplitGraphOrder(ctrl_t * ctrl,graph_t * graph,graph_t ** r_lgraph,graph_t ** r_rgraph)422 void SplitGraphOrder(ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph,
423 graph_t **r_rgraph)
424 {
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];
428 idx_t *rename;
429 idx_t *auxadjncy;
430 graph_t *lgraph, *rgraph;
431
432 WCOREPUSH;
433
434 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->SplitTmr));
435
436 nvtxs = graph->nvtxs;
437 xadj = graph->xadj;
438 vwgt = graph->vwgt;
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);
446
447 rename = iwspacemalloc(ctrl, nvtxs);
448
449 snvtxs[0] = snvtxs[1] = snvtxs[2] = snedges[0] = snedges[1] = snedges[2] = 0;
450 for (i=0; i<nvtxs; i++) {
451 k = where[i];
452 rename[i] = snvtxs[k]++;
453 snedges[k] += xadj[i+1]-xadj[i];
454 }
455
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;
462
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;
469
470 /* Go and use bndptr to also mark the boundary nodes in the two partitions */
471 for (ii=0; ii<graph->nbnd; ii++) {
472 i = bndind[ii];
473 for (j=xadj[i]; j<xadj[i+1]; j++)
474 bndptr[adjncy[j]] = 1;
475 }
476
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)
481 continue;
482
483 istart = xadj[i];
484 iend = xadj[i+1];
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;
490 }
491 else {
492 auxadjncy = sadjncy[mypart];
493 l = snedges[mypart];
494 for (j=istart; j<iend; j++) {
495 k = adjncy[j];
496 if (where[k] == mypart)
497 auxadjncy[l++] = k;
498 }
499 snedges[mypart] = l;
500 }
501
502 svwgt[mypart][snvtxs[mypart]] = vwgt[i];
503 slabel[mypart][snvtxs[mypart]] = label[i];
504 sxadj[mypart][++snvtxs[mypart]] = snedges[mypart];
505 }
506
507 for (mypart=0; mypart<2; mypart++) {
508 iend = snedges[mypart];
509 iset(iend, 1, sadjwgt[mypart]);
510
511 auxadjncy = sadjncy[mypart];
512 for (i=0; i<iend; i++)
513 auxadjncy[i] = rename[auxadjncy[i]];
514 }
515
516 lgraph->nvtxs = snvtxs[0];
517 lgraph->nedges = snedges[0];
518 rgraph->nvtxs = snvtxs[1];
519 rgraph->nedges = snedges[1];
520
521 SetupGraph_tvwgt(lgraph);
522 SetupGraph_tvwgt(rgraph);
523
524 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->SplitTmr));
525
526 *r_lgraph = lgraph;
527 *r_rgraph = rgraph;
528
529 WCOREPOP;
530 }
531
532
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.
536
537 This function relies on the fact that adjwgt is all equal to 1.
538
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
547 connected component.
548
549 \returns an array of subgraphs corresponding to the extracted subgraphs.
550 */
551 /*************************************************************************/
SplitGraphOrderCC(ctrl_t * ctrl,graph_t * graph,idx_t ncmps,idx_t * cptr,idx_t * cind)552 graph_t **SplitGraphOrderCC(ctrl_t *ctrl, graph_t *graph, idx_t ncmps,
553 idx_t *cptr, idx_t *cind)
554 {
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;
558 idx_t *rename;
559 idx_t *auxadjncy;
560 graph_t **sgraphs;
561
562 WCOREPUSH;
563
564 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->SplitTmr));
565
566 nvtxs = graph->nvtxs;
567 xadj = graph->xadj;
568 vwgt = graph->vwgt;
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);
576
577 /* Go and use bndptr to also mark the boundary nodes in the two partitions */
578 for (ii=0; ii<graph->nbnd; ii++) {
579 i = bndind[ii];
580 for (j=xadj[i]; j<xadj[i+1]; j++)
581 bndptr[adjncy[j]] = 1;
582 }
583
584 rename = iwspacemalloc(ctrl, nvtxs);
585
586 sgraphs = (graph_t **)gk_malloc(sizeof(graph_t *)*ncmps, "SplitGraphOrderCC: sgraphs");
587
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++) {
593 i = cind[j];
594 rename[i] = snvtxs++;
595 snedges += xadj[i+1]-xadj[i];
596 }
597
598 sgraphs[iii] = SetupSplitGraph(graph, snvtxs, snedges);
599
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;
605
606 snvtxs = snedges = sxadj[0] = 0;
607 for (ii=cptr[iii]; ii<cptr[iii+1]; ii++) {
608 i = cind[ii];
609
610 istart = xadj[i];
611 iend = xadj[i+1];
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;
617 }
618 else {
619 l = snedges;
620 for (j=istart; j<iend; j++) {
621 k = adjncy[j];
622 if (where[k] != 2)
623 sadjncy[l++] = k;
624 }
625 snedges = l;
626 }
627
628 svwgt[snvtxs] = vwgt[i];
629 slabel[snvtxs] = label[i];
630 sxadj[++snvtxs] = snedges;
631 }
632
633 iset(snedges, 1, sadjwgt);
634 for (i=0; i<snedges; i++)
635 sadjncy[i] = rename[sadjncy[i]];
636
637 sgraphs[iii]->nvtxs = snvtxs;
638 sgraphs[iii]->nedges = snedges;
639
640 SetupGraph_tvwgt(sgraphs[iii]);
641 }
642
643 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->SplitTmr));
644
645 WCOREPOP;
646
647 return sgraphs;
648 }
649
650
651 /*************************************************************************/
652 /*! This function uses MMD to order the graph. The vertices are numbered
653 from lastvtx downwards. */
654 /*************************************************************************/
MMDOrder(ctrl_t * ctrl,graph_t * graph,idx_t * order,idx_t lastvtx)655 void MMDOrder(ctrl_t *ctrl, graph_t *graph, idx_t *order, idx_t lastvtx)
656 {
657 idx_t i, j, k, nvtxs, nofsub, firstvtx;
658 idx_t *xadj, *adjncy, *label;
659 idx_t *perm, *iperm, *head, *qsize, *list, *marker;
660
661 WCOREPUSH;
662
663 nvtxs = graph->nvtxs;
664 xadj = graph->xadj;
665 adjncy = graph->adjncy;
666
667 /* Relabel the vertices so that it starts from 1 */
668 k = xadj[nvtxs];
669 for (i=0; i<k; i++)
670 adjncy[i]++;
671 for (i=0; i<nvtxs+1; i++)
672 xadj[i]++;
673
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);
680
681 genmmd(nvtxs, xadj, adjncy, iperm, perm, 1, head, qsize, list, marker, IDX_MAX, &nofsub);
682
683 label = graph->label;
684 firstvtx = lastvtx-nvtxs;
685 for (i=0; i<nvtxs; i++)
686 order[label[i]] = firstvtx+iperm[i]-1;
687
688 /* Relabel the vertices so that it starts from 0 */
689 for (i=0; i<nvtxs+1; i++)
690 xadj[i]--;
691 k = xadj[nvtxs];
692 for (i=0; i<k; i++)
693 adjncy[i]--;
694
695 WCOREPOP;
696 }
697
698
699
700
701
702