34 if (options[0] == 0) {
66 for (i=0; i<*nvtxs; i++)
82 int i, ii, j, l, wflag, nflag;
90 if (options[0] == 0) {
123 piperm =
idxmalloc(*nvtxs,
"ONMETIS: piperm");
125 PruneGraph(&ctrl, &graph, *nvtxs, xadj, adjncy, piperm, (
float)(0.1*ctrl.
pfactor));
131 cptr =
idxmalloc(*nvtxs+1,
"ONMETIS: cptr");
132 cind =
idxmalloc(*nvtxs,
"ONMETIS: cind");
134 CompressGraph(&ctrl, &graph, *nvtxs, xadj, adjncy, cptr, cind);
140 else if (2*graph.
nvtxs < *nvtxs && ctrl.
nseps == 1)
162 if (graph.
nvtxs < *nvtxs) {
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;
175 for (i=0; i<graph.
nvtxs; i++)
177 for (l=ii=0; ii<graph.
nvtxs; ii++) {
179 for (j=cptr[i]; j<cptr[i+1]; j++)
180 iperm[cind[j]] = l++;
188 for (i=0; i<*nvtxs; i++)
216 if (options[0] == 0) {
248 for (i=0; i<*nvtxs; i++)
265 int i, j, nvtxs, nbnd, tvwgt, tpwgts2[2];
269 nvtxs = graph->
nvtxs;
273 tpwgts2[0] = tvwgt/2;
274 tpwgts2[1] = tvwgt-tpwgts2[0];
296 label = graph->
label;
297 for (i=0; i<nbnd; i++)
298 order[label[bndind[i]]] = --lastvtx;
308 MMDOrder(ctrl, &rgraph, order, lastvtx);
325 int i, j, nvtxs, nbnd, tvwgt, tpwgts2[2], nsgraphs, ncmps, rnvtxs;
330 nvtxs = graph->
nvtxs;
334 tpwgts2[0] = tvwgt/2;
335 tpwgts2[1] = tvwgt-tpwgts2[0];
343 label = graph->
label;
344 for (i=0; i<nbnd; i++)
345 order[label[bndind[i]]] = --lastvtx;
347 cptr =
idxmalloc(nvtxs,
"MlevelNestedDissectionCC: cptr");
348 cind =
idxmalloc(nvtxs,
"MlevelNestedDissectionCC: cind");
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);
374 rnvtxs += sgraphs[i].
nvtxs;
388 int i, nvtxs, cnvtxs, mincut, tmp;
397 nvtxs = graph->
nvtxs;
400 bestwhere =
idxmalloc(nvtxs,
"MlevelNodeBisection2: bestwhere");
403 for (i=ctrl->
nseps; i>0; i--) {
408 if (graph->
mincut < mincut) {
431 cnvtxs = cgraph->
nvtxs;
433 bestwhere =
idxmalloc(cnvtxs,
"MlevelNodeBisection2: bestwhere");
436 for (i=ctrl->
nseps; i>0; i--) {
442 if (cgraph->
mincut < mincut) {
481 switch (ctrl->
IType) {
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];
514 idxtype *auxadjncy, *auxadjwgt;
518 nvtxs = graph->
nvtxs;
524 label = graph->
label;
525 where = graph->
where;
532 snvtxs[0] = snvtxs[1] = snvtxs[2] = snedges[0] = snedges[1] = snedges[2] = 0;
533 for (i=0; i<nvtxs; i++) {
535 rename[i] = snvtxs[k]++;
536 snedges[k] += xadj[i+1]-xadj[i];
540 sxadj[0] = lgraph->
xadj;
541 svwgt[0] = lgraph->
vwgt;
543 sadjncy[0] = lgraph->
adjncy;
544 sadjwgt[0] = lgraph->
adjwgt;
545 slabel[0] = lgraph->
label;
548 sxadj[1] = rgraph->
xadj;
549 svwgt[1] = rgraph->
vwgt;
551 sadjncy[1] = rgraph->
adjncy;
552 sadjwgt[1] = rgraph->
adjwgt;
553 slabel[1] = rgraph->
label;
556 for (ii=0; ii<graph->
nbnd; ii++) {
558 for (j=xadj[i]; j<xadj[i+1]; j++)
559 bndptr[adjncy[j]] = 1;
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)
570 if (bndptr[i] == -1) {
571 auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
572 for(j=istart; j<iend; j++)
573 auxadjncy[j] = adjncy[j];
574 snedges[mypart] += iend-istart;
577 auxadjncy = sadjncy[mypart];
579 for (j=istart; j<iend; j++) {
581 if (where[k] == mypart)
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];
593 for (mypart=0; mypart<2; mypart++) {
594 iend = snedges[mypart];
595 idxset(iend, 1, sadjwgt[mypart]);
597 auxadjncy = sadjncy[mypart];
598 for (i=0; i<iend; i++)
599 auxadjncy[i] = rename[auxadjncy[i]];
602 lgraph->
nvtxs = snvtxs[0];
603 lgraph->
nedges = snedges[0];
604 rgraph->
nvtxs = snvtxs[1];
605 rgraph->
nedges = snedges[1];
619 int i, j, k, nvtxs, nofsub, firstvtx;
620 idxtype *xadj, *adjncy, *label;
621 idxtype *perm, *iperm, *head, *qsize, *list, *marker;
623 nvtxs = graph->
nvtxs;
631 for (i=0; i<nvtxs+1; i++)
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;
641 genmmd(nvtxs, xadj, adjncy, iperm, perm, 1, head, qsize, list, marker,
MAXIDX, &nofsub);
643 label = graph->
label;
644 firstvtx = lastvtx-nvtxs;
645 for (i=0; i<nvtxs; i++)
646 order[label[i]] = firstvtx+iperm[i]-1;
651 for (i=0; i<nvtxs+1; i++)
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;
669 idxtype *auxadjncy, *auxadjwgt;
673 nvtxs = graph->
nvtxs;
679 label = graph->
label;
680 where = graph->
where;
686 for (ii=0; ii<graph->
nbnd; ii++) {
688 for (j=xadj[i]; j<xadj[i+1]; j++)
689 bndptr[adjncy[j]] = 1;
695 for (iii=0; iii<ncmps; iii++) {
697 snvtxs = snedges = 0;
698 for (j=cptr[iii]; j<cptr[iii+1]; j++) {
700 rename[i] = snvtxs++;
701 snedges += xadj[i+1]-xadj[i];
705 sxadj = sgraphs[iii].
xadj;
706 svwgt = sgraphs[iii].
vwgt;
708 sadjncy = sgraphs[iii].
adjncy;
709 sadjwgt = sgraphs[iii].
adjwgt;
710 slabel = sgraphs[iii].
label;
712 snvtxs = snedges = sxadj[0] = 0;
713 for (ii=cptr[iii]; ii<cptr[iii+1]; ii++) {
718 if (bndptr[i] == -1) {
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;
727 for (j=istart; j<iend; j++) {
735 svwgt[snvtxs] = vwgt[i];
736 sadjwgtsum[snvtxs] = snedges-sxadj[snvtxs];
737 slabel[snvtxs] = label[i];
738 sxadj[++snvtxs] = snedges;
741 idxset(snedges, 1, sadjwgt);
742 for (i=0; i<snedges; i++)
743 sadjncy[i] = rename[sadjncy[i]];
745 sgraphs[iii].
nvtxs = snvtxs;
746 sgraphs[iii].
nedges = snedges;
747 sgraphs[iii].
ncon = 1;
750 sgraphs[iii].
adjwgt = NULL;
#define Compute2WayNodePartitionParams
void METIS_NodeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options, idxtype *perm, idxtype *iperm)
#define COMPRESSION_FRACTION
#define ConstructMinCoverSeparator
void METIS_NodeWND(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, int *numflag, int *options, idxtype *perm, idxtype *iperm)
#define MlevelNodeBisectionMultiple
#define Compute2WayPartitionParams
#define Change2FNumberingOrder
#define Allocate2WayNodePartitionMemory
#define AllocateWorkSpace
#define MlevelNestedDissection
#define IFSET(a, flag, cmd)
#define SplitGraphOrderCC
#define ConstructSeparator
#define Change2CNumbering
void GKfree(void **ptr1,...)
void METIS_EdgeND(int *nvtxs, idxtype *xadj, idxtype *adjncy, int *numflag, int *options, idxtype *perm, idxtype *iperm)
#define MlevelNestedDissectionCC
#define MlevelEdgeBisection
#define MlevelNodeBisection
#define ORDER_UNBALANCE_FRACTION
#define Init2WayPartition